Графы и их применение

Знакомимся с важными и очень полезными объектами математики – графами. Для того чтобы вам было проще понять, что это такое, мы по ходу изложения материала будем уточнять это понятие.

Что такое граф?

Первое определение графа: графом (будем обозначать его буквой G) называется рисунок, состоящий их нескольких точек (вершин графа) и ребер – отрезков или дуг, соединяющих некоторые вершины.

На рисунке 1 показан пример графа.

К [pic] ак вы видите, ребрами соединены не все вершины графа. Вершины, из которых не выходит ни одного ребра, называют изолированными. (На рисунке изолированная вершина это точка G).

С помощью графов удобно и наглядно изображается информация о разных объектах и отношениях между ними. Рассмотрим пример.

П [pic] ример 1. В розыгрыше финальной части турнира участвуют семь команд: шесть команд, набравших наибольшее количество очков в предварительной части турнира и команда – победитель прошлого года. Сначала играют друг с другом первые шесть команд, затем три команды, одержавшие победы и команда, победитель прошлого года, играют друг с другом. Два победителя этого тура встречаются в финале.

Понять о чем идет речь в этом тексте нелегко. Попробуем представить его в виде наглядной схемы (смотри рисунок 2) и порядок организации финальной части розыгрыша станет очевидным.

Обратимся теперь к истории появления графов. Впервые в рассмотрение их ввел великий математик Леонард Эйлер. В популярной литературе часто упоминается его задача о Кенигсбергских мостах. Смысл задачи таков: в городе Кенигсберге (ныне это город Калининград) протекает река Прегель. Сам город расположен на берегах этой реки и ее островах. Естественно, что в городе построены мосты, связывающие все его районы (смотри рисунок 3). Во время прогулки по городу Эйлер захотел пройти по всем мостам, причем по каждому только один раз. Однако ему это не удалось. Вернувшись домой, ученый составил схему, изобразив участки суши точками, а мосты отрезками (рисунок 4). Это и был первый граф.

[pic] Мы ответим на вопрос, можно ли осуществить пешую прогулку по указанному правилу, в конце статьи, а сейчас рассмотрим некоторые важные свойства графов.

Определение 1. Степенью вершины графа называется число выходящих из него ребер.

Степени вершин А, В и D на рисунке 4 равны трем, а степень вершины С равна 5.

В [pic] графе на рисунке 1 степень вершины G равна нулю, так как из нее не выходит ни одно ребро.

Для степени вершины принято следующее обозначение: deg(A).

Рассмотрим некоторый граф G. Обозначим количество его вершин буквой p, а количество ребер буквой q. Сформулируем в виде теорем простейшие свойства степени.

Теорема 1. Сумма степеней всех вершин графа G равна удвоенному количеству его ребер (2q).

Граф называют простым, если две вершины соединяет не более одного ребра, в противном случае, граф называют мультиграфом. На рисунке 1 изображен простой граф, а на рисунке 4 мультиграф.

Теорема 2. В простом графе найдется не менее двух вершин с одинаковыми степенями.

Теорема 3. В простом графе с p вершинами число ребер не больше [pic] :

[pic] .

Определение 2. Граф называется полным, если каждая его вершина соединена со всеми другими вершинами графа.

Примеры полных графов вы можете построить сами: нарисуйте выпуклый многоугольник и постройте все его диагонали. Из доказательства теоремы 2 вытекает, что в полном графе с p вершинами [pic] ребер.

Пути, циклы, связность

Еще одно важное понятие, относящееся к графам – связность. Для того чтобы ввести его, дадим несколько определений. Начнем с понятия путь.

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

Р [pic] ассмотрим примеры. На рисунке 5 жирными линиями показан путь из точки А в точку В, который мы можем записать так: (AEDB). Другой путь из А в В показан пунктирными линиями, его можно записать как (l1l2l3).

Заметим, что может существовать несколько путей из одной точки в другую. В качестве устного упражнения сосчитайте, сколько всего путей можно указать из вершины А в вершину В.

Рассмотрим теперь специфический случай, когда начало и конец пути совпадают.

Определение 4. Циклом называется путь, у которого начало и конец совпадают.

На рисунке 5 циклами являются следующие пути: (AEFDA), (EFBCADE).

Упражнение. Попробуйте перечислить как можно больше циклов, содержащих точку А.

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

Определение 5. Граф называется связным, если любые две его вершины можно соединить хотя бы одним путем. В противном случае граф называется несвязным.

Граф на рисунке 1 несвязен, так как нет ни одного пути, соединяющего точку G с остальными вершинами, графы на рисунках 2, 4, 5 - связные.

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

Деревья

[pic] Важным частным случаем графа является дерево. Это название связано с типичным видом некоторых представителей данного класса. Дадим определение.

Определение 6. Деревом называется связный граф, не содержащий циклов. Несвязный граф, не имеющий циклов, называют лесом. (В лесу, как известно, не меньше двух деревьев.)

На рисунках 6 и 7 приведены примеры деревьев. Как видит читатель, далеко не все они напоминают по форме дерево. Тем не менее, можно так деформировать граф на рисунке 7, что он станет полностью похож на граф с рисунка 6. Нас естественно будет интересовать вопрос о том, когда граф является деревом. Ответ на него сформулируем ниже, а сейчас укажем одно интересное свойство деревьев.

Т [pic] еорема 6. В любом дереве существует хотя бы одна вершина степени единица. (Такие вершины называют «висячими».)

Теперь сформулируем теорему, являющуюся признаком дерева.

Теорема 7. Связный граф является деревом тогда и только тогда, когда количество его вершин на единицу превосходит количество ребер:

[pic] .

Упражнение. Найдите три минимальных остова графа на рис.5.

Планарные графы. Раскраски

Исторически планарные графы связаны с одной знаменитой задачей.

Задача о домиках и колодцах. В некоторой деревне есть три колодца. Трое жителей, живущие в трех стоящих рядом домиках перессорились, и решили так протоптать тропинки от своих домов к каждому из трех колодцев, чтобы они не пересекались. Удастся ли им выполнить свой план?

[pic]

П [pic] опробуем решить эту задачу. Проведем тропинки так, как это показано на рисунке 8. Как видно, нам удалось провести только восемь тропинок, а девятая должна пересечься хотя бы с одной. Можно доказать (мы не будем приводить строгое доказательство), что эта задача не имеет решения. Дело в том, что по мере проведения тропинок из двух первых домиков, будет получаться некоторый замкнутый контур, внутри которого будет стоять один из колодцев, при этом третий домик будет находиться снаружи от этого контура. Для того чтобы соединить этот домик с колодцем, обязательно потребуется пересечь новой тропинкой одну из уже проложенных.

Можно предложить еще одну задачу.

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

Эта задача также не может быть решена.

На рисунке 9 построены графы [pic] и [pic] , соответствующие задаче о домиках и колодцах и задаче о пяти хуторах. Оказывается, что проблема укладки графа на плоскости тесно связана с этими типами графов.

Перейдем теперь к более строгим формулировкам.

Определение 7. Граф называется планарным, если его можно изобразить на плоскости без самопересечений. Такое изображение называют плоской укладкой графа.

Н [pic] а рисунке 10 изображен полный граф [pic] и его плоская укладка.

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

Б [pic] удем говорить, что два графа гомеоморфны, если один из них получен из другого, путем добавления новых вершин на уже имеющиеся ребра.

На рисунке 11 показаны два гомеоморфных графа. Граф справа получен из первого графа добавлением четырех вершин. На практике бывает довольно трудно увидеть, что два графа гомеоморфны.

Задача о четырех красках. На политической карте мира нарисовано несколько государств. Карту нужно раскрасить так, что бы две страны, имеющие общую границу, были покрашены в разные цвета.

В классическом варианте предполагалось, что карту можно раскрасить четырьмя цветами. Покажем, как эта задача связана с графами. Обозначим каждую страну на карте точкой, вершины, отвечающие странам, имеющим общую границу, соединим ребрами. Теперь задачу о раскрашивании можно сформулировать так: раскрасить вершины планарного графа так, чтобы любые две смежные были покрашены в разные цвета. Эта задача может быть решена для графов с малым количеством вершин. Если же число вершин достаточно велико, то гипотеза четырех красок оказывается неверной. (Этот факт установлен с помощью мощных компьютеров.)

Вместе с тем, довольно простыми средствами была доказана теорема о пяти красках.

Теорема 9. Планарный граф можно раскрасить пятью красками так, что любые смежные вершины будут окрашены в разные цвета.

Еще одна интересная проблема: сколькими способами можно раскрасить граф ^{[link] Здесь граф необязательно должен быть планарен.}