Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг). Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку: как и геометрия, обладает наглядностью; как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи; не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»); имеет выраженный прикладной характер.
На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в 1976 году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетей.
Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее).
Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины, многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности. В разных областях знаний понятие «граф» может встречаться под следующими названиями: структура (гражданское строительство); сеть (электротехника); социограмма (социология и экономика); молекулярная структура (химия); навигационная карта (картография); распределительная сеть (энергетика) и так далее.
Первые использования и открытия графов
Теория графов как раздел прикладной математики «открывалась» несколько раз. Ключ к пониманию теории графов и её комбинаторной сущности отражены в словах Джеймса Сильвестра: «Теория отростков () — одна из теорий чистого обобщения, для неё не существенны ни размеры, ни положение объекта; в ней используются геометрические линии, но они относятся к делу не больше, чем такие же линии в генеалогических таблицах помогают объяснять законы воспроизведения».
Первое использование диаграммы графа в науке
Диаграмма одной из разновидностей графа — дерева — использовалась издавна (конечно, без понимания, что это «граф»). Генеалогическое древо применялось для наглядного представления родственных связей. Но только античный комментатор работ Аристотеля финикийский философ и математик Порфирий использовал изображение дерева в науке как иллюстрацию дихотомического деления в своей работе «» (, ) для классификации философского понятия материи.
Первое использование и «открытие» теории графов
Швейцарский, прусский и российский математик Леонард Эйлер в статье (на латинском языке, изданной Петербургской академией наук) о решении знаменитой задачи о кёнигсбергских мостах, датированной 1736 годом, первым применил идеи теории графов при доказательстве некоторых утверждений. При этом Эйлер не использовал ни сам термин «граф», ни какие-либо термины теории графов, ни изображения графов. Леонард Эйлер считается отцом теории графов (как и топологии), открывшим понятие графа, а 1736 год назначен годом рождения теории графов.
Второе «открытие» графов
В 1847 году немецкий физик Густав Кирхгоф фактически разработал теорию деревьев при решении системы уравнений для нахождения величины силы тока в каждом контуре электрической цепи. Кирхгоф фактически изучал вместо электрической цепи соответствующий ей граф и показал, что для решения системы уравнений нет необходимости анализировать каждый цикл графа, достаточно рассмотреть только независимые циклы, определяемые любым остовным деревом графа.
Третье «открытие» графов
В 1857 году английский математик Артур Кэли, занимаясь практическими задачами органической химии, открыл важный класс графов — деревья. Кэли пытался перечислить химические изомеры предельных (насыщенных) углеводородов CnH2n+2 с фиксированным числом n атомов углерода.
Четвёртое «открытие» графов
В 1859 году ирландский математик сэр Уильям Гамильтон придумал игру «Вокруг света». В этой игре использовался додекаэдр, каждая из 20 вершин которого соответствовала известному городу. От играющего требовалось обойти «вокруг света», то есть пройти по рёбрам додекаэдра так, чтобы пройти через каждую вершину ровно один раз.
Пятое «открытие» графов
В 1869 году, независимо от Артура Кэли, французский математик Камиль Жордан (в частности, в статье « Sur les assemblages de lignes ») придумал и исследовал деревья в рамках чистой математики. При этом Жордан использовал термины теории графов «вершина» () и «ребро» (), но вместо термина «граф» было «соединение рёбер» () или просто «соединение» (). Рисунки Жордан не использовал. При этом Жордан не подозревал о значении своего открытия для органической химии.
Soient x, y, z, u, … des points en nombre quelconque ; xy, xz, yu, … des arêtes droites ou courbes, mais non bifurquées, dont chacune joint ensemble deux de ces points. Nous appellerons un semblable système un assemblage d’arêtes, dont x, y, z, u, … sont les sommets.
Возникновение слова «граф» Первое появление слова «граф» в смысле теории графов состоялось в 1878 году в краткой заметке (на английском языке) английского математика Джеймса Сильвестра в журнале Nature и имеет графическое происхождение как обобщение понятий «диаграмма Кекуле» и «химикограф».
Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph.
В переводе:
Таким образом, каждый инвариант и ковариант выражается некоторым графом, точно идентичным диаграмме Кекуле или химикографу.
Начало систематического использования слова «граф» и диаграмм графов
Мы привычно рисуем точки, изображающие людей, населённые пункты, химические молекулы и т. д., и соединяем эти точки линиями, означающими отношения. Это социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т. д. В начале XX века венгерский математик Денеш Кёниг первый предложил называть эти схемы «графами» и изучать их общие свойства. В 1936 году вышла первая в мире книга по теории графов (на немецком языке) Денеша Кёнига «Теория конечных и бесконечных графов» с большей частью результатов за прошедшие 200 лет, начиная с 1736 года — даты выхода первой статьи Леонарда Эйлера по теории графов с решением задачи о кёнигсбергских мостах. В частности, в книге Кёнига имеется общий параграф для задачи о кёнигсбергских мостах и задаче о домино (построение замкнутой цепи из всех костей домино по правилам игры).
История возникновения теории графов
Теория графов (другими словами, системы линий, соединяющих заданные точки) очень удобна для начинающих: имеет геометрическую наглядность; имеет математическую содержательность; не имеет громоздкого математического аппарата.
«Как и теория чисел, теория графов концептуально проста, но порождает сложные нерешённые проблемы. Как и геометрия, она визуально приятна. Эти два аспекта, наряду с их разнообразными приложениями, делают теорию графов идеальным предметом для включения в учебные программы по математике».
Возникновение этого раздела математики в XVIII веке связано с математическими головоломками. Достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играх.
+ Краткая хронология событий развития теории графов Год Событие 1735 Представление Эйлером статьи по теории графов в Петербургской академии наук 1736 Год, считающийся годом рождения теории графов 1741 Публикация (датированная 1736 годом) статьи Эйлера по теории графов в Петербургской академии наук 1852 Френсис Гатри сообщает о проблеме четырёх красок Августу де Моргану 1879 Историческая публикация 1879 года с объяснением проблемы четырёх красок Артура Кэли 1879 Ошибочное «доказательство» проблемы четырёх красок Альфредом Кемпе 1890 Перси Джон Хивуд обнаружил ошибку в «доказательстве» Кемпе, доказал, что теорема верна, если «четыре» заменить на «пять», обобщил понятие «карты страны» с плоскости на замкнутые поверхности и сформулировал гипотезу Хивуда 1927 Лев Семёнович Понтрягин доказал (но не опубликовал) теорему Понтрягина — Куратовского 1930 Казимеж Куратовский опубликовал (независимо о Понтрягина) теорему Понтрягина — Куратовского 1936 Вышла первая в мире книга по теории графов Денеша Кёнига «Теория конечных и бесконечных графов» 1968 Группа математиков из разных стран доказала гипотезу Хивуда 1976 Группа математиков осуществили первое компьютерное доказательство теоремы о четырёх красках 1977 Фрэнк Харари основал журнал «Теория графов»
Геометрия положения
Отцом теории графов (как и топологии) считается швейцарский математик и механик Леонард Эйлер (1707—1783), написавший статью с решением задачи о кёнигсбергских мостах. Эйлер писал:
В дополнение к той ветви геометрии, которая занимается величинами и которой всегда уделялось самое большое внимание, существует другая ветвь, прежде почти неизвестная, о которой впервые упоминал Лейбниц, назвав её геометрией положения [geometria situs]. Эта ветвь занимается только определением положения и его свойствами, она не включает ни измерений, ни вычислений, с ними связанных...
Далее Эйлер пишет, что не ясно, какие задачи и методы их решения относятся к геометрии положения. Тем не менее, Эйлер считал кёнигсбергские мосты именно такой задачей, о чём говорит и заголовок статьи. В действительности, Готфрид Лейбниц не позже 1679 года написал в письме к Христиану Гюйгенсу:
Меня не удовлетворяет алгебра в том отношении, что не позволяет получить ни кратчайшие доказательства, ни самые красивые конструкции геометрии. Следовательно, в силу этого я считаю, что нам нужен другой способ анализа, геометрический или линейный, который прямо бы работал с положением точно так же, как алгебра работает с величиной...
Лейбниц, введя термин analysis situs (анализ положения), не заложил основы новой математической дисциплины, но указал направление будущих исследований.
Задача о кёнигсбергских мостах
Публикация статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения» о решении задачи о кёнигсбергских мостах имеет следующую историю: Эйлер представил статью на Конференции Петербургской академии наук; в 1736 году Эйлер отправил два письма: — письмо , австрийскому астроному и математику, которое целиком посвящено задаче о кёнигсбергских мостах; — письмо , немецкому политическому деятелю и астроному, в конце которого идёт речь об основных идеях статьи; в 1741 году в Санкт-Петербурге, наконец, вышла статья Эйлера на латинском языке с датой 1736 года:
Leonhardi Euleri. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140.
В переводе:
Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140.
Поскольку выход статьи Эйлера из печати датируется 1736 годом (и обоих писем тоже), этот год назначен датой рождения теории графов.
Эйлер в своей статье так сформулировал задачу о семи кёнигсбергских мостах:
В городе Кенигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, Ь, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.
В конце статьи Эйлер записал выводы вполне современным языком: