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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Деревья

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще одна интересная проблема: сколькими способами можно раскрасить граф¹, если имеется n красок.

Оказывается, что число способов раскрашивания является многочленом от n, коэффициенты этого многочлена можно вычислить с помощью специального алгоритма.

Укажем еще одно обобщение задачи о раскрасках. Известно, что граф без самопересечений располагается на некоторой поверхности (на сфере, на торе, на бутылке Клейна и т.п.), какое минимальное количество красок нужно для его раскрашивания?

Ответ на этот вопрос был получен в разделе математики, называющемся «топологией». Оказалось, что для всех замкнутых двумерных поверхностей (кроме сферы), данное число выражается через Эйлерову характеристику этой поверхности.

Двудольные графы

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

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

Если каждая вершина одной доли соединена ребром с каждой вершиной другой доли, то такой граф называют полным двудольным графом класса , где n и m - количество вершин в каждой доле.

Упражнение. Найдите количество ребер в графе .

Для произвольного графа естественно поставить вопрос: является ли он двудольным? Имеется точное условие, определяющее это свойство. Сформулируем это условие в виде теоремы.

Теорема 10. Граф является двудольным тогда и только тогда, когда все простые циклы, содержащиеся в этом графе, имеют четную длину. (То есть, все простые циклы состоят из четного количества ребер).

Напомним, что простой цикл проходит через каждую свою вершину ровно один раз.

Следует заметить, что, зная, что граф двудольный, весьма непросто разделить вершины этого графа по долям. Укажем один из методов, как это сделать (он, кстати, по сути, является доказательством теоремы).

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

Примеры решения задач

Рассмотрим несколько примеров, при решении которых успешно применяются графы.

Задача 1. Один из ребят сказал: «А у нас в классе 25 человек, и каждый дружит ровно с семью одноклассниками!»

«Не может быть этого», - ответил приятелю Витя Иванов, победитель олимпиады. Почему он так ответил?

Решение. Представим всех ребят в классе в виде вершин графа. Получим 25 вершин. Соединим вершины, обозначающие друзей, ребрами. Тогда из каждой вершины будет выходить по семь ребер. Сумма степеней вершин графа будет равна 25x7=175. Это нечетное число. А нам известно, что сумма степеней вершин графа должна быть четна. Получили противоречие.

Задача 2. В стране 15 городов, каждый соединен дорогами не менее чем с 7-ю другими. Докажите, что из любого города можно проехать в любой другой либо напрямую, либо через один промежуточный город.

Решение. Рассмотрим город А. Он соединен дорогами с не менее чем семью городами В₁, В₂, …, В₇, … Всего получилось не меньше 8 городов. Предположим, что есть город С, не связанный ни с А ни с В₁, В₂, …, В₇, … Значит он связан только с теми городами, которые остались вне этого списка. Но таких городов меньше 7, что противоречит условию.

Задача 3. В классе 28 человек. Каждая девочка дружит с 4 мальчиками, а каждый мальчик - с 3 девочками. Сколько в классе мальчиков и девочек?

Решение. В графе, для этой задачи вершины, соответствующие мальчикам, выкрасим синим цветом, а вершины, соответствующие девочкам - красным. Каждое ребро графа соединяет ровно две вершины: одну синюю и одну красную. Пусть всего x красных и y синих вершин (x+y=28 - уравнение №1). Выразим количество ребер в графе. С одной стороны, оно равно 3x, с другой - 4y. Получим уравнение №2: 3x=4y. Решая систему из двух уравнений, легко найти, что x=16 а y=12.

Задача 4. Докажите, что среди учеников любого класса найдутся двое, имеющие одинаковое число знакомых в этом классе (если, конечно, в этом классе не менее двух учеников).

Решение. Доказательство следует из теоремы 2, которая утверждает, что в любом графе существуют две вершины с одинаковой степенью. Изобразим класс в виде графа, вершины которого - ученики, а ребрами соединены только те вершины, которые обозначают знакомых. В этом графе есть две вершины с одинаковой степенью, следовательно, в классе есть двое ребят с одинаковым числом знакомых.

Задача 5. Расположите на плоскости 6 точек и соедините их непе­ресекающимися линиями так, чтобы из каждой точки вы­ходили четыре линии.

Решение. Смотри рисунок 12.

Задача 6. В марсианском метро 100 станций. От любой станции до любой другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными станциями был возможен проезд. Докажите, что такая станция найдётся.

Решение. План марсианского метро является связным графом. Возможны два варианта:

1 случай. Граф является деревом. Тогда этот граф имеет «висячую» вершину. Ее и следует перекрыть.

2 случай. Граф имеет циклы. Тогда нужно перекрыть одну из станций, принадлежащих этому циклу.

Контрольное задание

Представленные ниже задачи являются контрольным заданием для учащихся 8-9 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу:68000, г. Хабаровск, ул. Дзержинского 43, ХКЦТТ.

Для зачета нужно набрать не менее 20 баллов (количество баллов за каждую задачу указано в конце условия), но если вы решите задачи, оцененные ровно в 20 баллов, этого может оказаться недостаточно, так как за недочеты и ошибки баллы снимаются.

М8.3.1. В трёх вершинах правильного пятиугольника располо­жили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом до­биться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами? (5 баллов)

Указание: нетрудно заметить, что ребра такого графа образуют простой цикл, поэтому изменить порядок точек нельзя.

М8.3.2. На математической олимпиаде было предложено 20 за­дач. На закрытие пришло 20 школьников. Каждый из них решил по две задачи, причём выяснилось, что среди при­шедших каждую задачу решило ровно два школьника. До­кажите, что можно так организовать разбор задач, чтобы каждый школьник рассказал одну из решенных им задач, и все задачи были разобраны.(5 баллов)

Указание: постройте двудольный граф, одна доля которого - задачи, а другая - ученики. Каждая вершина этого графа будет иметь степень два. Поэтому данный граф может «развалиться» на несколько непересекающихся простых циклов. Распределите задачи между учениками внутри каждого цикла.

М8.3.3. В спортклубе тренируются 100 толстяков, веса которых равны 1 кг, 2 кг, ..., 100 кг. На какое наименьшее число команд их можно разделить, чтобы ни в какой команде не было двух толстяков, один из которых вдвое тяжелее другого? (10 баллов)

М8.3.4. В тридевятом царстве каждые два города соединены до­рогой с односторонним движением. Докажите, что суще­ствует город, из которого можно проехать в любой другой не более чем по двум дорогам. (10 баллов)

М8.3.5. В городе на каждом перекрестке сходится чётное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.(5 баллов)

Указание: используйте признак Эйлерового графа.

М8.3.6. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятёрок подряд стоящих цифр встреча­ются все 32 возможные комбинации. Найдите пять послед­них цифр последовательности. (10 баллов)

М8.3.7. Дан правильный 45-угольник. Можно ли так расста­вить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой за­нумерованы этими цифрами. (10 баллов)

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

М8.3.8. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из n символов, идущих подряд, встретился. (10 баллов)

Указание: рассмотрите граф, вершины которого суть сло­ва длины п-1. Две вершины и и v соединяются стрелкой, если существует слово длины п, у которого и является на­чалом, a v - концом.

М8.3.9. Рёбра дерева окрашены в два цвета. Если в какую-то вершину приходят рёбра только одного цвета, то их все можно перекрасить в другой цвет. Можно ли все дерево сделать одноцветным? (10 баллов)

Указание: рассмотрите сначала «висячие» вершины, ребра, которые из них выходят можно перекрашивать по своему усмотрению.

1</ Здесь граф необязательно должен быть планарен.