Введение.

ГРАФЫ

Примеры.

Пример 1. Таблица для конъюнкции.

x1	x2

Пример 2. Таблица для композиции f(x₁, x₂) =

x1	x2

Определение 31 (общее определение) Булева функция – функция f(x₁, x₂, …, x_n), которая по любому набору логических констант выдает логическую константу.

Теорема. Любая булева функция n переменных может быть задана с помощью композиции, содержащей конечное число только трех связок: дизъюнкции, конъюнкции и отрицания.

Любой из нас, конечно, прав,

Найдя без проволочек,

Что он … обыкновенный граф

Из палочек и точек.

Понятие «граф» – одно из самых простых и самых употребительных понятий в математике и других науках, хотя теория графов зародилась чуть ли не 250 лет тому назад в ходе решения головоломки, и тогда же появились первые теоремы о графах, доказанные самим Леонардом Эйлером.

Долгие годы эта теория не находила широких приложений и была известна в основном как средство решения головоломок, логических или развлекательных задач, задач олимпиадного типа или на смекалку. При решении таких задач удобно составлять таблицы, изображать объекты точками, соединять их отрезками или стрелками, подмечать закономерности из полученных рисунков, выполнять над точками и отрезками операции, не похожие на алгебраические и геометрические.

И в обычной жизни очень часто мы рисуем на бумаге точки, изображающие химические вещества, населенные пункты, генеалогические деревья и соединяем эти точки линиями и стрелками, означающими некоторые отношения между рассматриваемыми объектами. Такие схемы встречаются всюду под различными названиями: электрические цепи (в физике), карты, лабиринты, диаграммы, генеалогические деревья, диаграммы организации (в экономике), социограммы (в психологии) и т.д. В 1936 году Д. Кёниг предложил называть такие схемы графами и систематически изучать их свойства.

Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.

Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д.

Наиболее близки к графам – топология и комбинаторика.

Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который оканчивался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. Возможен ли вообще такой маршрут?

Для удобства решения составили схему или диаграмму. Части суши (оба берега и острова) обозначили точками А, В, С, D, а пути их соединяющие и проходящие по мостам, изобразим линиями, соединяющими эти точки. (Рис. 2) Такая схема содержит всю необходимую информацию о рассматриваемой ситуации и не содержит ничего лишнего. Глядя на нее, можем заключить только, что четыре объекта – А, В, С, D – попарно как-то связаны между собой ( в данном случае мостами), причем А с В и В с С соединены двойной связью, а D с каждым из объектов А, В и С – одинарной. Точки А, В, С, D – вершины, соединяющие их линии – ребра диаграммы.

Задача будет решена в ходе работы над схемой рисунка 2. (показано позднее)

Очевидно, что подобными схемами можно описать самые различные объекты и ситуации. Например, вершинами могут быть атомы в молекуле, а ребрами – связи между ними. Точно так же можно рассмотреть множество людей и соединить их попарно на схеме линиями в том случае, если они знакомы, или если они родственники. Существуют схемы метрополитена, железных или шоссейных дорог, планы выставок и т.д., словом, схемы и планы без указания масштаба, показывающие лишь связи между принадлежащими объектами, состоящие из вершин и ребер, однако с ними трудно проделывать формальные операции, следовательно, диаграммы из точек и линий надо заменить какими-то более формализованными моделями. Так пришли к графам.

П. 1. Основные понятия.

Определение 1. Будем говорить, что задан граф G, если задано конечное множество и некоторое множество W неупорядоченных пар различных элементов из V: . Таким образом, граф – это упорядоченная пара . Элементы множества V называют вершинами графа, а заданные пары этих элементов – ребрами. Множество ребер W, соединяющих элементы множества V, отображают это множество само в себя.

Замечание. Определение графа совпадает с определением отношения на множестве. Граф – бинарное отношение на множестве V , т.е. подмножество R множества (множество всех упорядоченных пар вида , где ).

В соответствие каждому графу можно поставить некоторую схему на плоскости, если вершины графа изобразить точками, или кружочками, или квадратиками, а ребра, соединяющие некоторые вершины, – отрезками прямых или кривых линий. Эту схему называют диаграммой графа, геометрическим графом или, для краткости, просто графом. Отсюда, определение 1 можно переписать в виде:

Определение 1^’. Граф представляет собой непустое множество точек и множество отрезков прямых или кривых линий, оба конца которых принадлежат заданному множеству. Граф с p вершинами и q ребрами называется (p, q) – графом.

Обозначения: граф – G или Г;

вершины – заглавными различными буквами А, В, С …, или маленькими различными буквами, или одинаковыми буквами с индексами х₁, х₂,... или числами 1, 2, 3…;

ребра – (А, В) или , или , или (х₁, х₂), или (1, 2) (отрезки, соединяющие вершины), или просто u₁, u₂…(первое ребро, второе и т.д.).

Определение 2. Петля – это ребро, концы которого совпадают. Вершины, которые не соединены ребрами, называются изолированными.

Задание графа (1 способ) Задать граф можно путем перечисления ребер графа с указанием концов и добавлением списка изолированных вершин, например, граф с множеством вершин и списком дуг .

Пример. Построить графы: а) Г = , b) .