Теория графов – от истоков к современности (80

УДК 519.1

К.А. Дридгер, к.п.н.

Теория графов – от истоков к современности.

В своей статье автор обращается к проблеме рассмотрения теории графов в историческом аспекте и в современном видении. В рамках данной статьи представлены базовые задачи теории графов, выделены основные направления исследований в этой области и типовые задачи.

Ключевые слова: граф, теория графов, история теории графов, задачи теории графов.

K.A. Dridger, candidate of pedagogics

The theory of graphs - from the beginnings to the present day.

In the article the author addresses to the consideration of graph theory in historical aspect and in the modern vision. In the framework of this article are presented the basic problems of the theory of graphs, defined the main directions of research in this area and the types of tasks.

Keywords: the graph, graph theory, history of the theory of graphs, problems of the theory of graphs.

Теория графов представляет собой раздел дискретной математики, в основу которого заложен геометрический подход к изучению объектов (как геометрических схем, представляющих собой системы линий, соединяющих заданные точки), сочетающий большую геометрическую наглядность с математической содержательностью и с возможностью обходиться без гро - моздкого аппарата [8, с. 8].

В настоящее время теория графов находится в стадии развития, причем интерес к этой математической области все больше возрастает, что, с точки зрения Фрэнка Харари, объясняется следующими причинами: «Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, эко-

1

номика, антропология и лингвистика. Эта теория тесно связана со многими разделами математики, среди которых теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Графы действуют притягательно и обладают эстетической привлекательностью... Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков» [9, с. 9].

В отличие от многих других научных дисциплин, истоки теории графов относятся к вполне определенному времени – в 1736 г. швейцарским математиком Леонардом Эйлером была опубликована первая работа, в которой были изложены результаты по решению математических развлекательных задач и головоломок. Более ста лет этот труд оставался единственным исследованием по теории графов.

Выделим основополагающие задачи практического характера, решение которых положило начало теории графов:

1)задача о «Кенигсбергских мостах»;

2)задача о существовании Эйлерова цикла (пути);

3)задача о шахматном коне;

4)задача о существовании Гамильтонова цикла;

5)задача «коммивояжера»;

6)задача о «трех домах и трех колодцах»;

7)задача о «четырех красках».

Историю решения первой (и самой знаменитой) задачи отражает переписка Эйлера и итальянского математика Маринони: «Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой,

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

2

доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором A обозначает остров, а B, C и D – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g» [7, с. 41-42]. Схематическое изображение условия задачи представлено на рис. 1.

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

Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими» [7, с. 102-103].

Рис. 1. Схема расположения Кенигсбергских мостов.

На поставленный вопрос Эйлер дает следующий ответ: «Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему

3

решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A

ведут пять мостов, а к остальным – по три моста, т. е. число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать» [7, с. 103-104].

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

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

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

4

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

Рис. 2. Иллюстрация к задаче о Кенигсбергских мостах и ее интерпретация в виде графа.

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

Среди головоломок, положивших начало теории графов, следует выделить еще одну – задача о шахматном коне, в который требуется пройти через все клетки доски, не ступив ни на одну дважды. Эта задача очень древняя, она впервые упоминается в книге «Китаб Аш-Шатрандж» Абу Бакра Мухаммада ас-Сули (IX в.). Однако систематическое изложение путей решения, предлагавшихся ранее, и своих собственных, основанных на симметрии пути коня, было выполнено Эйлером в 1766 г.

Отметим, что задача о «Кенигсбергских мостах» и задача о шахматном коне имеют принципиальное отличие: если в первой необходимо по одному

5

разу, не повторяясь, обойти все ребра графа, то во второй требуется обойти таким же образом все вершины.

Это отличие представило возможность исследования такого типа задач, в которых требуется определить существование пути, проходящего через каждую вершину графа, исключая начальную, только один раз, названного гамильтоновым в честь ирландского математика, физика и астронома Уильяма Гамильтона. В 1857 г. ученым была предложена настольная игра «Кругосветное путешествие», основой которой служил додекаэдр, т. е. правильный многогранник с 20-ю вершинами, каждая из его 12 граней являлась правильным пятиугольником (рис. 3). В этой конструкции в каждом из 20 углов вбивались гвоздики, изображавшие города, к одному гвоздику привязывалась веревка, с помощью которой требовалось найти путь через эти города, посетив каждый из них ровно один раз, и вернуться в исходный город. В таком случае формально проблема сводится к нахождению цикла в графе, в некотором смысле противоположного эйлерову циклу, который проходит через все ребра только один раз [4, с. 99].

Рис. 3. Схематическое представление игры «Кругосветное путешествие Независимо от У. Гамильтона исследования на эту же тему проводил

британский математик Томас Киркман, которому принадлежит заслуга выявления класса многогранников, на которых вышеуказанная задача неразрешима.

6

Со временем, после некоторого изменения условий, эта головоломка превратилась в так называемую задачу «коммивояжера». Это задача поиска минимального гамильтонова цикла, суть ее состоит в следующем: пусть даны п городов и задана таблица попарных расстояний между ними, требуется найти циклический путь обхода по одному разу всех городов, при этом путь должен иметь минимально возможную длину. В более общих формулировках для пары вершин задается значение некоторой функции и требуется найти цикл, при котором общее значение функции минимизируется или максимизируется [4, с. 99]. В 1930-х гг. ее изучением занимались австрийский математик Карл Менгер, а позже Хаслер Уитни и Мерил Флуд. Эту задачу сегодня относят к классу NP-

трудных задач.

Еще одна знаменитая головоломка о «трех домах и трех колодцах» заключается в том, что на одном участке земли построены три дома и вырыты три колодца, требуется провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. На рис. 4 изображён граф, отвечающий естественному расположению тропинок, где точками A, B, C обозначены дома, а X, Y, Z соответственно колодцы [4, с. 95].

Рис. 4. Иллюстрация к задаче о «трех домах и трех колодцах» В 1917 г. Генри Э. Дьюдени переформулировал данную задачу: в каждый

из трёх домов, изображенных на рис. 5, необходимо провести газ, свет и воду, посредством подземных линий труб и кабелей. Вопрос состоит в том, можно ли обеспечить эти три дома коммунальными услугами без пересечения линий снабжения. Граф, моделирующий данную задачу, представлен на рис. 6 [2, с. 246-247].

7

в 1890 г. английским математиком Перси Хивудом было доказано утверждение

отом, что такая возможность определена при использовании 5 цветов.

Вдальнейшем разрешение этой проблемы также занимало умы ученых: в 1904 г. немецкий тополог Вернике представил список так называемых «неизбежных» фрагментов, один из которых присутствует в любой карте;

американский математик Дэвид Биркхоф в 1912 г. ввел понятие «хроматический полином», под которым понимается число возможных раскрасок графа заданным количеством цветов; американский математик Филипп Франклин в 1922 г. доказал гипотезу для карт, содержащих не больше 25 стран. В итоге эту проблему удалось свести к исследованию верности гипотезы о 4 красках для достаточно большого числа графов (около 30 тыс.), что и было сделано американскими математиками Вольфгангом Хакеном и Кеннетом Аппелем впервые с помощью компьютеров в 1976 г. [3, с. 71]. Однако попытки упростить доказательство настолько, чтобы оно было доступно человеку, предпринимаются до сих пор. Задача определения так называемого «хроматического числа графа», т. е. минимального числа цветов, в которые граф можно раскрасить, также как и задача «коммивояжера», относится к классу NP-полных задач.

От класса многочисленных головоломок, игр и развлекательных задач, представляющих для большинства ученых «несерьезную» тему, теория графов постепенно стала затрагивать важные практические проблемы, многие из которых требовали тонких математических методов [6, с. 10]. В этом отношении судьбу теории графов можно сравнить с судьбой теории вероятностей, также первоначально рассматривавшейся лишь в связи с ее «применениями» к азартным играм [8, с. 6].

Так, в середине XIX в. немецкий физик Густав Роберт Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по представлять такую схему графом и находить в этом графе остовные деревья, с помощью которых выделяются линейно независимые системы контуров; английский математик Артур Кэли,

9

исходя из задач выявления и перечисления изомеров насыщенных углеводородов, в 1857 г. пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них [6, с. 10].

В XX в. задачи, связанные с графами, стали возникать не только в прикладных отраслях, но и внутри самой математики (в топологии, алгебре,

теории вероятностей и др.). Графы начали использовать для представления математических объектов в различных дискретных задачах, причем в качестве синонимов к термину «граф» употребляли и другие понятия - диаграмма, карта, комплекс, лабиринт, сеть, схема. В 1936 г. вышли труды венгерского математика Джозефа Кенига и норвежского математика Ойстена Оре, благодаря которым термин «граф» стал наиболее употребительным, чем вышеперечисленные. Отдельно теории графов посвящена вышедшая в 1962 г. работа французского математика Клода Бержа «Теория графов и её приложение». Однако теория графов как самостоятельная математическая дисциплина сформировалась только к середине 30-х гг. XX в. на основе трудов таких математиков, как В.Г. Визинг, А.А. Зыков, Л.С. Понтрягин. В это время появились первые результаты, относящиеся к изучению свойств графов - связности, планарности, симметрии, которые привели к формированию ряда новых направлений в теории графов [6, С. 10].

С развитием кибернетики и вычислительной техники в конце 40-х - начале

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

На наш взгляд, к основным направлениям исследований по теории графов можно отнести следующие:

1.Исследования комбинаторного характера (например, задачи о подсчете графов или их частей, обладающих заданными свойствами, задачи о построении графов с фиксированными свойствами, анализ и

10