Теория графов представляет собой раздел математики, имеющий широкое
практическое применение. В её терминах формулируется большое число
задач, связанных с дискретными объектами. Такие задачи возникают при
проектировании интегральных схем и схем управления, электрических цепей,
блок-схем программ, в экономике, статистике, химии, биологии и в других
областях. Теория графов становится одной из существенных частей
математического аппарата кибернетики, языком дискретной математики.
В отличие от других научных дисциплин, теория графов имеет вполне
определенную дату рождения. Первая работа по теории графов, написанная
швейцарским математиком Леонардом Эйлером (1707-1783), была опубликована
в 1736 году в Трудах Академии наук в Санкт-Петербурге. Исследование
Эйлера было проведено в связи с популярной в то время задачей о
кенигсбергских мостах.
В связи с этим Эйлера пишет письмо итальянскому математику и инженеру Маринони:
"Некогда
мне была предложена задача об острове, расположенном в городе
Кенигсберге и окруженном рекой, через которую перекинуто семь мостов.
Спрашивается, может ли кто- нибудь непрерывно обойти их, проходя только
однажды через каждый мост. И тут же мне было сообщено, что никто еще до
сих пор не мог это проделать, но никто и не доказал, что это невозможно.
Вопрос этот, хотя и банальный, показался мне, однако, достойным
внимания тем, что для его решения недостаточны ни геометрия, ни алгебра,
ни комбинаторное искусство… После долгих размышлений я нашел легкое
правило, основанное на вполне убедительном доказательстве, с помощью
которого можно во всех задачах такого рода тотчас же определить, может
ли быть совершен такой обход через какое угодно число и как угодно
расположенных мостов или не может. Кенигсбергские же мосты расположены
так, что их можно представить на следующем рисунке
, на котором A
обозначает остров, а B, C и D – части континента, отделенные друг от
друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g
":
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:
"Это решение по своему
характеру, по-видимому, имеет мало отношения к математике, и мне
непонятно, почему следует скорее от математика ожидать этого решения,
нежели от какого-нибудь другого человека, ибо это решение подкрепляется
одним только рассуждением, и нет необходимости привлекать для нахождения
этого решения какие-либо законы, свойственные математике. Итак, я не
знаю, каким образом получается, что вопросы, имеющие совсем мало
отношения к математике, скорее разрешается математиками, чем другими".
В другом письме Эйлера к
Маринони: "Вопрос состоит в том, чтобы определить, можно ли
обойти все эти семь мостов, проходя через каждый только однажды, или
нельзя. Мое правило приводит к следующему решению этого вопроса.
Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, –
таких, у которых нет другого перехода с одного на другой, кроме как
через мост. В данном примере таких участков четыре – A, B, C, D. Далее
нужно различать, является ли число мостов, ведущих к этим отдельным
участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным
– по три моста, т. е. Число мостов, ведущих к отдельным участкам,
нечетно, а этого одного уже достаточно для решения задачи. Когда это
определено, применяем следующее правило: если бы число мостов, ведущих к
каждому отдельному участку, было четным, то тогда обход, о котором идет
речь, был бы возможен, и в то же время можно было бы начать этот обход с
любого участка.Если же из этих чисел два были бы нечетные, ибо
только одно быть нечетным не может, то и тогда мог бы совершиться
переход, как это предписано, но только начало обхода непременно должно
быть взято от одного из тех двух участков, к которым ведет нечетное
число мостов. Если бы, наконец, было больше двух участков, к которым
ведет нечетное число мостов, то тогда такое движение вообще невозможно…
если можно было привести здесь другие, более серьезные задачи, этот
метод мог бы принести еще большую пользу и им не следовало бы
пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к
своему другу Элеру. В нем Эйлер писал, что переход возможен, если на участке разветвления
реки имеется не более двух областей, в которые ведет нечетное число
мостов. Для того, чтобы проще представить себе это, будем стирать на
рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться
в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на
рисунке будет изображен участок, где опять имеется не более двух областей,
в которые ведет нечетное число мостов, а при наличии областей с нечетным
числом мостов мы будем располагаться в одной из них. Продолжая двигаться
так далее, пройдем через все мосты по одному разу.
Эйлер дал ответ на задачу про Кенигсбергские мосты и нашел критерий существования
маршрута, удовлетворяющего требованиям задачи.Однако результат, полученный Эйлером, более ста лет оставался единственным результатом теории графов.Развитие теории графов в конце XIX и начале XX вв. было связано с
распространением представлений о молекулярном строении вещества и
становлением теории электрических цепей. К 50-м годам XX века в
теории графов сложились два различных направления: алгебраическое и
оптимизационное.Например, поиск ответа на поставленный в задаче о Кенигсбергских вопрос относится к
алгебраическому направлению теории графов. А в задаче, где требуется
найти маршрут, по которому житель, выйдя из дома, пройдет по каждому
мосту хотя бы один раз и вернется домой, причем длина маршрута должна
быть минимальной, задача поиска такого маршрута относится к оптимизационному
направлению теории графов.Оптимизационное направление получило широкое развитие благодаря
появлению ЭВМ, так как для эффективного использования ЭВМ при решении
прикладных задач с использованием теории графов необходимы эффективные
алгоритмы решения графовых задач. Широкое развитие теория графов получила в 50-х гг. XX века в связи со
становлением кибернетики и развитием вычислительной техники, когда теория графов
существенно обогатилась и новым материалом, и новыми подходами и когда
началось систематическое изучение графов с разных точек зрения
(структурной, информационной и т. д.). Именно в это время
формулировались проблематика и методы теории графов. Теория графов находит применение в
теории программирования и при построении вычислительных машин, в
изучении физических, химических и технологических процессов, в решении
задач планирования, в лингвистических и социологических исследованиях и
т. д. Теория графов имеет тесные связи как с классическими, так и с новыми
разделами математики; это — топология, алгебра, комбинаторный анализ,
теория чисел, теория минимизации булевских функций. Теория графов включает
большое число разнообразных задач. Одни из них группируются в отдельные
направления, другие стоят более изолированно. Среди сложившихся разделов
Теория графов следует отметить задачи, относящиеся к анализу графов,
определению различных характеристик их строения, например выяснение
связности графа: можно ли из любой вершины попасть в любую; подсчёт
графов или их частей, обладающих заданными свойствами, например подсчёт
количества деревьев с заданным числом рёбер (дерево — неориентированный
граф без циклов); решение транспортных задач, связанных с перевозками
грузов по сети. Решен ряд задач по синтезу графов с заданными
свойствами, например построение графа с заданными степенями вершин
(степень вершины — число выходящих из неё рёбер). Имеет прикладное и
теоретическое значение задача о выяснении возможности расположения графа
на плоскости без самопересечений его рёбер (т. е. является ли данный
граф плоским), задача о разбиении графа на минимальное число плоских
графов. Для некоторых задач Теория графов (выше были приведены далеко не все)
были разработаны методы их решения. Среди них: метод Пойя перечисления и
подсчёта графов с заданными свойствами, теорема и алгоритм Форда —
Фалкерсона для решения транспортной задачи, «венгерский» алгоритм
решения задачи о назначениях и т. д. Почти все задачи теории конечных
графов (практически интересны именно графы с конечным числом вершин)
могут быть решены путём перебора большого числа вариантов (точнее полный
перебор), поэтому для них требуется построение эффективных алгоритмов и
использование быстродействующих вычислительных машин. Такими задачами
являются: задача о раскраске вершин графа, задача об определении
идентичности двух графов, Коммивояжёра задача.
Есть задачи, требующие принципиального ответа, например задача о
раскраске плоских графов, задача о восстановлении графа по его
подграфам и многие другие.
