Теория графов

Тео́рия гра́фов — раздел дискретной математики, изучающий графы. В самом общем смысле граф — это множество точек (вершин, узлов), которые соединяются множеством линий (рёбер, дуг)^[1]. Теория графов (то есть систем линий, соединяющих заданные точки) включена в учебные программы для начинающих математиков, поскольку^[2]^[3]^[4]^[5]:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата («комбинаторные методы нахождения нужного упорядочения объектов существенно отличаются от классических методов анализа поведения систем с помощью уравнений»^[6]);
имеет выраженный прикладной характер.

На протяжении более сотни лет развитие теории графов определялось в основном проблемой четырёх красок. Решение этой задачи в 1976 году оказалось поворотным моментом истории теории графов, после которого произошло её развитие как основы современной прикладной математики. Универсальность графов незаменима при проектировании и анализе коммуникационных сетей^[7].

Теория графов, как математическое орудие, приложима как к наукам о поведении (теории информации, кибернетике, теории игр, теории систем, транспортным сетям), так и к чисто абстрактным дисциплинам (теории множеств, теории матриц, теории групп и так далее)^[8]^[9].

Несмотря на разнообразные, усложнённые, малопонятные и специализированные термины многие модельные (схемные, структурные) и конфигурационные проблемы переформулируются на языке теории графов, что позволяет значительно проще выявить их концептуальные трудности^[10]. В разных областях знаний понятие «граф» может встречаться под следующими названиями:

и так далее^[11].

Первые использования и открытия графов

Теория графов как раздел прикладной математики «открывалась» несколько раз. Ключ к пониманию теории графов и её комбинаторной сущности отражены в словах Джеймса Сильвестра: «Теория отростков (англ. ramification) — одна из теорий чистого обобщения, для неё не существенны ни размеры, ни положение объекта; в ней используются геометрические линии, но они относятся к делу не больше, чем такие же линии в генеалогических таблицах помогают объяснять законы воспроизведения»^[12].

Первое использование диаграммы графа в науке

Дерево Порфирия

Диаграмма одной из разновидностей графа — дерева — использовалась издавна (конечно, без понимания, что это «граф»). Генеалогическое древо применялось для наглядного представления родственных связей. Но только античный комментатор работ Аристотеля финикийский философ и математик Порфирий использовал изображение дерева в науке как иллюстрацию дихотомического деления в своей работе «Введение» (греч. Εἰσαγωγή, лат. Isagoge) для классификации философского понятия материи^[13].

Первое использование и «открытие» теории графов

Мультиграф задачи о кёнигсбергских мостах

Швейцарский, прусский и российский математик Леонард Эйлер в статье (на латинском языке, изданной Петербургской академией наук) о решении знаменитой задачи о кёнигсбергских мостах, датированной 1736 годом, первым применил идеи теории графов при доказательстве некоторых утверждений. При этом Эйлер не использовал ни сам термин «граф», ни какие-либо термины теории графов, ни изображения графов^[14]. Леонард Эйлер считается отцом теории графов (как и топологии), открывшим понятие графа^[15], а 1736 год назначен годом рождения теории графов^[16].

Второе «открытие» графов

В 1847 году немецкий физик Густав Кирхгоф фактически разработал теорию деревьев при решении системы уравнений для нахождения величины силы тока в каждом контуре электрической цепи. Кирхгоф фактически изучал вместо электрической цепи соответствующий ей граф и показал, что для решения системы уравнений нет необходимости анализировать каждый цикл графа, достаточно рассмотреть только независимые циклы, определяемые любым остовным деревом графа^[15].

Пример электрической цепи, соответствующего ей графа и остовного дерева
Электрическая цепь 'N
Граф G, соответствующий электрической цепи
Остовое дерево T графа G

Третье «открытие» графов

В 1857 году английский математик Артур Кэли, занимаясь практическими задачами органической химии, открыл важный класс графов — деревья. Кэли пытался перечислить химические изомеры предельных (насыщенных) углеводородов C_nH_2n+2 с фиксированным числом n атомов углерода^[15].

Первые четыре линейных алкана (насыщенных углеводорода)
Метан CH₄
Этан C₂H₆
Пропан C₃H₈
Бутан C₄H₁₀

Четвёртое «открытие» графов

В 1859 году ирландский математик сэр Уильям Гамильтон придумал игру «Вокруг света». В этой игре использовался додекаэдр, каждая из 20 вершин которого соответствовала известному городу. От играющего требовалось обойти «вокруг света», то есть пройти по рёбрам додекаэдра так, чтобы пройти через каждую вершину ровно один раз^[15].

Игра Гамильтона «Вокруг света»
Обход вершин додекаэдра на многограннике
Обход вершин на проекции додекаэдра на плоскость

Пятое «открытие» графов

В 1869 году, независимо от Артура Кэли, французский математик Камиль Жордан (в частности, в статье « Sur les assemblages de lignes ») придумал и исследовал деревья в рамках чистой математики. При этом Жордан использовал термины теории графов «вершина» (фр. sommet) и «ребро» (фр. arête), но вместо термина «граф» было «соединение рёбер» (фр. assemblage d’arêtes) или просто «соединение» (фр. assemblage). Рисунки Жордан не использовал^[17]. При этом Жордан не подозревал о значении своего открытия для органической химии^[15].

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.

— M. Camille Jordan. Sur les assemblages de lignes)^[17]

Возникновение слова «граф»

Первое появление слова «граф» в смысле теории графов состоялось в 1878 году в краткой заметке (на английском языке) английского математика Джеймса Сильвестра в журнале Nature и имеет графическое происхождение как обобщение понятий «диаграмма Кекуле» и «химикограф»^[18]^[19].

Every invariant and covariant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph.

— Silvester J. J. Chemistry and algebra (italics as in the original)^[20]

В переводе:

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

— Сильвестр Дж. Дж. Химия и алгебра, 1878 (курсив оригинала)

Начало систематического использования слова «граф» и диаграмм графов

Денеш Кёниг

Псевдограф домино (28 костей)

Мы привычно рисуем точки, изображающие людей, населённые пункты, химические молекулы и т. д., и соединяем эти точки линиями, означающими отношения. Это социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т. д. В начале XX века венгерский математик Денеш Кёниг первый предложил называть эти схемы «графами» и изучать их общие свойства^[8]. В 1936 году вышла первая в мире книга по теории графов (на немецком языке) Денеша Кёнига «Теория конечных и бесконечных графов» с большей частью результатов за прошедшие 200 лет, начиная с 1736 года — даты выхода первой статьи Леонарда Эйлера по теории графов с решением задачи о кёнигсбергских мостах^[16]. В частности, в книге Кёнига имеется общий параграф для задачи о кёнигсбергских мостах и задаче о домино (построение замкнутой цепи из всех костей домино по правилам игры)^[21]^[22].

История возникновения теории графов

Теория графов (другими словами, системы линий, соединяющих заданные точки) очень удобна для начинающих^[3]:

имеет геометрическую наглядность;
имеет математическую содержательность;
не имеет громоздкого математического аппарата.

«Как и теория чисел, теория графов концептуально проста, но порождает сложные нерешенные проблемы. Как и геометрия, она визуально приятна. Эти два аспекта, наряду с их разнообразными приложениями, делают теорию графов идеальным предметом для включения в учебные программы по математике»^[5].

Возникновение этого раздела математики в XVIII веке связано с математическими головоломками. Достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играх^[3].

Краткая хронология событий развития теории графов^[23]
Год	Событие
1735	Представление Эйлером статьи по теории графов в Петербургской академии наук
1736	Год, считающийся годом рождения теории графов
1741	Публикация (датированная 1736 годом) статьи Эйлера по теории графов в Петербургской академии наук
1852	Френсис Гатри сообщает о проблеме четырёх красок Августу де Моргану
1879	Историческая публикация 1879 года с объяснением проблемы четырёх красок Артура Кэли
1879	Ошибочное «доказательство» проблемы четырёх красок Альфредом Кемпе
1890	Перси Джон Хивуд обнаружил ошибку в «доказательстве» Кемпе, доказал, что теорема верна, если «четыре» заменить на «пять», обобщил понятие «карты страны» с плоскости на замкнутые поверхности и сформулировал гипотезу Хивуда
1927	Лев Семёнович Понтрягин доказал (но не опубликовал) теорему Понтрягина — Куратовского
1930	Казимеж Куратовский опубликовал (независимо о Понтрягина) теорему Понтрягина — Куратовского
1936	Вышла первая в мире книга по теории графов Денеша Кёнига «Теория конечных и бесконечных графов»
1968	Группа математиков из разных стран доказала гипотезу Хивуда
1976	Группа математиков осуществили первое компьютерное доказательство теоремы о четырёх красках
1977	Фрэнк Харари основал журнал «Теория графов»

Геометрия положения

Отцом теории графов (как и топологии) считается швейцарский математик и механик Леонард Эйлер (1707—1783)^[12], написавший статью с решением задачи о кёнигсбергских мостах. Эйлер писал^[24]:

В дополнение к той ветви геометрии, которая занимается величинами и которой всегда уделялось самое большое внимание, существует другая ветвь, прежде почти неизвестная, о которой впервые упоминал Лейбниц, назвав ее геометрией положения [geometria situs]. Эта ветвь занимается только определением положения и его свойствами, она не включает ни измерений, ни вычислений, с ними связанных...

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

Далее Эйлер пишет, что не ясно, какие задачи и методы их решения относятся к геометрии положения. Тем не менее, Эйлер считал кёнигсбергские мосты именно такой задачей, о чём говорит и заголовок статьи. В действительности, Готфрид Лейбниц не позже 1679 года написал в письме к Христиану Гюйгенсу^[24]:

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

Лейбниц, введя термин analysis situs (анализ положения), не заложил основы новой математической дисциплины, но указал направление будущих исследований^[24].

Задача о кёнигсбергских мостах

Публикация статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения» о решении задачи о кёнигсбергских мостах имеет следующую историю:

26 августа (6 сентября) 1735 года^[25] Эйлер представил статью на Конференции Петербургской академии наук^[16];
в 1736 году Эйлер отправил два письма:

13 (24) марта 1736 года — письмо Иоганну Якобу Маринони^[de], австрийскому астроному и математику, которое целиком посвящено задаче о кёнигсбергских мостах^[26];
3 (14) апреля 1736 года — письмо Карлу Леонарду Готлибу Элеру^[de], немецкому политическому деятелю и астроному, в конце которого идёт речь об основных идеях статьи^[26];

в 1741 году в Санкт-Петербурге, наконец, вышла статья Эйлера на латинском языке с датой 1736 года^[26]:

Leonhardi Euleri. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140.

В переводе^[27]:

Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140.

Поскольку выход статьи Эйлера из печати датируется 1736 годом (и обоих писем тоже), этот год назначен датой рождения теории графов^[16].

Эйлер в своей статье так сформулировал задачу о семи кёнигсбергских мостах^[27]:

В городе Кенигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, Ь, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

В конце статьи Эйлер записал выводы вполне современным языком^[28]:

20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:
Если имеется более двух областей, в которые ведёт нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.
Если, однако, имеются только две области, в которые ведёт нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей.
Если, наконец, нет ни одной области, в которую ведёт нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.
Следовательно, с помощью этого правила поставленная задача может быть полностью решена.

— Леонард Эйлер. Решение одной задачи, связанной с геометрией положения

Теорема о четырёх красках

Теорема о четырёх красках — наиболее известное утверждение в теории графов (а может, и во всей математике), долгое время не поддающееся доказательству (а может, так и не доказанное). Эту легендарную задачу в течение пяти минут может объяснить любой математик любому прохожему, после чего оба, понимая проблему, решить её не смогут. Следующая цитата из ставшей исторической статьи 1965 года американского математика Кеннет О. Мэй^[en]^[29]:

[Предполагается, что] любую карту на плоскости или поверхности шара можно раскрасить только четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Каждая страна должна состоять из одной связной области, а смежными называются страны, которые имеют общую границу в виде линии (а не просто одной общей точки). Эта гипотеза тесно связана с наиболее модными направлениями теории графов, а в разделе математики, называемом комбинаторной топологией, она действовала подобно катализатору. На протяжении более чем половины столетия многие математики (кое-кто говорит, что все) предпринимали попытки решить эту проблему, но смогли доказать справедливость гипотезы только для отдельных случаев... Единодушно признается, что гипотеза справедлива, но маловероятно, что она будет доказана в общем случае. Кажется, что ей на некоторое время предназначено сохранить отличительную черту быть одновременно и наиболее простой, и наиболее заманчивой нерешённой проблемой математики.

— May K. O. The origin of the four-color conjecture / Isis. 56 (1965). P. 346—348

Карта стран и соответствующий ей граф

Теорема о четырёх красках относится к теории графов, так как каждая карта порождает граф следующим образом:

страны (включая внешнюю область) — это вершины;
вершины смежных стран соединяются ребром.

Этот граф рисуется на плоскости без пересечения рёбер. Теорема о четырёх красках доказана, если доказано, что вершины любого подобного графа можно раскрасить четырьмя красками так, чтобы смежные вершины имели разные цвета^[30].

Теорема о четырёх красках имеет легендарную историю, интересную и иногда непонятную^[29]^[31]:

имеются неподтверждённые сообщения, что Августу Мёбиусу эта проблема была известна в 1840 году;
точно известно, что Френсис Гатри^[en], южноафриканский математик и ботаник, 23 октября 1852 года сообщил шотландскому математику и логику Августу де Моргану о данной проблеме, после чего велись обсуждения в узких кругах математиков и дилетантов;
историческая публикация 1879 года с объяснением проблемы

Cayley Arthur. On the Colouring of Maps // Proceedings of the Royal Geographical Society. 1879. Vol. 1, No. 4. P. 259–261

принадлежит Артуру Кэли, английскому математику. Теперь проблема приобретает большую известность;

в том же 1879 году вышла публикация ошибочного «доказательства» проблемы

Kempe A. B. On the Geographical Problem of the Four Colours // American Journal of Mathematics. 1879. Vol. 2, No. 3. P. 193–200

английского церковного юриста и любителя математики Альфреда Кемпе^[en]. Это было не только первое из многих ошибочных «доказательств», но и самое «правильное»: на основе идей этой статьи удалось сначала доказать, что пяти красок хватит, а затем провести полное компьютерное доказательство теоремы о четырёх красках;

ошибку в «доказательстве» Кемпе через 11 лет в 1890 году обнаружил английский математик Перси Джон Хивуд, и в опубликованной по этому поводу статье

Heawood P. J. Map colour theorems //Quarterly Journal of Pure and Applied Mathematics. 24 (1890). P. 332—338

также доказал, что теорема верна, если «четыре» заменить на «пять», и, кроме того, обобщил понятие «карты страны» с плоскости на замкнутые поверхности и сформулировал гипотезу Хивуда;

в 1968 году группа математиков из разных стран доказала гипотезу Хивуда;
в 1976 году американские математики осуществили первое компьютерное доказательство теоремы о четырёх красках.

Теорема Понтрягина — Куратовского

Теория графов содержит топологические аспекты. Первым результатом в этом направлении является формула Эйлера в теории графов, полученная им в 1736 году. Следующий результат в виде теоремы Понтрягина — Куратовского был получен только через 191 год: в 1927 году советский математик Лев Семёнович Понтрягин доказал (но не опубликовал) этот результат, а в 1930 году польский математик Казимеж Куратовский опубликовал его (независимо от Понтрягина). Теорему Понтрягина — Куратовского также называют критерием Понтрягина — Куратовского^[32]:

Планарный граф — это граф, который можно нарисовать на плоскости без пересечения рёбер. Граф, который нельзя так нарисовать, называется непланарным. Ниже показаны два важных непланарных графа, обозначаемых [math]\displaystyle{ K_5 }[/math] и [math]\displaystyle{ K_{3,3} }[/math], их нельзя нарисовать на плоскости без пересечения рёбер. Эти два графа выделяются среди других тем, что только они используются в критерии Понтрягина — Куратовского^[33].

Легендарные непланарные графы
$Полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math]$

Полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math]
$Полный двудольный граф (3, 3) [math]\displaystyle{ K_{3,3} }[/math]$

Полный двудольный граф (3, 3) [math]\displaystyle{ K_{3,3} }[/math]

Доказательство без слов непланарности тессеракта. Вверху — тессеракт содержит [math]\displaystyle{ K_5 }[/math], внизу — [math]\displaystyle{ K_{3,3} }[/math]

До появления критерия Понтрягина — Куратовского доказательство планарности или непланарности графов было очень сложной проблемой теории графов^[33].

Теорема Понтрягина — Куратовского. Граф планарен тогда и только тогда, когда он ни в каком виде не содержит графов [math]\displaystyle{ K_5 }[/math] и [math]\displaystyle{ K_{3,3} }[/math].

Справа приведены два простых доказательства без слов того, что остов четырёхмерного гиперкуба (тессеракта) как граф непланарен. На верхнем рисунке показано, что в тессеракте содержится полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math], на нижнем — полный двудольный граф (3, 3) [math]\displaystyle{ K_{3,3} }[/math].

Основные легендарные издания

Один из отцов современной теории графов Фрэнк Харари

Ранняя теория графов — теория графов до 1936 года, до выхода книги Кёнига^[24].

В 1936 году вышла первая в мире книга по теории графов венгерского математика Денеша Кёнига «Теория конечных и бесконечных графов» на немецком языке:

Kőnig, Dénes. Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaf, 1936.

Эта книга состояла из 248 страниц (без учёта предисловия, оглавления и библиографии) и большей части результатов теории графов за 200 лет — с даты выхода статьи Леонарда Эйлера с решением задачи о кёнигсбергских мостах^[16].

Современная теория графов — теории графов, начиная с 1936 года, с момента выхода книги Кёнига. С времени выхода книги Кёнига, но в основном с конца Второй мировой войны, теория графов начала ускоренно развиваться. Этот рост заключался не только в увеличении числа книг по теории графов, но и в том, что развились специальные аспекты теории графов^[16]:

Один из отцов современной теории графов — Фрэнк Харари, который в 1977 году основал журнал «Теория графов»^[en]^[34]^[16].

Книга Фрэнка Харари «Теория графов» стала классической де-факто^[35]^[36].

Книга Рейнгарда Дистеля «Теория графов» (выдержала 5 редакций) не имеет конкурентов в русскоязычной библиографии. Этот канон вводного курса в теорию графов инициировал отождествление некоторых областей обучения и исследования^[2]^[37].

Описание ранней теории графов

Ранняя теория графов продолжалась ровно 200 лет, от первой статьи по теории графов Леонарда Эйлера 1736 года до первой книги по теории графов Денеша Кёнига 1936 года. В предисловии к книге написано, что изложение теории графов ограничивается областью абсолютных графов (абстрактных графов в современной терминологии), а относительная теория графов (топологическая теория графов в современной терминологии) и перечислительная теория графов не рассматриваются. Ниже приведено полное название книги Денеша Кёнига и её краткое оглавление, состоящее из названий глав^[16]^[38]^[39].

Теория конечных и бесконечных графов. Комбинаторная топология одномерных комплексов (нем. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe, англ. Theory of finite and infinite graphs).

Глава I. Основы (нем. die Grundlahen, англ. foundations).

Глава II. Эйлеровы и гамильтоновы обходы (нем. Eulersche und Hamiltonsche Linien, англ. Euler trails and Hamiltonian cycles).

Глава III. Задача о лабиринте (нем. das Labyrinthenproblem, англ. the Labyrinth Problem).

Глава IV. Ациклические графы (нем. kreislose Graphen, англ. acyclic graphs).

Глава V. Центры деревьев (нем. Zentren der Bäume, англ. centers of trees).

Глава VI. Специальные методы исследования бесконечных графов (нем. Spezielle Untersuchungen über unendliche Graphen, англ. infinite graphs).

Глава VII. Основные задачи ориентированных графов (нем. Basisprobleme für gerichtete Graphen, англ. basis problems for directed graphs).

Глава VIII. Некоторые приложения ориентированных графов (логика — теория игр — теория групп) (нем. Verschiedene Anwendungen der gerichteten Graphen (Logik — Theorie der Spiele — Gruppentheorie), англ. various applications of directed graphs (logic – theory of games – group theory)).

Глава IX. Циклы, звёзды и соответствующие линейные формы (нем. Zyklen und Büschel und die entsprechenden linearen Formen, англ. (directed) cycles and stars and the corresponding linear forms).

Глава X. Композиция циклов и звёзд (нем. Komposition der Kreise und der Büschel, англ. composition of cycles and stars).

Глава XI. Факторизация регулярных конечных графов (нем. Faktorenzerlegung regulärer endlicher Graphen, англ. factorization of regular finite graphs).

Глава XII. Факторизация регулярных конечных графов третьей степени (нем. Faktorenzerlegung regulärer endlicher Graphen dritten Grades, англ. factorization of regular finite graphs of degree 3).

Глава XIII. Факторизация регулярных бесконечных графов (нем. Faktorenzerlegung regulärer unendlicher Graphen, англ. factorization of regular infinite graphs).

Глава XIV. Разделяющие вершины и множества вершин (нем. trennende Knotenpunkte und Knotenpunktmengen, англ. separating vertices and sets vertices).

Проблемы представления теории графов

Проблемы терминологии

Обычно упоминаемый факт пестроты и неупорядоченности терминологии и обозначений в теории графов — частично следствие того, что этой наукой интересуются специалисты из весьма разнообразных областей знания^[40]. Кроме того, в терминологии самой теории графов имеется некоторый люфт, немного затрудняющий изучение и представление теории графов. С особой осторожностью приходится применять такие понятия, как «маршрут», «путь» и «цепь», которые, означая почти одно и то же, могут принимать разные конкретные значения у разных авторов^[36].

Вот что писал в начале своей классической книги Фрэнк Харари (переизданной в 2003 году)^[41]^[42].

Большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою собственную терминологию. На конференциях по теории графов каждый выступающий, чтобы избежать неправильного понимания, считает необходимым определить прежде всего язык, которым он будет пользоваться. Даже само слово «граф» не является священным. Некоторые авторы действительно определяют «граф» как граф, другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть. Нам кажется, что единообразие в терминологии теории графов никогда
не будет достигнуто, но, может быть, оно и ни к чему.
— Харари Фрэнк. Теория графов, 2003

Наиболее радикален взгляд с позиций конструктивной математики^[43]^[44].

…нам кажется не слишком важным, как назвать точки, соединённые линиями: «графом», «орграфом», «мультиграфом», «псевдографом». Графы, построенные на основе реальных структур, слишком разнообразны, чтобы их классифицировать по тем признакам, о которых говорили родоначальники этой науки. Нас гложет сомнение: нужно ли вообще различать такие понятия, как «ребро» — «дуга», «контур» — «цикл», «путь» — «маршрут», «центр» — «центроид» и т. д. Ведь на практике (а графы в основном имеют прикладное значение) все эти ряды терминов забываются и заменяются каки-либо одним словом: «граф», «ребро», «цикл», «путь», «центр». Информатику трудно понять, почему граф с петлёй уже не является полноценным графом, а только «псевдографом». …Разве информатик или кто-либо другой из специалистов не в состоянии сам решить, каким словом ему пользоваться — «путь» или «маршрут», — и через какие буквы его маршрут-путь лучше обозначить? Граф — это наглядный образ, достоинство которого как раз и состоит в том, что он требует минимума слов и символов.

— Акимов О. Е. Дискретная математика: логика, группы, графы, 2003

Программисты тоже вносят свою лепту в разброс терминологии^[45].

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

— Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов, 1981

Но в изданиях последних лет речь идёт уже о «в основном стандартной» терминологии^[46]^[47].

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

— Дистель Р. Теория графов, 2002. Reinhard Diestel. Graph Theory, 2016

Например, в фундаментальном труде в области кибернетики «Алгоритмы: построение и анализ» используется стандартная терминология^[48].

При описании времени работы алгоритма над данным графом [math]\displaystyle{ G = (V, E) }[/math] мы обычно определяем размер входного графа в терминах количества его вершин [math]\displaystyle{ |V| }[/math] и количества рёбер [math]\displaystyle{ |E| }[/math] графа, т. е. размер входных данных описываем двумя, а не одним параметром.

— Кормен Т. Х. и др. Алгоритмы: построение и анализ, 2009

Проблемы рисования графов

Абстрактные графы можно изображать на плоскости по-разному. Вопрос о том, изоморфны ли данные изображения графов, то есть изоморфны ли данные изображения графов одному абстрактному графу, может быть нетривиальным. Иногда этот вопрос решается просто. Например, следующие два графа неизоморфны, поскольку они имеют разное число вершин^[49].

Неизоморфные графы: разное число вершин
Три вершины
Четыре вершины

Следующие два графа также неизоморфны, поскольку они имеют разное число рёбер^[49].

Неизоморфные графы: разное число рёбер
Пять рёбер
Шесть рёбер

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

1-2-3-4-8-7-6-5-1,

а второй граф не имеет. То есть при любой нумерации вершин второго графа нельзя получить на нём гамильтонов цикл, соответствующий гамильтонову циклу первого графа^[49].

Неизоморфные графы: разные обходы вершин
Есть гамильтонов цикл
Нет гамильтонова цикла

Если сразу не ясно, как доказать неизоморфность графов, то вопрос о наличии изоморфизма может оказаться труден. Два следующих изоморфных графа на первый взгляд неизоморфны^[49].

Изоморфные графы, кажущиеся неизоморфными
$Циркулянтный граф [math]\displaystyle{ C_7(1,2) }[/math]$

Циркулянтный граф [math]\displaystyle{ C_7(1,2) }[/math]
$Циркулянтный граф [math]\displaystyle{ C_7(1,3) }[/math]$

Циркулянтный граф [math]\displaystyle{ C_7(1,3) }[/math]

Проблемы литературы

На какие источники лучше ориентироваться, представляя теорию графов? Вот отзывы о некоторых книгах.

Харари Фрэнк. Теория графов, 2003.

Книга Фрэнка Харари стала классической де-факто^[35]^[36].

Прошло 30 лет после выпуска монографии Ф. Харари «Теория графов», но её привлекательные качества нисколько не потускнели. Унификация терминологии, проведённой автором и широко распространенной благодаря этой книге, стала общепринятой. Преподавание теории графов с использованием книги Ф. Харари ведется во многих вузах нашей страны.

— Предисловие В. П. Козырева (2002) к книге: Харари Фрэнк. Теория графов, 2003

В книге Герберта Фляйшнера «Эйлеровы графы и смежные вопросы» приведён список книг, рекомендуемых в качестве введения в теорию графов. Это книги на английском языке, из которых только первая переведена на русский: это книга Фрэнка Харари «Теория графов»^[50].

Дистель Р. Теория графов, 2002.

Книга Рейнгарда Дистеля «Теория графов» (выдержала 5 редакций) не имеет конкурентов в русскоязычной библиографии. Этот канон вводного курса в теорию графов инициировал отождествление некоторых областей обучения и исследования^[2]^[37].

…сейчас хватает переводов на русский язык учебников по теории графов, в первую очередь замечательной книги Дистеля. И, увы, только книги Дистеля.
…Именно работа над переводом 5-го издания книги Дистеля стимулировала продолжение работы над моей книгой в 2017 году после долгого перерыва. Я заметил, насколько велика «симметрическая разность» его книги и моей.

— Карпов Д. В. Теория графов. 2017 или позже

Классификация теории графов

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

Теория графов^[16]:

абстрактные графы («обычные» графы);
топологическая теория графов;
перечисление графов;
алгебраическая теория графов;
алгоритмическая теория графов.

Теория графов^[51]:

элементарно-комбинаторная теория графов;
логическая теория графов;
алгебраическая теория графов;
матроиды;
рекуррентные свойства графов;
случайные графы;
бесконечные графы.

Аналитическая теория графов^[52]:

Основные термины теории графов

Теория графов, как и любая современная математическая модель, использует стенографические символы, экономящие мышление и делающие математическую модель гибкой и эффективной^[53].

Здесь деликатно и сжато приведены первые термины основной части теории графов. Большинство стандартных терминов настолько наглядны, что легко усваиваются. Необходимо достаточно строго определить ряд понятий, чтобы в дальнейшем иметь возможность их широко использовать^[41]^[54]^[55].

Графы (англ. graphs)

Краткая, но представительная сводка основных определений теории графов, примыкающих к понятию собственно графа. Эти понятия вводятся одно за другим достаточно систематически, хотя и несколько утомительно^[56]^[57]^[58].

Граф — это два конечных непересекающихся множества, причём второе состоит из 2-элементных подмножеств первого. Обозначение: [math]\displaystyle{ G = (V, E) }[/math]^[59], где [math]\displaystyle{ E \subseteq V \times V }[/math] и [math]\displaystyle{ V \cap E = \varnothing }[/math].

Вершина графа (узел, точка) — это элемент множества [math]\displaystyle{ V }[/math] графа. Обозначение: [math]\displaystyle{ v \in V(G) }[/math].

Ребро графа (линия, дуга) — это элемент множества [math]\displaystyle{ E }[/math] графа. Обозначение: [math]\displaystyle{ e \in E(G) }[/math].

Ребро в старых изданиях могли также назвать ветвью, звеном^[60] или кривой^[61].

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

Порядок графа — это число вершин графа [math]\displaystyle{ G }[/math]. Обозначение: [math]\displaystyle{ |G| }[/math]. Число рёбер графа обозначается [math]\displaystyle{ \|G\| }[/math].

Пустой граф — это граф без вершин. Обозначение: [math]\displaystyle{ G (\varnothing, \varnothing) \equiv \varnothing }[/math].

Тривиальный граф — это граф порядка 0 или 1.

Примеры графов
Слева направо: граф порядка 1, граф порядка 2 с 1 ребром, граф порядка 4 с 4 рёбрами, граф порядка 8 с 12 рёбрами

Концевые вершины, или концы, ребра — это две вершины, которые определяют ребро. Ребро соединяет свои концевые вершины. Ребро и его концевая вершина инцидентны, или одно находится при другом. Множество всех рёбер при вершине [math]\displaystyle{ v \in V(G) }[/math] обозначается [math]\displaystyle{ E(v) }[/math].

Смежные, или соседние, вершины — это две вершины, инцидентные одному ребру.

Смежные рёбра — это рёбра, которые имеют общий конец.

Полный граф — это граф, все вершины которого попарно смежны, то есть любые две вершины соединены ребром. Обозначение полного графа с [math]\displaystyle{ n }[/math] вершинами: [math]\displaystyle{ K_n }[/math]^[62] (иногда [math]\displaystyle{ K^n }[/math]). Граф [math]\displaystyle{ K_3 }[/math] называется треугольником.

Примеры полных графов
Первые пять полных графов

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

концы любого ребра принадлежат разным подмножествам разбиения;
вершины в каждом подмножестве разбиения попарно несмежны.

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

Обозначение полного двудольного графа с числом вершин в подмножествах разбиения [math]\displaystyle{ n }[/math] и [math]\displaystyle{ m }[/math]: [math]\displaystyle{ K_{n, m} }[/math]^[62].

Различные диаграммы полного двудольного графа (3, 3)
$Граф [math]\displaystyle{ K_{3, 3} }[/math]$

Граф [math]\displaystyle{ K_{3, 3} }[/math]
$Граф [math]\displaystyle{ K_{3, 3} }[/math]$

Граф [math]\displaystyle{ K_{3, 3} }[/math]
$Граф [math]\displaystyle{ K_{3, 3} }[/math]$

Граф [math]\displaystyle{ K_{3, 3} }[/math]
$Граф [math]\displaystyle{ K_{3, 3} }[/math]$

Граф [math]\displaystyle{ K_{3, 3} }[/math]

Степень, или валентность, вершины графа — это число рёбер, инцидентных вершине. Обозначение степени вершины [math]\displaystyle{ v }[/math]: [math]\displaystyle{ \deg v \equiv d(v) }[/math]^[63].

Изолированная вершина графа — это вершина с нулевой степенью.

Концевая, или висячая, вершина графа — это вершина с первой степенью.

Минимальная степень вершин графа [math]\displaystyle{ G }[/math] обозначается через [math]\displaystyle{ \min \deg G \equiv \delta(G) }[/math], максимальная степень — [math]\displaystyle{ \max \deg G \equiv \Delta(G) }[/math].

Регулярный, или однородный граф — это граф, все вершины которого имеют одну и ту же степень. Другими словами, для такого графа [math]\displaystyle{ G }[/math] его степени [math]\displaystyle{ \delta(G) = \Delta(G) }[/math].

r-регулярный, или r-однородный, граф — это граф [math]\displaystyle{ G }[/math] с [math]\displaystyle{ \delta(G) = \Delta(G) = r }[/math]. Такие графы называются также просто регулярными, или однородными. 3-регулярный граф называется кубическим.

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

Теорема. Сумма степеней вершин графа равна удвоенному числу его рёбер.

Следствие 1. В любом графе число вершин с нечётными степенями чётно.

Следствие 2. Любой кубический граф имеет чётное число вершин.

Пример регулярных графов
Кубический граф с 4 вершинами
4-регулярный граф с 6 вершинами
5-регулярный граф с 12 вершинами

Типы графов (англ. types of graphs)

Продолжение краткой, но представительной сводки основных теоретико-графовых определений, примыкающих к понятию графа. Для полноты перечислим ряд разновидностей графов^[64]^[65]^[66].

Изоморфизм двух графов — это взаимно-однозначное соответствие между множествами их вершин, сохраняющее смежность. Обозначение: [math]\displaystyle{ G \simeq H }[/math].

Ясно, что изоморфизм — это отношение эквивалентности на графах.

Обычно изоморфные графы не различают и пишут [math]\displaystyle{ G = H }[/math] вместо [math]\displaystyle{ G \simeq H }[/math], понятие изоморфизма широко используется при изображениях графов.

Инвариант графа — это число, которое принимает одно и то же значение на изоморфных графах.

Полный набор инвариантов определяет граф с точностью до изоморфизма. Например, число вершин и число рёбер графа — полный набор инвариантов для любого графа с числом вершин, не большим 3.

Пример изоморфных графов
$Диаграмма [math]\displaystyle{ K_4 }[/math] с пересечением вершин$

Диаграмма [math]\displaystyle{ K_4 }[/math] с пересечением вершин
$Диаграмма [math]\displaystyle{ K_4 }[/math] без пересечения вершин$

Диаграмма [math]\displaystyle{ K_4 }[/math] без пересечения вершин

Подграф графа — это граф, все вершины и рёбра которого принадлежат исходному графу. Исходный граф — это надграф своего подграфа. Другими словами, граф [math]\displaystyle{ G }[/math] содержит граф [math]\displaystyle{ G' }[/math]: [math]\displaystyle{ G \subseteq G' }[/math].

Óстовный подграф графа — это подграф, содержащий все вершины своего надграфа.

Порождённый, или индуцированный, подграф графа — это подграф, содержащий все рёбра надграфа для множества своих вершин, то есть две вершины порождённого подграфа смежны тогда и только тогда, когда они смежны в надграфе.

Пример графа и подграфов
Исходный граф
Óстовный, но не порождённый подграф
Порождённый, но не о́стовный подграф

Мультиграф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит из 2-элементных подмножеств множества. Обозначение: [math]\displaystyle{ G = (V, E) }[/math]^[67], где любой элемент [math]\displaystyle{ e \in E }[/math] мультимножества [math]\displaystyle{ e \in V \times V }[/math] и [math]\displaystyle{ V \cap E = \varnothing }[/math].

В мультиграфе пара вершин может быть соединена более чем одним ребром.

Кратные рёбра — это рёбра, соединяющие одну и ту же пару вершин.

Другими словами, мультиграф — это граф с кратными рёбрами, а граф — это мультиграф без кратных рёбер.

Простой, или обыкновенный, граф — это граф без кратных рёбер, если графом назвать мультиграф.

Псевдограф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит как из 1-элементных, так и из 2-элементных подмножеств множества. Обозначение: [math]\displaystyle{ G = (V, E) }[/math], где мультимножество [math]\displaystyle{ E \subseteq V \cup (V \times V) }[/math] и [math]\displaystyle{ V \cap E = \varnothing }[/math].

В псевдографе ребро может соединять вершину саму с собой.

Петля— это ребро, у которого концевые вершины совпадают.

Иногда псевдограф называют мультиграфом.

Гиперграф — это конечные непересекающиеся множество и мультимножество, причём мультимножество состоит из любых подмножеств множества. Обозначение: [math]\displaystyle{ G = (V, E) }[/math], где любой элемент [math]\displaystyle{ e \in E }[/math] мультимножества принадлежит булеану: [math]\displaystyle{ e \in P(V) }[/math], и [math]\displaystyle{ V \cap E = \varnothing }[/math].

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

Ориентированный граф, или орграф — это псевдограф, рёбра которого ориентированы, то есть имеют начальную вершину и концевую вершину. Обозначение: [math]\displaystyle{ D = (V, E) }[/math]^[68], где мультимножество [math]\displaystyle{ E }[/math] состоит из упорядоченных пар [math]\displaystyle{ v, u \in V }[/math] и [math]\displaystyle{ V \cap E = \varnothing }[/math].

Ориентированное ребро, или дуга — это ребро орграфа.

Примеры видов графов
Мультиграф задачи о Кёнигсбергских мостах
Псевдограф
$Гиперграф [math]\displaystyle{ V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\} }[/math], [math]\displaystyle{ E = \{e_1,e_2,e_3,e_4\} = }[/math][math]\displaystyle{ = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, }[/math][math]\displaystyle{ \{v_3,v_5,v_6\}, \{v_4\}\} }[/math]$

Гиперграф [math]\displaystyle{ V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\} }[/math], [math]\displaystyle{ E = \{e_1,e_2,e_3,e_4\} = }[/math][math]\displaystyle{ = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, }[/math][math]\displaystyle{ \{v_3,v_5,v_6\}, \{v_4\}\} }[/math]
Орграф

Пути и связность (англ. paths and connectivity)

Свойство графа, считающееся одним из самых простых и в то же время основных, это свойство связности. Здесь представлен ближайший круг понятий этого свойства связности^[69]^[70]^[71].

Путь, или простой путь, в графе — это подграф, представляющий собой последовательность различных вершин, в которой каждая вершина соединена со следующей ребром. Обозначение пути (англ. path): [math]\displaystyle{ P = (V, E) }[/math], где

[math]\displaystyle{ V = \{x_0, x_1, x_2, \dots, x_k\} }[/math], [math]\displaystyle{ E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k\} }[/math],

все [math]\displaystyle{ x_i }[/math] различны.

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

Концевые вершины, или концы, пути — это вершины [math]\displaystyle{ x_0 }[/math] и [math]\displaystyle{ x_k }[/math]. Вершины [math]\displaystyle{ x_0 }[/math] и [math]\displaystyle{ x_k }[/math] соединены путём [math]\displaystyle{ P }[/math].

Внутренние вершины пути — это вершины [math]\displaystyle{ x_1, x_2, \dots, x_{k-1} }[/math].

Длина пути — это число рёбер пути. Обозначение пути длиной [math]\displaystyle{ k }[/math]: [math]\displaystyle{ P_k }[/math].

Цикл, или простой цикл, в графе — это подграф, представляющий собой замкнутую последовательность различных вершин, в которой каждая вершина соединена со следующей ребром. Обозначение цикла (англ. cycle): [math]\displaystyle{ C = (V, E) }[/math], где

[math]\displaystyle{ V = \{x_0, x_1, x_2, \dots, x_k, x_0\} }[/math], [math]\displaystyle{ E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k, x_kx_0\} }[/math],

все [math]\displaystyle{ x_i }[/math] различны.

Длина цикла — это число рёбер цикла. Обозначение цикла длиной [math]\displaystyle{ k }[/math]: [math]\displaystyle{ C_k }[/math].

Хорда цикла — это рёбро, которое не принадлежит циклу и соединяет две его вершины.

Теорема. Любой граф [math]\displaystyle{ G }[/math] с минимальной степенью вершин [math]\displaystyle{ \delta(G) \geqslant 2 }[/math] содержит цикл длины не менее [math]\displaystyle{ \delta(G) + 1 }[/math].

Пример путей
$Два пути [math]\displaystyle{ P_4 }[/math]: жёлтый и синий$

Два пути [math]\displaystyle{ P_4 }[/math]: жёлтый и синий
$Красный цикл [math]\displaystyle{ C_{12} }[/math]. Пунктирные рёбра — хорды цикла$

Красный цикл [math]\displaystyle{ C_{12} }[/math]. Пунктирные рёбра — хорды цикла

Связный граф — это граф, у которого две любые вершины соединены путём.

Компонента связности, или компонента, графа — это максимальный связный подграф графа.

Несвязный граф состоит по крайней мере из двух компонент связности.

Компонента, будучи связной, непуста; поэтому пустой граф не имеет компонент.

Пример связного и несвязного графов
Связный граф на 5 вершинах
Несвязный граф из 2 компонент на 5 вершинах

Разделяющая вершина, или точка сочленения графа — это вершина графа, при удалении которой число компонент связности графа увеличивается.

Мост графа — это ребро графа, при удалении которого число компонент связности графа увеличивается.

Конечные вершины моста — это разделяющие вершины.

Ясно, что мосты в графе — это те и только те рёбра, которые не принадлежат никакому циклу.

Неразделимый граф — это непустой связный граф без разделяющих вершин.

Примеры разделяющих вершин и моста
e — мост. Вершина a и концы моста — разделяющие вершины

Маршрут в графе — это подграф, представляющий собой последовательность вершин, в которой каждая вершина соединена со следующей ребром. Обозначение маршрута: [math]\displaystyle{ (V, E) }[/math], где

[math]\displaystyle{ V = \{x_0, x_1, x_2, \dots, x_k\} }[/math], [math]\displaystyle{ E = \{x_0x_1, x_1x_2, x_2x_3, \dots, x_{k-1}x_k\} }[/math].

В маршруте могут быть совпадающие рёбра и врешины.

Ясно, что если все вершины в маршруте различны, то это путь.

Маршрут замкнут, если [math]\displaystyle{ x_0 = x_k }[/math], иначе маршрут открыт.

Эйлеров цикл, или эйлеров обход, графа — это замкнутый маршрут в графе, который проходит по всем рёбрам графа ровно один раз.

Эйлеров граф — это граф, который имеет эйлеров цикл.

Ясно, что эйлеров граф связен.

Теорема (Эйлер, 1736). Связный граф Эйлеров тогда и только тогда, когда все вершины графа имеют чётную степень.

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

Примеры эйлеровых графов
$Полный граф [math]\displaystyle{ K_4 }[/math], никакой обход рёбер по одному разу невозможен$

Полный граф [math]\displaystyle{ K_4 }[/math], никакой обход рёбер по одному разу невозможен
Не эйлеров граф, имеющий открытый маршрут, проходящий по всем рёбрам ровно один раз
Эйлеров граф. Эйлеров цикл — обход рёбер в алфавитном порядке

Деревья (англ. trees)

Четыре семейства графов были представлены выше, это полные, двудольные, регулярные и эйлеровы графы. Ещё одно семейство графов в разных областях науки называется одинаково — деревья. Деревья находят приложения в различных областях знания и имеют особый статус в самой теории графов по причине предельной простоты их строения, и при решении задачи о графах её сначала могут исследовать на деревьях^[72]^[73]^[74].

Дерево

Лес — это граф без циклов.

Дерево — это связный лес. Обозначение дерева (англ. tree): [math]\displaystyle{ T }[/math].

Другими словами, лес — это граф, компоненты которого суть деревья.

Лист — это вершина степени 1 в дереве.

Любое нетривиальное дерево имеет по крайней мере два листа. При удалении листа остаётся снова дерево.

Теорема. Для графа следующие утверждения равносильны:

(i) граф — дерево;

(ii) каждые две вершины графа соединены единственным путём;

(iii) граф — минимальный связный, то есть граф связен и становится несвязным при удалении любого ребра;

(iv) граф — максимальный ациклический, то есть граф не имеет цикла и цикл возникает при соединении ребром любых двух несмежных вершин.

Следствие 1. Любой связный граф имеет остовное дерево.

Доказательство. Из равносильности условий (i) и (iii) теоремы следует, что любой минимальный остовный подграф — дерево.

Следствие 2. Связный [math]\displaystyle{ n }[/math]-вершинный граф — дерево тогда и только тогда, когда он имеет ровно [math]\displaystyle{ n - 1 }[/math] ребро.

Все деревья с 5 вершинами

Корневое дерево (дерево с выделенной вершиной)

Корень дерева — это фиксированная вершина дерева. Обозначение корня (англ. root): [math]\displaystyle{ r }[/math].

Корневое дерево — это дерево с корнем.

Древесный порядок — это частичный порядок на вершинах дерева, определяемый деревом и его корнем: для любых двух вершин [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] дерева [math]\displaystyle{ x \leqslant y }[/math], если [math]\displaystyle{ x }[/math] принадлежит пути с концами [math]\displaystyle{ r }[/math] и [math]\displaystyle{ y }[/math].

В древесном порядке:

корень дерева [math]\displaystyle{ r }[/math] — наименьший элемент;
любой лист дерева, отличный от корня, — наибольший элемент;
концы любого ребра дерева сравнимы.

Цепь, или линейно упорядоченное множество, — это частично упорядоченное множество, в котором любая пара элементов сравнима.

Теорема. Вершины пути на дереве с концами [math]\displaystyle{ r }[/math] и [math]\displaystyle{ y }[/math] образуют цепь, где [math]\displaystyle{ y }[/math] — любая фиксированная вершина дерева, отличная от корня [math]\displaystyle{ r }[/math].

Примеры цепей на корневом дереве
Дерево с корнем 3 и максимальными цепями 3-1-2, 3-7-6-5, 3-7-10

Динамика поиска в глубину на графе

Нормальное остовное дерево графа — это остовное корневое дерево графа такое, что любые две смежные вершины графа сравнимы.

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

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

На иллюстрации ниже показаны два возможных остовых дерева полного графа [math]\displaystyle{ K_4 }[/math]. Остовые деревья представлены жирными рёбрами. Левое остовное дерево — нормальное, если его корень — вершина A или D; при корнях B или C нормальности не получается, поскольку тогда концы ребра, например, A-D несравнимы. Правое остовное дерево не может быть нормальным при любом выборе его корня, всегда найдётся ребро с несравнимыми концами.

Два остовных дерева полного графа с 4 вершинами
Жирные рёбра — нормальное остовное дерево с корнем A или D
Жирные рёбра — остовное дерево, которое не может быть нормальным при любом выборе корня

Современное состояние теории графов

Современному состоянию теории графов отвечает стандартный учебник, сочетающий в себе классику и активнуюе математику и охватывающий основной материал предмета. Оглавление подобной книги даёт краткое представление о современном состоянии теории графов, из которого и состоит этот раздел^[75].

Паросочетания, покрытия и упаковка (англ. matching, covering and packing)

Как найти максимально возможное число независимых рёбер в графе? Можно ли все вершины графа разбить на пары? Ответы начинаются со следующих понятий^[76]^[77]^[78].

Паросочетание, или независимое множество рёбер в графе, — это множество рёбер графа, не имеющих общих вершин.

Паросочетания на графах (показаны красным цветом)
Паросочетание из двух рёбер
Паросочетание из трёх рёбер

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

Покрытия вершин графов паросочетаниями (показаны красным цветом)
Паросочетание покрывает 8 вершин графа из 9
Паросочетание покрывает все 8 вершин графа

Теорема о свадьбах

Теорема о свадьбах (Холл, 1935). Двудольный граф содержит паросочетание, покрывающее одну из долей, тогда и только тогда, когда любое число вершин этой доли связаны с не меньшим числом вершин другой доли.

Граф можно разбить (или в граф можно упаковать, или граф можно покрыть, или разложить) на несколько остовных деревьев или остовных лесов, не имеющих общих рёбер.

Древесность — это минимальное число лесов, на которые можно разбить граф.

Например, граф [math]\displaystyle{ K_5 }[/math] имеет 5 вершин, поэтому максимальный размер его остовного дерева 4. С другой стороны, граф [math]\displaystyle{ K_5 }[/math] имет 10 рёбер, поэтому для их покрытия потребуется минимум 3 дерева. Следовательно, показанное ниже разбиение графа [math]\displaystyle{ K_5 }[/math] на 3 леса минимально.

Минимальное разбиение на остовные леса полного графа с пятью вершинами
$Полный граф [math]\displaystyle{ K_5 }[/math]$

Полный граф [math]\displaystyle{ K_5 }[/math]
$1-й остовный лес графа [math]\displaystyle{ K_5 }[/math]$

1-й остовный лес графа [math]\displaystyle{ K_5 }[/math]
$2-й остовный лес графа [math]\displaystyle{ K_5 }[/math]$

2-й остовный лес графа [math]\displaystyle{ K_5 }[/math]
$3-е остовное дерево графа [math]\displaystyle{ K_5 }[/math]$

3-е остовное дерево графа [math]\displaystyle{ K_5 }[/math]

Связность (англ. connectivity)

Более глубоко связность графа раскрывается путём использования понятий [math]\displaystyle{ k }[/math]-связности, блока и независимости путей^[79]^[78].

[math]\displaystyle{ k }[/math]-связный граф (вершинно [math]\displaystyle{ k }[/math]-связный) — это связный граф, который:

имеет больше [math]\displaystyle{ k }[/math] вершин;
остаётся связным после удаления менее [math]\displaystyle{ k }[/math] любых вершин.

Например, любой непустой граф 0-связен, а любой связный граф с более чем одной вершиной 1-связен. Двусвязный граф остаётся связным при удалении любой вершины.

Связность, или вершинная связность, графа [math]\displaystyle{ \kappa }[/math] — это наибольшее целое число [math]\displaystyle{ k }[/math], при котором граф [math]\displaystyle{ k }[/math]-связен.

Например, [math]\displaystyle{ \kappa = 0 }[/math] тогда и только тогда, когда граф:

либо несвязен;
либо состоит из одной вершины.

Связность связного графа с точкой сочленения равна 1. Полный граф [math]\displaystyle{ K_n }[/math] остаётся связным при удалении любого числа вершин и имеет одну вершину после удаления [math]\displaystyle{ n - 1 }[/math] вершины, поэтому [math]\displaystyle{ \kappa(K_n) = n - 1 }[/math] при всех [math]\displaystyle{ n \geqslant 1 }[/math].

Аналогично определяется рёберно [math]\displaystyle{ k }[/math]-связный граф и рёберная связность графа [math]\displaystyle{ \lambda }[/math].

Например, [math]\displaystyle{ \lambda = 0 }[/math] тогда и только тогда, когда граф:

либо несвязен;
либо состоит из одной вершины.

Рёберная связность связного графа с мостом равна 1.

Связность , рёберная связность [math]\displaystyle{ \lambda }[/math] и минимальная степень вершин [math]\displaystyle{ \delta }[/math] связаны следующим неравенством.

Теорема (Уитни, 1932). Для любого графа [math]\displaystyle{ G }[/math] с числом вершин больше одной

[math]\displaystyle{ \kappa(G) \leqslant \lambda(G) \leqslant \delta(G) }[/math].

Пример графа со значениями связностей, не равными друг другу
$Граф с [math]\displaystyle{ \kappa = 2, \lambda = 3, \delta = 4 }[/math]$

Граф с [math]\displaystyle{ \kappa = 2, \lambda = 3, \delta = 4 }[/math]

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

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

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

Подграф является блоком тогда и только тогда, когда он:

максимальный двусвязный подграф;
мост со своими вершинами;
изолированная вершина.

Разные блоки в графе по причине своей максимальности могут пересекаться только по одной точке сочленения. Следовательно:

каждое ребро графа состоит в единственном блоке;
сам граф — это объединение блоков.

В этом смысле блоки — это двусвязные аналоги компонент связности. Только компоненты связности не пересекаются, а блоки могут пересекаться. Блоки вместе со способами их пересечения определяют грубую структуру графа — граф блоков и точек сочленения.

Граф блоков и точек сочленения графа — это двудольный граф с сериями вершин [math]\displaystyle{ a }[/math] и [math]\displaystyle{ B }[/math], построенный следующим образом:

вершины [math]\displaystyle{ a }[/math] соответствуют всем точкам сочленения исходного графа, вершины [math]\displaystyle{ B }[/math] — блокам;
ребро соединяет вершину [math]\displaystyle{ a }[/math] с вершиной [math]\displaystyle{ B }[/math], если точка сочленения [math]\displaystyle{ a }[/math] принадлежит блоку [math]\displaystyle{ B }[/math].

Теорема. Граф блоков связного графа — дерево.

Пример графа и его графа блоков и точек сочленения
Исходный граф
Граф блоков и точек сочленения исходного графа

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

Определение [math]\displaystyle{ k }[/math]-связности связано с удалением [math]\displaystyle{ k }[/math] вершин. Возможно, более наглядно такое определение: граф [math]\displaystyle{ k }[/math]-связен, когда две его любые вершины можно соединить [math]\displaystyle{ k }[/math] независимыми путями. Эти два определения эквивалентны, это двойственные формулировки одного и того же свойства.

Классическая теорема Менгера — один из камней в основании теории графов.

Теорема (Менгер, 1927). Для любых подмножеств вершин графа [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] минимальное число вершин, отделяющих [math]\displaystyle{ A }[/math] от [math]\displaystyle{ B }[/math], равно максимальному числу независимых путей из [math]\displaystyle{ A }[/math] в [math]\displaystyle{ B }[/math].

Глобальный вариант теоремы Менгера.

(i) Граф [math]\displaystyle{ k }[/math]-связен тогда и только тогда, когда между любыми двумя его вершинами имеется [math]\displaystyle{ k }[/math] независимых путей.

(ii) Граф рёберно [math]\displaystyle{ k }[/math]-связен тогда и только тогда, когда между любыми двумя его вершинами имеется [math]\displaystyle{ k }[/math] непересекающихся по рёбрам путей.

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

Графа для иллюстрации теоремы Менгера
Белые вершины разделены не менее чем двумя вершинами и белые вершины можно соединить не более чем двумя независимыми путями

Планарные графы (англ. planar graphs)

Желательно, чтобы граф, нарисованный на листе бумаги, воспринимался как можно легче. Один из способов уменьшить хаос множества линий — избегать их пересечения. Можно ли нарисовать граф таким образом, чтобы рёбра не пересекались, то есть пересекались бы только в общих концевых вершинах^[80]^[81]^[82]?

Плоский граф — это граф, нарисованный на плоскости без пересечения рёбер, то есть рёбра пересекаются только в общих концевых вершинах.

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

Теорема. У плоского леса только одна грань — внешняя.

Теорема (формула Эйлера, 1736). Для любого связного плоского графа с [math]\displaystyle{ n }[/math] вершинами, [math]\displaystyle{ m }[/math] рёбрами и [math]\displaystyle{ l }[/math] гранями верна формула

[math]\displaystyle{ n - m + l = 2 }[/math].

Следствие формулы Эйлера. Плоский граф с тремя или более вершинами имеет не более [math]\displaystyle{ 3n - 6 }[/math] рёбер.

Плоский граф, формула Эйлера и грани
$Исходный плоский граф: 4 вершины, 5 рёбер и 3 грани, [math]\displaystyle{ 4 - 5 + 3 = 2 }[/math]$

Исходный плоский граф: 4 вершины, 5 рёбер и 3 грани, [math]\displaystyle{ 4 - 5 + 3 = 2 }[/math]
Три грани исходного графа: внешняя (красная) и две внутренние

Планарный граф — это граф, который можно нарисовать на плоскости как плоский.

Например, полный граф с четырьмя вершинами [math]\displaystyle{ K_4 }[/math] планарен.

Планарность полного графа с четырьмя вершинами
$Граф [math]\displaystyle{ K_4 }[/math], нарисованный как неплоский$

Граф [math]\displaystyle{ K_4 }[/math], нарисованный как неплоский
$Граф [math]\displaystyle{ K_4 }[/math], нарисованный как плоский$

Граф [math]\displaystyle{ K_4 }[/math], нарисованный как плоский

Два легендарных графа непланарны:

полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math];
полный двудольный граф [math]\displaystyle{ K_3,3 }[/math].

Докажем, что граф [math]\displaystyle{ K_5 }[/math] непланарен. От противного. Предположим, что [math]\displaystyle{ K_5 }[/math] планарен. Тогда по следствию формулы Эйлера [math]\displaystyle{ K_5 }[/math] имеет не более [math]\displaystyle{ 3\cdot5 - 6 = 9 }[/math] рёбер. Но [math]\displaystyle{ K_5 }[/math] имеет 10 рёбер. Полученное противоречие доказывает, что граф [math]\displaystyle{ K_5 }[/math] непланарен.

Легендарные непланарные графы
$Полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math]$

Полный граф с пятью вершинами [math]\displaystyle{ K_5 }[/math]
$Полный двудольный граф [math]\displaystyle{ K_{3,3} }[/math]$

Полный двудольный граф [math]\displaystyle{ K_{3,3} }[/math]

Стягивание ребра графа — это удаление ребра из графа и слияние концевых вершин этого ребра в одну вершину вместе со своими рёбрами.

Стягивание ребра
Стягивание ребра с концевыми вершинами u и v

Теорема Понтрягина — Куратовского (1927, 1930), или теорема Куратовского (1930). Граф планарен тогда и только тогда, когда из него нельзя получить удалением рёбер и вершин с их рёбрами и последующим стягиванием рёбер ни граф [math]\displaystyle{ K_5 }[/math], ни граф [math]\displaystyle{ K_{3,3} }[/math].

Например, из непланарного графа Петерсена можно получить подобным образом:

граф [math]\displaystyle{ K_5 }[/math] стягиванием внешних маленьких рёбер, направленных к центру графа: 0—5, 1—6, 2—7, 3—8, 4—9;
граф [math]\displaystyle{ K_{3,3} }[/math] таким образом, как показано на следующем анимационном рисунке.

Доказательство непланарности графа Петерсена
$Получение из графа Петерсена графа [math]\displaystyle{ K_{3,3} }[/math]$

Получение из графа Петерсена графа [math]\displaystyle{ K_{3,3} }[/math]

Раскраска (англ. colouring)

Сколькими цветами можно раскрасить страны на карте так, чтобы смежные страны имели разный цвет? Сколько дней заседает парламентский комитет, если каждый комитет заседает один день, а некоторые члены парламента служат в нескольких комитетах? Какова минимальная длина школьного расписания, если известно, как часто каждый преподаватель преподаёт в каждом классе^[83]^[84]?

Раскраска графа, или вершинная раскраска графа, — это раскраска вершин графа такая, что смежные вершины имеют разный цвет.

Примеры раскраски графов
$Раскраска полного графа [math]\displaystyle{ K_4 }[/math]$

Раскраска полного графа [math]\displaystyle{ K_4 }[/math]
$Раскраска полного графа [math]\displaystyle{ K_6 }[/math]$

Раскраска полного графа [math]\displaystyle{ K_6 }[/math]
Раскраска графа Петерсена

k-раскраска графа, или вершинная k-раскраска графа, или k-раскрашиваемость, — это вершинная раскраска графа в k цветов.

Различная k-раскраска графа-звезды с 5 вершинами
Граф-звезда с 5 вершинами раскрашен в 2 цвета
Граф-звезда с 5 вершинами раскрашен в 3 цвета
Граф-звезда с 5 вершинами раскрашен в 4 цвета

Хроматическое число графа, или вершинное хроматическое число графа, или k-хроматичность, — это минимальное k, при котором граф имеет k-раскраску. Обозначение: [math]\displaystyle{ \chi }[/math].

Например, граф 1-хроматичен, когда он имеет хотя бы одну вершину и не имеет рёбер. Полный граф [math]\displaystyle{ K_n }[/math] n-хроматичен. Граф-звезда с 5 вершинами 2-хроматичен. И все графы-звёзды 2-хроматичны. Более того, граф двудолен тогда и только тогда, когда он 2-хроматичен.

Теорема. У графа с m рёбрами

[math]\displaystyle{ \chi \leqslant \frac12 + \sqrt{2m + \frac14} }[/math].

Доказательство. Пусть граф [math]\displaystyle{ \chi }[/math]-раскрашен. Тогда для любых двух цветов имеется хотя бы одно ребро с концами, окрашенными в эти цвета. Значит, таких рёбер не меньше, чем [math]\displaystyle{ \frac12 \chi(\chi - 1) }[/math], то есть [math]\displaystyle{ m \geqslant \frac12 \chi(\chi - 1) }[/math]. Решая неравенство относительно [math]\displaystyle{ \chi }[/math], получаем утверждение теоремы.

Теорема о четырёх красках. Любой плоский граф 4-раскрашиваем.

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

Окраска географической карты в 4 цвета
Карта субъектов Российской Федерации, раскрашенная в четыре цвета

Гораздо проще доказывается следующая ослабленное утверждение.

Теорема о пяти красках. Любой плоский граф 5-раскрашиваем.

Следующее утверждение тоже широко известно.

Теорема (Грёч, 1959). Любой плоский граф без треугольников 3-раскрашиваем.

Раскраска планарного графа без треугольников в 3 цвета
3-раскраска бидиакис-куба, пример планарного графа без треугольников
3-раскраска планарного графа без треугольников

Рёберная раскраска графа, — это раскраска рёбер графа такая, что смежные рёбра имеют разный цвет.

Примеры рёберной раскраски графов
$Рёберная раскраска полного графа [math]\displaystyle{ K_4 }[/math]$

Рёберная раскраска полного графа [math]\displaystyle{ K_4 }[/math]
$Рёберная раскраска полного графа [math]\displaystyle{ K_8 }[/math]$

Рёберная раскраска полного графа [math]\displaystyle{ K_8 }[/math]
Рёберная раскраска графа Петерсена

Рёберная k-раскраска графа, или рёберная k-раскрашиваемость, — это рёберная раскраска графа в k цветов.

Различная рёберная k-раскраска полного графа с 4 вершинами
$Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 3 цвета$

Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 3 цвета
$Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 4 цвета$

Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 4 цвета
$Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 5 цветов$

Полный граф [math]\displaystyle{ K_4 }[/math] рёберно раскрашен в 5 цветов

Хроматический индекс графа, или рёберное хроматическое число графа, или рёберная k-хроматичность, — это минимальное k, при котором граф имеет рёберную k-раскраску. Обозначение: [math]\displaystyle{ \chi' }[/math].

Для хроматического числа графа [math]\displaystyle{ \chi }[/math] доказаны лишь очень грубые оценки, тогда как для хроматический индекс графа [math]\displaystyle{ \chi' }[/math] равен либо максимальной степени вершин графа [math]\displaystyle{ \Delta }[/math], либо [math]\displaystyle{ \Delta + 1 }[/math].

Ясно, что для любого графа [math]\displaystyle{ \chi' \geqslant \Delta }[/math].

Теорема (Кёниг, 1916). Для любого двудольного графа [math]\displaystyle{ \chi' = \Delta }[/math].

Теорема (Визинг, 1964). Для любого графа [math]\displaystyle{ \Delta \leqslant \chi' \leqslant \Delta + 1 }[/math].

Теорема Визинга делит конечные графы на два класса: имеющие [math]\displaystyle{ \chi' = \Delta }[/math] и имеющий [math]\displaystyle{ \chi' = \Delta + 1 }[/math].

Рёберная раскраска графов разных классов
$Полный граф [math]\displaystyle{ K_4 }[/math] имеет [math]\displaystyle{ \chi' = \Delta = 3 }[/math]$

Полный граф [math]\displaystyle{ K_4 }[/math] имеет [math]\displaystyle{ \chi' = \Delta = 3 }[/math]
$Полный граф [math]\displaystyle{ K_3 }[/math] имеет [math]\displaystyle{ \chi' = \Delta + 1 = 3 }[/math]$

Полный граф [math]\displaystyle{ K_3 }[/math] имеет [math]\displaystyle{ \chi' = \Delta + 1 = 3 }[/math]

Потоки (англ. flows)

Граф можно рассматривать как сеть, когда рёбра несут некоторый поток, например поток воды, или электрического тока, или данных и так далее. Как моделируется подобная ситуация математически^[85]^[86]?

Разбиение множества — это набор попарно непересекающихся подмножеств, объединение которых даёт всё множество.

Примеры разбиений множеств
Разбиение множества на 6 подмножеств
Разбиение множества на 7 подмножеств

Разрез в графе — это набор всех рёбер графа, пересекающих некоторое разбиение всех вершин графа на два множества — на стороны разбиения, то есть концевые вершины каждого ребра разреза находятся в разных сторонах разбиения.

Ясно, что стороны разбиения однозначно определяют разрез.

Бонд, или коцикл, — это минимальный по количеству рёбер непустой разрез в графе, то есть при удалении любого числа рёбра из разреза разрез перестаёт быть каким-либо разрезом.

В следующем примере 5-рёберный разрез не минимальный, поскольку при удалении 3 рёбер получается минимальный разрез, показанный справа.

Примеры разрезов в графе
5-рёберный разрез в 6-рёберном графе (не бонд)
2-рёберный разрез в том же графе (бонд)

Поток на графе — это набор целых чисел [math]\displaystyle{ f(x, y) }[/math], приписанных каждой упорядоченной паре [math]\displaystyle{ (x, y) }[/math] смежных узлов (вершин) сети (графа) такой, что:

выполняется антисимметричность потока [math]\displaystyle{ f(x, y) = -f(y, x) }[/math];
в узлах [math]\displaystyle{ x }[/math], в которых поток в сеть не входит и не выходит, выполняется первое правило Кирхгофа [math]\displaystyle{ \sum f(x, y) = 0 }[/math], где суммирование проводится по всем [math]\displaystyle{ y }[/math], смежным с [math]\displaystyle{ x }[/math].

Источник — это узел, где поток входит в сеть. Обозначение: [math]\displaystyle{ s }[/math].

Сток — это узел, где поток выходит из сети. Обозначение: [math]\displaystyle{ t }[/math].

Пример потока с источником s и стоком t на графе
Граф потока не имеет (для вершин u и v не выполнено правило Кирхгофа)
Поток на графе

Теория потоков:

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

Ребро мультиграфа не определяется однозначно парой [math]\displaystyle{ (x, y) }[/math] или [math]\displaystyle{ (y, x) }[/math].

Ориентированное ребро мультиграфа — это тройка [math]\displaystyle{ (e, x, y) }[/math], где [math]\displaystyle{ e }[/math] — ребро мультиграфа, начинающееся в вершине [math]\displaystyle{ x }[/math] и заканчивающееся в вершине [math]\displaystyle{ y }[/math].

Ребро [math]\displaystyle{ e }[/math] с [math]\displaystyle{ x \ne y }[/math] имеет два направления [math]\displaystyle{ (e, x, y) }[/math] и [math]\displaystyle{ (e, y, x) }[/math]. Петля имеет одно направление [math]\displaystyle{ (e, x, x) }[/math].

Циркуляция на графе — это функция [math]\displaystyle{ f(e, x, y) }[/math] такая, что:

(F1) выполняется антисимметричность циркуляции [math]\displaystyle{ f(e, x, y) = -f(e, y, x) }[/math] для всех ориентированных рёбер графа [math]\displaystyle{ (e, x, y) }[/math] с [math]\displaystyle{ x \ne y }[/math];

(F2) во всех узлах [math]\displaystyle{ v }[/math] выполняется первое правило Кирхгофа [math]\displaystyle{ \sum f(e, v, w) = 0 }[/math], где суммирование проводится по всем [math]\displaystyle{ w }[/math], смежным с [math]\displaystyle{ v }[/math].

Теорема. В циркуляции суммарный поток через любой разрез равен нулю:

[math]\displaystyle{ \sum f(e, v, w) = 0 }[/math], где суммирование идёт по всем рёбрам [math]\displaystyle{ (e, v, w) }[/math] произвольного разреза графа.

Пример циркуляции на графе (источников и стоков нет)
Граф циркуляции не имеет (для вершин s, t и v не выполнено правило Кирхгофа)
Циркуляция на графе
В циркуляция поток через любой разрез равен 0

Функция пропускной способности на графе, или пропускная способность рёбер графа, — это набор натуральных чисел (с нулём), приписанных каждому ориентированному ребру мультиграфа.

Функция пропускной способности на графе определена независимо для обоих направлений ребра.

Пример пропускной способности на графе
Граф с источником s и стоком t. Указаны пропускные способности ориентированных рёбер

Сеть — это мультиграф с двумя выделенными узлами (вершинами) [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math] и функцией пропускной способности [math]\displaystyle{ c(e, x, y) }[/math] на каждом ориентированном ребре [math]\displaystyle{ (e, x, y) }[/math].

Разрез сети — это разрез мультиграфа сети такой, что выделенные узлы [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math] лежат на разных сторонах разреза.

Пропускная способность разреза сети — это сумма [math]\displaystyle{ \sum c(e, v, w) }[/math], где суммирование идёт по всем рёбрам [math]\displaystyle{ (e, v, w) }[/math] разреза сети.

Поток в сети — это вещественнозначная функция [math]\displaystyle{ f(e, x, y) }[/math] в сети такая, что:

(F1) выполняется антисимметричность потока [math]\displaystyle{ f(e, x, y) = -f(e, y, x) }[/math] для всех ориентированных рёбер сети (графа) [math]\displaystyle{ (e, x, y) }[/math] с [math]\displaystyle{ x \ne y }[/math];

(F2') во всех узлах (вершинах) [math]\displaystyle{ v }[/math], кроме [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math], выполняется первое правило Кирхгофа [math]\displaystyle{ \sum f(e, v, w) = 0 }[/math], где суммирование проводится по всем [math]\displaystyle{ w }[/math], смежными с [math]\displaystyle{ v }[/math];

(F3) [math]\displaystyle{ f(e, x, y) \leqslant c(e, x, y) }[/math] для всех ориентированных рёбер сети [math]\displaystyle{ (e, x, y) }[/math].

Величина потока разреза сети — это сумма [math]\displaystyle{ \sum f(e, v, w) }[/math], где суммирование идёт по всем рёбрам [math]\displaystyle{ (e, v, w) }[/math] разреза сети.

Величина потока разреза сети одинакова для всех разрезов сети и называется величиной потока сети.

Теорема (Форд, Фалкерсон, 1956). В любой сети максимальная величина потока равна минимальной пропускной способности разрезов.

Пример максимального потока в сети
Сеть с источником s и стоком t. Для каждого ориентированного ребра указаны поток (1-е число) и пропускная способность (2-е число). Поток через любой разрез максимален и равен 18 — минимальной пропускной способности разрезов

Экстремальная теория графов (англ. extremal graph theory)

Какая рёберная плотность необходима для существования заданного подграфа — типичная экстремальная задача на графах. Достаточно высокая средняя степень вершин или большое хроматическое число гарантируют, что нужная подструктура обязательно встретится в графе? Какое наибольшее возможное число рёбер может иметь [math]\displaystyle{ n }[/math]-вершинный граф, чтобы не иметь другой, меньший, граф в качестве подграфа^[87]^[88]?

Экстремальный граф — для заданных натурального числа [math]\displaystyle{ n }[/math] и графа [math]\displaystyle{ H }[/math] это [math]\displaystyle{ n }[/math]-вершинный граф [math]\displaystyle{ G }[/math] с максимально возможным числом рёбер, не содержащий подграф [math]\displaystyle{ H }[/math]: [math]\displaystyle{ G \nsupseteq H }[/math]. Такое максимальное число рёбер обозначается [math]\displaystyle{ \operatorname{ex}(n, H) }[/math].

Максимальный граф — для заданных натурального числа [math]\displaystyle{ n }[/math] и графа [math]\displaystyle{ H }[/math] это [math]\displaystyle{ n }[/math]-вершинный граф [math]\displaystyle{ G }[/math] такой, что [math]\displaystyle{ G \nsupseteq H }[/math], но при добавлении любого нового ребра [math]\displaystyle{ G \supseteq H }[/math].

Ясно, что экстремальный граф максимален. Но не наоборот, как показано на рисунке ниже.

Пример экстремального графа и максимального не экстремального
$Полный граф 3-го порядка [math]\displaystyle{ K_3 }[/math]$

Полный граф 3-го порядка [math]\displaystyle{ K_3 }[/math]
$Экстремальный граф 4-го порядка для полного графа [math]\displaystyle{ K_3 }[/math]$

Экстремальный граф 4-го порядка для полного графа [math]\displaystyle{ K_3 }[/math]
$Максимальный, но не экстремальный граф 4-го порядка для [math]\displaystyle{ K_3 }[/math]$

Максимальный, но не экстремальный граф 4-го порядка для [math]\displaystyle{ K_3 }[/math]

[math]\displaystyle{ r }[/math]-дольный граф, или многодольный граф — это граф, у которого множество вершин допускает разбиение на [math]\displaystyle{ r }[/math] подмножеств — долей таких, что:

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

Полный [math]\displaystyle{ r }[/math]-дольный граф — это [math]\displaystyle{ r }[/math]-дольный граф, в котором каждые две вершины из разных долей смежны. Обозначение: [math]\displaystyle{ K_{n_1, n_2, \dots, n_r} }[/math].

Пример двудольных графов
Неполный двудольный граф
$Полный двудольный граф [math]\displaystyle{ K_{3, 3} }[/math]$

Полный двудольный граф [math]\displaystyle{ K_{3, 3} }[/math]

Пример 3-дольных графов
Неполный 3-дольный граф
$Полный 3-дольный граф [math]\displaystyle{ K_{3, 2, 2} }[/math]$

Полный 3-дольный граф [math]\displaystyle{ K_{3, 2, 2} }[/math]

Граф Турана — это [math]\displaystyle{ n }[/math]-вершинный граф со следующими свойствами:

это [math]\displaystyle{ r }[/math]-дольный граф с [math]\displaystyle{ r \leqslant n }[/math];
количества вершин долей отличаются друг от друга не более чем на 1.

Обозначение: граф Турана [math]\displaystyle{ T_r(n) }[/math] имеет [math]\displaystyle{ t_r(n) }[/math] рёбер.

Граф Турана [math]\displaystyle{ T_r(n) }[/math] плотен (то есть близок к полному графу), так как имеет около [math]\displaystyle{ n^2 }[/math] рёбер, точнее,

[math]\displaystyle{ t_r(n) \leqslant n^2 \frac{r-1}{2r} }[/math],

и равенство достигается, когда [math]\displaystyle{ r }[/math] делит [math]\displaystyle{ n }[/math].

Теорема (Туран, 1941). Граф Турана [math]\displaystyle{ T_{r - 1}(n) }[/math] — это единственный экстремальный граф для [math]\displaystyle{ n }[/math] и [math]\displaystyle{ K_r }[/math], причём [math]\displaystyle{ \operatorname{ex}(n, K_r) = t_{r - 1}(n) }[/math].

Пример графов, не являющихся графами Турана
Неполный двудольный граф
$Полный двудольный граф [math]\displaystyle{ K_{5, 3} }[/math], но размер долей отличается на 2$

Полный двудольный граф [math]\displaystyle{ K_{5, 3} }[/math], но размер долей отличается на 2

Пример графов Турана
$Полный двудольный граф [math]\displaystyle{ K_{3, 3} }[/math]: граф Турана [math]\displaystyle{ T_2(6) }[/math]$

Полный двудольный граф [math]\displaystyle{ K_{3, 3} }[/math]: граф Турана [math]\displaystyle{ T_2(6) }[/math]
$Полный 4-дольный граф [math]\displaystyle{ K_{4, 3, 3, 3} }[/math]: граф Турана [math]\displaystyle{ T_4(13) }[/math]$

Полный 4-дольный граф [math]\displaystyle{ K_{4, 3, 3, 3} }[/math]: граф Турана [math]\displaystyle{ T_4(13) }[/math]

Бесконечные графы (англ. infinite graphs)

Изучение бесконечных графов привлекательно, однако этим разделом теории графов часто пренебрегают. Терминология совпадает с терминологией конечных графов, за исключением принципиально новых понятий бесконечных графов. Наиболее типичные подобные понятия появляются уже при «минимуме бесконечности», когда у графа всего лишь счётное число вершин и только конечное число рёбер в вершинах^[89].

Локально конечный граф — это граф, в каждой вершине которого сходится конечное число рёбер.

Луч — это граф с бесконечными множествами вершин и рёбер, соответственно пронумерованных следующим образом:

[math]\displaystyle{ \{x_0, x_1, x_2, \dots \}, \{x_0x_1, x_1x_2, x_2x_3, \dots \}. }[/math]

Двойной луч — это граф с бесконечными множествами вершин и рёбер, соответственно пронумерованных следующим образом:

[math]\displaystyle{ \{ \dots, x_{-1}, x_0, x_1, \dots \}, \{ \dots, x_{-1}x_0, x_0x_1, x_1x_2, \dots \}. }[/math]

Пример двойного луча
Бесконечный граф со счётным числом вершин, в каждой вершине сходится 2 ребра

Ясно, что с точностью до изоморфизма существует только один луч и один двойной луч.

Двойной луч, во всех вершинах которого сходятся ровно два ребра, — это бесконечный 2-регулярный связный граф.

Путь — это либо конечный путь, либо луч, либо двойной луч.

Хвост — это подлуч луча или двойного луча. Луч имеет бесконечно много хвостов, которые отличаются только начальным конечным сегментом.

Гребень — это объединение луча с бесконечным количеством непересекающихся конечных путей, которые имеют первую вершину на луче. Зубья гребня — это последние вершины конечных путей гребня.

Пример гребня
$Гребень с белыми зубьями и лучом [math]\displaystyle{ R }[/math]$

Гребень с белыми зубьями и лучом [math]\displaystyle{ R }[/math]

Лемма Кёнига о бесконечном пути. Пусть:

граф — объединение бесконечного числа непересекающихся непустых конечных множеств [math]\displaystyle{ V_0, V_1, V_2, \dots }[/math];
у каждой вершины [math]\displaystyle{ v }[/math] из [math]\displaystyle{ V_n }[/math] при [math]\displaystyle{ n \geqslant 1 }[/math] есть сосед [math]\displaystyle{ f(v) }[/math] из [math]\displaystyle{ V_{n-1} }[/math].

Тогда граф содержит луч [math]\displaystyle{ v_0v_1v_2\dots }[/math] с [math]\displaystyle{ v_n \in V_n }[/math] для всех [math]\displaystyle{ n }[/math].

Лемма Кёнига о бесконечном пути
Иллюстрация к лемме Кёнига о бесконечном пути

Доказательство. 1. Имеется бесконечное множество конечных путей вида [math]\displaystyle{ v f(v) f(f(v)) \dots }[/math], которые заканчиваются в [math]\displaystyle{ V_0 }[/math]. Поскольку [math]\displaystyle{ V_0 }[/math] конечно, то имеется такая вершина [math]\displaystyle{ v_0 }[/math] в [math]\displaystyle{ V_0 }[/math], в которой заканчиваются бесконечно много таких путей.

2. Бесконечно много путей, заканчивающихся в [math]\displaystyle{ v_0 }[/math], имеют предпоследнюю вершину в [math]\displaystyle{ V_1 }[/math]. Путей бесконечно много, а [math]\displaystyle{ V_1 }[/math] конечно, поэтому имеется такая вершина [math]\displaystyle{ v_1 }[/math] в [math]\displaystyle{ V_1 }[/math], которая принадлежит бесконечному множеству таких путей.

3. Бесконечно много путей, проходящих через [math]\displaystyle{ v_1 }[/math], имеют вершину в [math]\displaystyle{ V_2 }[/math], поэтому имеется такая вершина [math]\displaystyle{ v_2 }[/math] в [math]\displaystyle{ V_2 }[/math], которая принадлежит бесконечному множеству этих путей.

4. И так далее до бесконечности. Бесконечный луч [math]\displaystyle{ v_0v_1v_2\dots }[/math] построен.

Приложения этой леммы о бесконечном пути основаны на том, что счётный граф можно рассматривать как бесконечную последовательность конечных подграфов.

Конец графа^[en] — это класс эквивалентности лучей графа. Два луча графа эквивалентны, если после удаления из графа любого конечного множества вершин оба луча имеют хвост в одной и той же компоненте связности.

Определим концы лестницы, бесконечной в две стороны. Каждый луч в этом графе содержит вершины, расположенные как угодно далеко либо слева, либо справа, но не одновременно слева и справа. Эти два типа лучей образуют два класса эквивалентности, поэтому лестница имеет два конца. На рисунке ниже эти концы графа отмечены точками.

2-сторонняя бесконечная лестница
2-сторонняя бесконечная лестница, концы отмечены точками

Особенно просты концы дерева:

два луча дерева эквивалентны тогда и только тогда, когда они имеют общий хвост;
для каждой фиксированной вершины дерева каждый конец содержит ровно один луч, начинающийся с этой вершины.

Даже локально конечное дерево может иметь континуум концов. Например, двоичное дерево, в котором вершины обозначены конечными 0—1 последовательностями, с пустым множеством [math]\displaystyle{ \emptyset }[/math] в качестве корня. Тогда концы такого дерева соответствуют его лучам, начинающимся с корня [math]\displaystyle{ \emptyset }[/math], и, следовательно, континууму бесконечных последовательностей 0—1.

Пример двоичного дерева
Двоичное дерево с континуумом концов, по одному для каждой бесконечной последовательности 0—1

Теория Рамсея для графов (англ. Ramsey theory for graphs)

Каждый ли достаточно большой граф содержит или полный граф [math]\displaystyle{ K_r }[/math], или индуцированное дополнение [math]\displaystyle{ \overline{K_r} }[/math]? Несмотря на сходство с экстремальными задачами с их поиском локальных следствий глобальных предположений, последний вопрос приводит к математике несколько иного рода. Действительно, теоремы и доказательства теории Рамсея имеют больше общего с подобными результатами из алгебры или геометрии. Язык графов естествен в рамсеевских задачах, и материал показывает разнообразие идей и методов, достаточное для того, чтобы передать обаяние этой теории в целом^[90]^[91]^[92]?

Дополнение графа — это граф, у которого:

множество верши совпадает с множеством вершин исходного графа;
вершины соединены ребром тогда и только тогда, когда они не соединены ребром в исходном графе. Обозначение для графа [math]\displaystyle{ G }[/math]: [math]\displaystyle{ \overline{G} }[/math].

Дополнение полного графа [math]\displaystyle{ K_r }[/math] — вполне несвязный граф [math]\displaystyle{ \overline{K_r} }[/math], содержащий только вершины.

Графы и их дополнения
Квадрат (слева) и его дополнение (справа)
$Полный граф [math]\displaystyle{ K_6 }[/math]$

Полный граф [math]\displaystyle{ K_6 }[/math]
$Дополнение [math]\displaystyle{ \overline{K_6} }[/math]$

Дополнение [math]\displaystyle{ \overline{K_6} }[/math]

Самодополнительный граф — это граф, который изоморфен своему дополнению. Наименьшие нетривиальные самодополнительные графы содержат 4 и 5 вершин.

Наименьшие нетривиальные самодополнительные графы
Самодополнительный граф с 4 вершинами
Самодополнительный граф с 5 вершинами
Самодополнительный граф с 5 вершинами

Задача Рамсея — широко известная головоломка:

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

Формулировка задачи Рамсея в теории графов:

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

Точная формулировка с использованием дополнения графа.

Теорема. Любой граф с шестью вершинами либо содержит треугольник, либо его дополнение содержит треугольник.

Доказательство. 1. Пусть дан граф [math]\displaystyle{ G }[/math] с шестью вершинами. Возьмём любую его вершину [math]\displaystyle{ v }[/math]. Вершина [math]\displaystyle{ v }[/math] соединена ребром с любой из остальных пяти вершин или в [math]\displaystyle{ G }[/math], или в [math]\displaystyle{ \overline{G} }[/math]. Поэтому, не теряя общности, предположим, что [math]\displaystyle{ v }[/math] соединена с вершинами [math]\displaystyle{ u_1, u_2, u_3 }[/math] в [math]\displaystyle{ G }[/math].

2. Если из вершин [math]\displaystyle{ u_1, u_2, u_3 }[/math] какие-нибудь две соединены ребром, то с [math]\displaystyle{ v }[/math] получается треугольник в [math]\displaystyle{ G }[/math]. Если никакие две из вершин [math]\displaystyle{ u_1, u_2, u_3 }[/math] не соединены ребром, то они образуют треугольник в [math]\displaystyle{ \overline{G} }[/math].

Обобщение теоремы.

Теорема (Рамсей, 1930). Для любого натурального числа [math]\displaystyle{ r }[/math] существует натуральное число [math]\displaystyle{ n }[/math] такое, что любой граф с не менее чем [math]\displaystyle{ n }[/math] вершинами или его дополнение содержат [math]\displaystyle{ K_r }[/math].

Удобно использовать раскраску в формулировке теоремы Рамсея:

для любого полного графа [math]\displaystyle{ K_r }[/math] существует такой полный граф [math]\displaystyle{ K_n }[/math], что любая его двуцветная раскраска ребёр содержит одноцветный [math]\displaystyle{ K_r }[/math].

Число Рамсея — это наименьшее [math]\displaystyle{ n }[/math] для данного [math]\displaystyle{ r }[/math] в теореме Рамсея. Обозначение: [math]\displaystyle{ R(r) }[/math].

Из стандартного доказательства теоремы Рамсея следует верхняя оценка числа Рамсея: [math]\displaystyle{ R(r) \leqslant 2^{2r-3} }[/math]. С помощью вероятностного метода можно найти нижнюю оценку: [math]\displaystyle{ R(r) \geqslant 2^{r/2} }[/math].

Например, [math]\displaystyle{ R(3) = 6 }[/math]:

из решения задачи Рамсея следует, что [math]\displaystyle{ R(3) \leqslant 6 }[/math];
докажем, что [math]\displaystyle{ R(3) \gt 5 }[/math]. Достаточно привести один пример графа с 5 вершинами, который не удовлетворяет теореме Рамсея для [math]\displaystyle{ K_3 }[/math]. Это самодополнительный пятиугольник, показанный выше, имеет 5 вершин и не содержит треугольников, и также не содержит треугольников его дополнение, которое с ним совпадает;
[math]\displaystyle{ R(3) \leqslant 6 }[/math] и [math]\displaystyle{ R(3) \gt 5 }[/math], то есть [math]\displaystyle{ R(3) = 6 }[/math].

Иллюстрация формулы R(3) = 6. Красные рёбра — граф, синие — его дополнение
Граф с 6 вершинами, есть только красные треугольники
Граф с 6 вершинами, есть только синие треугольники
Граф с 5 вершинами, нет ни красных, ни синих треугольников

Теорема Рамсея верна не только для полного графа [math]\displaystyle{ K_r }[/math], но и для любого графа [math]\displaystyle{ H }[/math] просто потому, что [math]\displaystyle{ H }[/math] — подграф полного графа [math]\displaystyle{ K_h }[/math], где [math]\displaystyle{ h }[/math] — число вершин [math]\displaystyle{ H }[/math].

Число Рамсея любого графа [math]\displaystyle{ H }[/math] — это наименьшее натуральное число [math]\displaystyle{ n }[/math] такое, что любой [math]\displaystyle{ n }[/math]-вершинный граф или его дополнение содержат [math]\displaystyle{ H }[/math]. Обозначение: [math]\displaystyle{ R(H) }[/math].

Если в графе мало рёбер, то он легче включается в другой граф, и можно ожидать [math]\displaystyle{ R(H) \lt R(h) = R(K_h) }[/math], где [math]\displaystyle{ h }[/math] — число вершин [math]\displaystyle{ H }[/math].

Ещё немного обобщим.

Число Рамсея пары графов [math]\displaystyle{ H_1 }[/math] и [math]\displaystyle{ H_2 }[/math] — это наименьшее натуральное число [math]\displaystyle{ n }[/math] такое, что для любого [math]\displaystyle{ n }[/math]-вершинного графа либо сам граф содержит [math]\displaystyle{ H_1 }[/math], либо его дополнение содержит [math]\displaystyle{ H_2 }[/math]. Обозначение: [math]\displaystyle{ R(H_1, H_2) }[/math], для полных графов [math]\displaystyle{ R(K_r, K_s) \equiv R(r, s) }[/math].

Ясно, что [math]\displaystyle{ R(H, H) = R(H) }[/math], [math]\displaystyle{ R(r, r) = R(r) }[/math].

Для большинства графов известны только очень грубые оценки для чисел Рамсея, точные нетривиальные числа Рамсея известны лишь для очень немногих графов.

Например, [math]\displaystyle{ R(3) = 6 }[/math], [math]\displaystyle{ R(4) = 18 }[/math], [math]\displaystyle{ R(3, 4) = R(4, 3) = 9 }[/math], [math]\displaystyle{ R(4, 5) = R(5, 4) = 25 }[/math].

Иллюстрация формулы R(3, 4) = 9. Красные рёбра — граф, синие — его дополнение
$Граф с 9 вершинами, есть красные [math]\displaystyle{ K_3 }[/math], нет синих [math]\displaystyle{ K_4 }[/math]$

Граф с 9 вершинами, есть красные [math]\displaystyle{ K_3 }[/math], нет синих [math]\displaystyle{ K_4 }[/math]
$Граф с 9 вершинами, нет красных [math]\displaystyle{ K_3 }[/math], есть синие [math]\displaystyle{ K_4 }[/math]$

Граф с 9 вершинами, нет красных [math]\displaystyle{ K_3 }[/math], есть синие [math]\displaystyle{ K_4 }[/math]
$Граф с 8 вершинами, нет ни красных [math]\displaystyle{ K_3 }[/math], ни синих [math]\displaystyle{ K_4 }[/math]$

Граф с 8 вершинами, нет ни красных [math]\displaystyle{ K_3 }[/math], ни синих [math]\displaystyle{ K_4 }[/math]

Гамильтоновы циклы (англ. Hamilton cycles)

Задача о том, содержит ли граф замкнутый маршрут, проходящий через каждое ребро в точности один раз, легко решается с помощью простой теоремы Эйлера (1736). Намного труднее решается такой же вопрос относительно вершин: когда граф содержит замкнутый маршрут, проходящий через каждую вершину в точности один раз^[93]^[94]^[95]?

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

Гамильтонов граф — это граф, который имеет гамильтонов цикл.

Ясно, что в каждую вершину гамильтонова графа входят по меньшей мере два ребра.

Примеры гамильтоновых циклов
Гамильтонов цикл на плоском додекаэдре
Гамильтонов цикл на объёмном додекаэдре

Теорема. Любой гамильтонов граф двусвязен.

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

Примеры односвязных графов
Граф «Дротик» негамильтонов
Граф «Рыба» негамильтонов

Тета-граф — это граф, который содержит только следующие вершины:

две вершины, в которые входят по три ребра;
вершины, в которые входят по два ребра.

То есть тета-граф имеет две вершины степени 3 и три непересекающиеся простые цепи, которые соединяют эти две вершины, длиной не менее 2 каждая.

Примеры тета-графов
$Простейший тета-граф — полный двудольный граф [math]\displaystyle{ K_{2, 3} }[/math]$

Простейший тета-граф — полный двудольный граф [math]\displaystyle{ K_{2, 3} }[/math]
Тета-граф с 7 вершинами
Тета-граф с 9 вершинами

Тета-граф негамильтонов. Простейший негамильтонов двусвязный граф — полный двудольный граф [math]\displaystyle{ K_{2, 3} }[/math].

Теорема. В каждом негамильтоновом двусвязном графе имеется тета-подграф.

То есть наличие тета-подграфа — необходимое условие негамильтоновости. Не каждый граф с тета-подграфом негамильтонов.

Простейший гамильтонов граф с тета-подграфом — полный двудольный граф [math]\displaystyle{ K_{2, 3} }[/math] с добавленным ребром.

Простейшие гамильтоновы графы
Простейший гамильтонов граф
Простейший гамильтонов граф с тета-подграфом

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

Теорема (Дирак^[en], 1952). Граф с [math]\displaystyle{ n \geqslant 3 }[/math] вершинами гамильтонов, если:

1) минимальная степень [math]\displaystyle{ \delta }[/math] его вершин зависит от n;

2) [math]\displaystyle{ \delta \geqslant n/2 }[/math].

То есть [math]\displaystyle{ \delta \geqslant n/2 }[/math] — достаточное условие гамильтоновости. Не для каждого гамильтонова графа выполняется это условие. Например, для простейшего гамильтонова графа с тета-подграфом условие не выполнено.

Кубический граф — это 3-регулярный граф, то есть граф, в каждой вершине которого сходится ровно 3 ребра.

Для планарных графов гамильтоновость связана с проблемой четырёх красок. Для доказательства теоремы о четырех красках достаточно доказать гипотезу Тэйта: любой 3-связный планарный кубический граф имеет гамильтонов цикл.

Гипотеза не подтвердилась. Первый контрпример был найден Таттом в 1946 году.

Контрпример гипотезе Тайта: граф Татта
3-связный планарный кубический граф без гамильтонова цикла

Теорема (Татт, 1956). Любой 4-связный планарный граф гамильтонов.

Примеры 4-связных планарных графов
4-связный планарный граф: октаэдр
5-связный планарный граф: икосаэдр

Случайные графы (англ. random graphs)

Вероятностный метод позволяет доказать существование объекта с заданным свойством следующим образом: 1) определяется вероятностное пространство на некотором большем классе объектов, заведомо непустом; 2) показывается, что искомое свойство выполняются для случайно выбранного элемента пространства с положительной вероятностью. Суть вероятностного метода в том, чтобы неконструктивно показать, что заданная раскраска существует или нет^[96]^[97]^[98].

Вероятностный метод хорошо иллюстрируется следующим примером: получим нижнюю оценку для числа Рамсея [math]\displaystyle{ R(k) }[/math].

1. Построим вероятностное пространство. Случайно раскрасим полный граф [math]\displaystyle{ K_n }[/math], то есть с равной вероятностью раскрасим каждое ребро [math]\displaystyle{ K_n }[/math] независимо в красный или синий цвет. Таким образом, вероятность для ребра [math]\displaystyle{ K_n }[/math] получить красный цвет равна [math]\displaystyle{ \frac{1}{2} = 2^{-1} }[/math], синий цвет — тоже [math]\displaystyle{ 2^{-1} }[/math].

2. Определим на случайно раскрашенном [math]\displaystyle{ K_n }[/math] следующее событие: случайно выбранный полный подграф [math]\displaystyle{ K_k }[/math] монохромен, то есть либо красный, либо синий. Подграф [math]\displaystyle{ K_k }[/math] имеет [math]\displaystyle{ {k\choose 2} }[/math] рёбер, поэтому вероятность уже выбранного подграфа [math]\displaystyle{ K_k }[/math] оказаться красным равна [math]\displaystyle{ 2^{-{k\choose 2}} }[/math], синим — тоже [math]\displaystyle{ 2^{-{k\choose 2}} }[/math], монохромным — [math]\displaystyle{ 2^{-{k\choose 2}} + 2^{-{k\choose 2}} = 2^{1-{k\choose 2}} }[/math].

Вероятность уже выбранного подграфа [math]\displaystyle{ K_k }[/math] быть одноцветным не зависит от [math]\displaystyle{ n }[/math]. Например, вероятность [math]\displaystyle{ K_3 }[/math] быть одноцветным всегда равна

[math]\displaystyle{ 2^{1-{3\choose 2}} = 2^{1-\frac{3!}{2!1!}} = 2^{1-\frac{6}{2}} = 2^{-2} = \frac{1}{4} }[/math],

вероятность [math]\displaystyle{ K_4 }[/math] быть одноцветным всегда равна

[math]\displaystyle{ 2^{1-{4\choose 2}} = 2^{1-\frac{4!}{2!2!}} = 2^{1-\frac{24}{4}} = 2^{-5} = \frac{1}{32} }[/math].

3. Подсчитаем теперь вероятность случайно выбранного подграфа [math]\displaystyle{ K_k }[/math] оказаться монохромным. Выбрать подграф [math]\displaystyle{ K_k }[/math] в полном графе [math]\displaystyle{ K_n }[/math] можно [math]\displaystyle{ {n\choose k} }[/math] разными способами. Поскольку события оказаться монохромными для этих подграфов могут оказаться зависимыми друг от друга, то вероятность случайно выбранного в [math]\displaystyle{ K_n }[/math] подграфа [math]\displaystyle{ K_k }[/math] оказаться монохромным всего лишь не больше суммы их вероятностей [math]\displaystyle{ {n\choose k}2^{1-{k\choose 2}} }[/math].

Например, вероятность [math]\displaystyle{ K_3 }[/math] оказаться монохромным в [math]\displaystyle{ K_3 }[/math] не больше

[math]\displaystyle{ {3\choose 3}2^{1-{3\choose 2}} = \frac{3!}{3!0!}2^{1-\frac{3!}{2!1!}} = 2^{1-\frac{6}{2}} = 2^{-2} = \frac{1}{4} }[/math],

вероятность [math]\displaystyle{ K_3 }[/math] оказаться монохромным в [math]\displaystyle{ K_4 }[/math] не больше

[math]\displaystyle{ {4\choose 3}2^{1-{3\choose 2}} = \frac{4!}{3!1!}2^{1-\frac{3!}{2!1!}} = 4\cdot2^{1-\frac{6}{2}} = 2^22^{-2} = 1 }[/math].

Оценим число Рамсея снизу. Если [math]\displaystyle{ n }[/math] достаточно мало для данного [math]\displaystyle{ k }[/math], то число Рамсея [math]\displaystyle{ R(k) \gt n }[/math].

Лемма. Если [math]\displaystyle{ {n\choose k}2^{1-{k\choose 2}} \lt 1 }[/math], то [math]\displaystyle{ R(k) \gt n }[/math].

Доказательство. 1. Пусть [math]\displaystyle{ {n\choose k}2^{1-{k\choose 2}} \lt 1 }[/math], то есть вероятность случайно выбранного в [math]\displaystyle{ K_n }[/math] подграфа [math]\displaystyle{ K_k }[/math] оказаться монохромным меньше 1.

2. Тогда вероятность всех подграфов [math]\displaystyle{ K_k }[/math] не оказаться монохромными больше нуля: [math]\displaystyle{ 1- {n\choose k}2^{1-{k\choose 2}} \gt 0 }[/math].

3. Другими словами, существует 2-раскраска [math]\displaystyle{ K_n }[/math] без монохроматических [math]\displaystyle{ K_k }[/math], то есть [math]\displaystyle{ R(k) \gt n }[/math].

Теорема (Эрдёш, 1947). Для любого натурального [math]\displaystyle{ k \geqslant 3 }[/math] число Рамсея [math]\displaystyle{ R(k) \gt 2^{k/2} }[/math].

Эта нижняя [math]\displaystyle{ R(k) \gt 2^{k/2} }[/math] и верхняя [math]\displaystyle{ R(k) \leqslant 2^{2k-3} }[/math] оценки весьма близки.

Доказательство. 1. При [math]\displaystyle{ k = 3 }[/math] имеем:

[math]\displaystyle{ {n\choose k} = {n\choose 3} = \frac{n!}{3!(n-3)!} = \frac{n(n-1)(n-2)}{6} \lt \frac{n^3}{6} }[/math],

[math]\displaystyle{ 2^{1-{k\choose 2}} = 2^{1-{3\choose 2}} = 2^{1-\frac{3!}{2!1!}} = 2^{-2} = \frac{1}{2^2} }[/math].

При всех [math]\displaystyle{ n \leqslant 2^{3/2} }[/math] имеем:

[math]\displaystyle{ {n\choose k} \lt \frac{n^3}{6} \leqslant \frac{2^{9/2}}{6} = \frac{2^{7/2}}{3} }[/math],

[math]\displaystyle{ {n\choose k}2^{1-{k\choose 2}} \lt \frac{2^{7/2}}{3}\frac{1}{2^2} = \frac{2^{3/2}}{3} \lt \frac{2,83}{3} \lt 1 }[/math].

Теперь по лемме [math]\displaystyle{ R(3) \gt n }[/math] для всех [math]\displaystyle{ n \leqslant 2^{3/2} }[/math], то есть [math]\displaystyle{ R(3) \gt 2^{3/2} }[/math].

2. Пусть теперь [math]\displaystyle{ k \geqslant 4 }[/math]. Имеем:

[math]\displaystyle{ k! = 1\cdot2\cdot3\cdot4\cdot\,\dots\,\cdot k = 2\cdot2\cdot3\cdot2\cdot\,\dots\,\cdot k \gt 2^k }[/math].

При всех [math]\displaystyle{ n \leqslant 2^{k/2} }[/math] выкладки как при [math]\displaystyle{ k = 3 }[/math]:

[math]\displaystyle{ {n\choose k}2^{1-{k\choose 2}} = \frac{1}{k!}\frac{n!}{(n - k)!}2^{1-\frac{k!}{2!(k-2)!}} \lt \frac{n^k}{2^k}2^{1-\frac{k(k-1)}{2}} \leqslant \frac{2^{k^2/2}}{2^k}2^{1-k^2/2 + k/2} = }[/math]

[math]\displaystyle{ = \frac{2^{1 + k/2}}{2^k} = 2^{1-k/2} \leqslant 2^{1-4/2} = \frac{1}{2} \lt 1 }[/math].

Теперь по лемме [math]\displaystyle{ R(k) \gt n }[/math] для всех [math]\displaystyle{ n \leqslant 2^{k/2} }[/math], то есть [math]\displaystyle{ R(k) \gt 2^{k/2} }[/math].

Случайный граф — это подграф полного графа [math]\displaystyle{ K_n }[/math], полученный случайным образом. Например, если все рёбра [math]\displaystyle{ K_n }[/math] случайным образом окрашены в красный или синий цвет, то случайным граф — это подграф, образованный всеми красными рёбрами. Ясно, что случайные графы — это независимые события. Обозначение: вероятность случайного графа [math]\displaystyle{ G }[/math] обозначается [math]\displaystyle{ P(G) }[/math].

Случайная величина — это неотрицательное вещественное число, заданное на каждом случайном графе [math]\displaystyle{ G }[/math]. Например, это может быть число вершин случайного графа, связность, хроматическое число и так далее. Обозначение: [math]\displaystyle{ X(G) }[/math].

Математическое ожидание, или среднее, случайной величины — это взвешенная сумма вероятностей всех случайных графов:

[math]\displaystyle{ E(X) = \sum P(G)X(G) }[/math].

Математическое ожидание линейно, то есть равенства

[math]\displaystyle{ E(X + Y) = E(X) + E(Y) }[/math] и [math]\displaystyle{ E(\lambda X) = \lambda E(X) }[/math]

выполняются для любых двух случайных величин [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] и любого вещественного числа [math]\displaystyle{ \lambda }[/math].

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

Неравенство Маркова. Для любой случайной величины [math]\displaystyle{ X \geqslant 0 }[/math] и любого вещественного числа [math]\displaystyle{ a \gt 0 }[/math] выполняется неравенство

[math]\displaystyle{ P(X \geqslant a) \leqslant \frac{E(X)}{a} }[/math].

Доказательство. Очевидно, что (суммирование ведётся по всем случайным графам [math]\displaystyle{ G }[/math])

[math]\displaystyle{ E(X) = \sum\limits_G P(G)X(G) \geqslant \sum\limits_{G\atop X(G) \geqslant a} P(G)X(G) \geqslant }[/math]

[math]\displaystyle{ \geqslant \sum\limits_{G\atop X(G) \geqslant a} P(G)a = a P(X \geqslant a) }[/math].

Миноры, деревья и полный предпорядок (англ. minors, trees and well-quasi-ordering)

Одна из самых глубоких математических теорем, которая затмевает любую другую теорему теории графов — это теорема о минорах графа: любое бесконечное множество графов содержит два графа таких, что один есть минор другого. Ниже объясняются некоторые основные понятия на подступах к этой теореме, доказательство которой занимает 500 страниц^[99]^[100].

Предпорядок, или квазипорядок — это рефлексивное и транзитивное отношение на множестве. Обозначение: [math]\displaystyle{ \leqslant }[/math].

Полный предпорядок^[en], или правильный квазипорядок — это предпорядок, при котором любая бесконечная последовательность элементов множества содержит два предупорядоченных элемента, причём больший элемент следует в последовательности за меньшим. Другими словами, любая последовательность [math]\displaystyle{ x_0, x_1, x_2, \dots }[/math] в множестве [math]\displaystyle{ X }[/math] содержит [math]\displaystyle{ x_i \leqslant x_j }[/math], [math]\displaystyle{ i \lt j }[/math].

Вполне предупорядоченные элементы — это элементы вполне предупорядоченного множества.

Теорема. Предпорядок на множестве тогда и только тогда полный, когда множество не содержит следующих бесконечных последовательностей элементов:

с попарно несравнимыми элементами;
строго убывающей, то есть последовательности [math]\displaystyle{ x_0 \gt x_1 \gt x_2 \gt \dots }[/math], где [math]\displaystyle{ x_i \gt x_j }[/math] означает [math]\displaystyle{ x_i \geqslant x_j }[/math] и [math]\displaystyle{ x_i \ne x_j }[/math].

Примеры. 1. Отношение делимости [math]\displaystyle{ \,\vdots\, }[/math] на множестве натуральных чисел предупорядочено и даже частично упорядочено, но не вполне предупорядочено, поскольку бесконечная последовательность простых чисел не содержит предупорядоченной пары.

2. Отношение делимости на множестве целых чисел предупорядочено и не частично упорядочено (поскольку, например, [math]\displaystyle{ 2\,\vdots-2 }[/math] и [math]\displaystyle{ -2\,\vdots\,2 }[/math], но [math]\displaystyle{ 2\ne-2 }[/math]) и также не вполне предупорядочено.

Отношение делимости
Диаграмма Хассе отношения делимости натуральных чисел

Подразбиение, или расширение, графа, или граф подразбиений — это граф, полученный из исходного делением рёбер вершинами.

Топологический минор графа — это граф, подразбиение которого есть подграф исходного графа.

Топологический минор сохраняет топологическую форму подграфа исходного графа.

Пример топологического минора
$Исходный граф [math]\displaystyle{ G }[/math]$

Исходный граф [math]\displaystyle{ G }[/math]
$Подразбиение [math]\displaystyle{ H }[/math] — подграф [math]\displaystyle{ G }[/math]$

Подразбиение [math]\displaystyle{ H }[/math] — подграф [math]\displaystyle{ G }[/math]
$Топологический минор [math]\displaystyle{ H }[/math] графа [math]\displaystyle{ G }[/math]$

Топологический минор [math]\displaystyle{ H }[/math] графа [math]\displaystyle{ G }[/math]

Минор графа — это граф, полученный из исходного графа удалением вершин и удалением и стягиванием рёбер. Обозначение отношения [math]\displaystyle{ X }[/math] — минор [math]\displaystyle{ Y }[/math]: [math]\displaystyle{ X \preccurlyeq Y }[/math]

Любой подграф графа — его минор. Любой граф — свой собственный минор.

Пример минора
Минор получен удалением ef и стягиванием bc

Теорема. (i) Любой топологический минор графа есть также его (обычный) минор. Обратное в общем случае неверно.

(ii) Для графа, в каждую вершину которого входит не более 3 рёбер, любой минор есть топологический минор.

Теорема. На множестве всех конечных графов отношения быть минором [math]\displaystyle{ \preccurlyeq }[/math] и быть топологическим минором суть частичные порядки.

Диаграмма Хассе отношения быть (топологическим) минором
Отношение быть (топологическим) минором квадрата. Все миноры — подграфы, кроме треугольника. Треугольник получается из квадрата стягиванием вершины

Запрещённый, или исключённый, минор для данного свойства графов — это граф, наличие которого как минора в графе говорит об отсутствии в последнем данного свойства.

По предыдущей теореме, множество запрещённых миноров замкнуто относительно взятия миноров: если граф [math]\displaystyle{ G }[/math] — запрещённый минор и [math]\displaystyle{ H \preccurlyeq G }[/math], то граф [math]\displaystyle{ H }[/math] — тоже запрещённый минор.

Теорема. Свойство графов можно задать запрещёнными минорами тогда и только тогда, когда оно замкнуто относительно взятия миноров.

Свойства графов, замкнутые относительно взятия миноров, часто встречаются в теории графов. Наиболее известный пример дан теоремой Понтрягина — Куратовского: планарность задаётся запрещением миноров [math]\displaystyle{ K_5 }[/math] и [math]\displaystyle{ K_{3, 3} }[/math].

Характеризация запрещёнными графами — это хорошая характеризация.

Хорошая характеризация — это характеризация свойства графов, упрощающая доказательство отсутствия этого свойства. Просто убедиться, что граф обладает некоторым свойством, достаточно изобразить граф определённым образом. Сложности возникают при доказательстве отсутствия свойства. Но, например, при наличии запрещённых миноров для свойства его отсутствие легко доказывается предъявлением какого-нибудь запрещённого минора.

Теорема. При наличии запрещённых миноров всегда существует единственное наименьшее их множество, элементы которого — миноры всех запрещённых миноров.

Ясно, что запрещённые миноры из наименьшего множества несравнимы по отношению [math]\displaystyle{ \preccurlyeq }[/math] быть минором. Следующая теорема утверждает, что любое множество несравнимых по [math]\displaystyle{ \preccurlyeq }[/math] графов конечно.

Теорема Робертсона — Сеймура (1986—2004). Конечные графы вполне предупорядочены по отношению [math]\displaystyle{ \preccurlyeq }[/math] быть минором.

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

Сильный вариант этой теоремы для деревьев следующий.

Теорема (Краскал, 1960)^[en]^*. Конечные деревья вполне предупорядочены по отношению быть топологическим минором.

Пример множества запрещённых миноров
Петерсеново семейство, запрещённые миноры для незацепленного вложения графа

Немного линейной алгебры (англ. some linear algebra)

В основе простых циклов и рёберных разрезов графов лежит алгебраическая структура, достижение понимания которой делает возможным применение мощных и красивых методов линейной алгебры, которые приводят, в свою очередь, к более глубокому пониманию теории графов и соответствующих алгоритмов на графах^[101]^[102]^[103]^[104].

Пространство вершин графа — это множество всех подмножеств множества всех вершин графа, преобразованное в векторное пространство над 2-элементным полем [math]\displaystyle{ \{0, 1\}. }[/math] Обозначение пространства вершин графа [math]\displaystyle{ G: \mathcal{V}(G). }[/math]

Вектор этого пространства — это подмножество вершин графа:

сумма двух векторов определяется как сумма по модулю 2, или симметрическая разность, или кольцевая сумма, подмножеств;
вектор противоположен сам себе;
нуль-вектор — пустое множество вершин;
базис векторного пространства составляют все одноэлементные подмножества — вершины графа. Поэтому размерность векторного пространства равна числу вершин графа.

Таблица сложения по модулю 2 векторов пространства 4 вершин
[math]\displaystyle{ \oplus }[/math]

Пространство рёбер графа — это множество всех подмножеств множества всех рёбер графа, преобразованное в векторное пространство над 2-элементным полем [math]\displaystyle{ \{0, 1\}. }[/math] Обозначение пространства рёбер графа [math]\displaystyle{ G: \mathcal{E}(G). }[/math]

Полностью аналогично пространству вершин.

Структуру графа задают его рёбра, поэтому обычно имеют дело с пространством рёбер.

Ниже показана таблица сложения по модулю 2 векторов пространства рёбер [math]\displaystyle{ \mathcal{E}(C_4) }[/math] циклического графа [math]\displaystyle{ C_4 }[/math]. Элементы подпространства разрезов [math]\displaystyle{ \mathcal{B}(C_4) }[/math] находятся внутри синих рамок, три элемента одного из базисов этого подпространства выделены синим. Подпространство циклов [math]\displaystyle{ \mathcal{C}(C_4) }[/math] в данном случае есть подпространство подпространства разрезов и состоит из двух элементов: пустого множества и графа [math]\displaystyle{ C_4 }[/math]; его элементы выделены голубым.

Остовное дерево, шесть бондов и цикл графа [math]\displaystyle{ C_4 }[/math]

Синее остовное дерево	Шесть бондов (минимальных разрезов). Три элемента одного из базисов выделены синим						Цикл

Таблица сложения по модулю 2 векторов пространства 4 рёбер графа [math]\displaystyle{ C_4 }[/math]
[math]\displaystyle{ \oplus }[/math]

Пространство циклов графа — это подпространство пространства рёбер графа, которое порождается всеми простыми циклами графа. Обозначение пространства циклов графа [math]\displaystyle{ G: \mathcal{C}(G). }[/math]

Другими словами, пространство циклов натянуто на простые циклы, то есть состоит из:

пустого множества;
всех простых циклов графа;
всех сумм по модулю 2 простых циклов графа.

Теорема. Пространство циклов порождается также циклами без хорд.

Цикломатическое число, или циклический ранг, графа — это размерность пространства циклов графа.

Теорема. Цикломатическое число связного графа равно числу хорд любого остовного дерева графа, то есть равно [math]\displaystyle{ m - n + 1 }[/math], где [math]\displaystyle{ m }[/math] — число рёбер графа, [math]\displaystyle{ n }[/math] — число вершин.

Ниже показана таблица сложения по модулю 2 векторов пространства циклов [math]\displaystyle{ \mathcal{C}(G) }[/math] даного графа [math]\displaystyle{ G }[/math], показанного ниже вместе с остовным деревом. Три элемента одного из базисов этого пространства выделены синим.

Остовное дерево и шесть простых циклов данного графа

Остовное дерево графа [math]\displaystyle{ G }[/math]	Шесть простых циклов данного графа. Три элемента одного из базисов выделены синим

Таблица сложения по модулю 2 векторов пространства циклов
[math]\displaystyle{ \oplus }[/math]

Пространство разрезов, или бондов, графа — это подпространство пространства рёбер графа, которое порождается пустым множеством и всеми минимальными разрезами графа. Обозначение пространства бондов графа [math]\displaystyle{ G: \mathcal{B}(G). }[/math]

Другими словами, пространство разрезов натянуто на минимальные разрезы, то есть состоит из:

пустого множества;
всех минимальных разрезов графа;
всех сумм по модулю 2 минимальных разрезов графа.

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

Ранг разрезов графа — это размерность пространства разрезов графа.

Теорема. Ранг разрезов связного графа равен числу рёбер любого остовного дерева графа, то есть равен [math]\displaystyle{ n - 1 }[/math], где [math]\displaystyle{ n }[/math] — число вершин графа.

Ниже показана таблица сложения по модулю 2 векторов пространства разрезов [math]\displaystyle{ \mathcal{B}(G) }[/math] даного графа [math]\displaystyle{ G }[/math], показанного ниже вместе с остовным деревом. Четыре элемента одного из базисов этого пространства выделены синим.

Остовное дерево и десять бондов данного графа [math]\displaystyle{ G }[/math]

Остовное дерево графа [math]\displaystyle{ G }[/math]	Десять бондов (минимальных разрезов) данного графа. Четыре элемента одного из базисов выделены синим

Таблица сложения по модулю 2 векторов пространства разрезов
[math]\displaystyle{ \oplus }[/math]

Применение теории графов

Уже в XIX веке графы применялись при проектировании электрических цепей и молекулярных схем; математические развлечения и головоломки — тоже часть теории графов^[105].

Некоторые задачи теории графов

Задача о кёнигсбергских мостах. Пройти по всем мостам центра старого Кёнигсберга по одному разу. Решена Леонардом Эйлером в публикации, датированной 1736 годом, это первый результат теории графов (первая теорема в той же публикации — сумма степеней вершин графа равна удвоенному числу его рёбер)^[16]^[106]^[12]^[107]^[21]^[108]^[109]^[13]^[110].

Иногда эту задачу переносят на систему мостов других городов. Например, была опубликована задача о 17 мостах устья Невы города Ленинграда 1940 года^[110].

Проблема четырёх красок — можно ли любую карту окрасить в четыре цвета так, чтобы смежные страны имели различные цвета? Сформулирована в 1852 году, в 1977 году опубликовано (анонсировано в 1976) первое общепринятое положительное доказательство с использованием компьютера^[111]^[112]^[113]^[114]^[115]^[116]^[117]^[118].
Задача о домино. Все 28 костей игры в домино должны соединиться в непрерывную (простую) цепь так, чтобы граничащие половинки двух камней имели одно и то же число. Так как наличие дублей задачу не усложняет, задача о домино ставится также для 21 кости (без дублей) без потери общности^[21]^[22]^[119].
Задача о лабиринте. Войти в произвольный лабиринт и пройти по всем его коридорам^[120]^[121].
Задача о трёх домах и трёх колодцах. Проложить непересекающиеся дорожки от каждого из трёх домов к каждому из трёх колодцев. Эта задача, как и задача о кёнигсбергских мостах, решения не имеет^[122].
Задача о ходе коня. Обойти конём шахматную доску, посетив каждую клетку ровно один раз с возвратом на исходную клетку^[123].
Задача о назначениях. Пусть компании требуется несколько различных видов работ, причём каждый сотрудник подходит только для некоторых из них и может выполнять не более одной работы за раз. Как следует распределять задания, чтобы выполнять максимальное количество заданий одновременно? Решить задачу помогает двудольный граф, в котором вершины одной доли — сотрудники, другой — рабочие места, и каждое ребро — подходящее назначение на работу^[124].
Комбинаторная оптимизация^[125].

Задача о кратчайшем пути. Дан (ориентированный) граф и каждый вес его ребра (дуги) представляет время, необходимое для её прохождения. Найти кратчайший путь (по времени) между заданными вершинами.
Задача о минимальном остовном дереве. Пусть нужно соединить несколько компьютеров в фиксированных местах, чтобы сформировать компьютерную сеть, и известна стоимость создания прямого соединения между любой парой компьютеров. Какие прямые соединения следует построить, чтобы стоимость сети была минимальна?
Задача Штейнера о минимальном дереве. Пусть имеется произвольное подмножество вершин связного взвешенного графа. Найти подграф-дерево с минимальной суммой весов рёбер, содержащее все вершины заданного подмножества.
Задача коммивояжёра (TSP). Пусть продавцу нужно посетить несколько городов в течение следующего месяца. Весовые коэффициенты представляют затраты на поездки между каждой парой городов. Как упорядочить визиты так, чтобы свести к минимуму общую стоимость поездки? Другими словами, нужно найти гамильтонов цикл, общий вес рёбер которого минимален.
Задача о максимальном потоке. Пусть вода перекачивается по сети трубопроводов от источника к стоку. Графовая модель — сеть, где каждый вес дуги — верхняя граница потока через соответствующий трубопровод. Найти максимальный поток от источника к стоку.
Задача о китайском почтальоне. Найти минимальный по весу цикл по всем рёбрам в заданном взвешенном графе, где веса рёбер зависит от приложения (например, расстояние, время, стоимость и т. д.).
Задача о китайском почтальоне (орграф). При выполнении поток компьютерной программы перемещается между различными состояниями, и переходы из одного состояния в другое зависят от входных данных. При тестировании программного обеспечения хотелось бы генерировать входные данные так, чтобы были протестированы все возможные переходы.

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

Задача реконструкции РНК. По неупорядоченным фрагментам одной и той же РНК реконструировать эту РНК-цепочку или полное множество подходящих РНК-цепочек.
Задача реконструкции строки цифр. Пусть для данной строки цифр [math]\displaystyle{ f_i }[/math] — число цифр [math]\displaystyle{ i }[/math] в строке, [math]\displaystyle{ f_{ij} }[/math] — число подстрок [math]\displaystyle{ ij }[/math] в строке. Сколько существует различных строк, отвечающих данным [math]\displaystyle{ f_i }[/math] и [math]\displaystyle{ f_{ij} }[/math], [math]\displaystyle{ i, j = 1, 2, \dots, n }[/math], [math]\displaystyle{ f_{ii} = 0 }[/math]?

Задача изоморфности графов. Разработать общий алгоритм для определения изоморфизма графа или, в качестве альтернативы, доказать, что такого алгоритма не существует^[126].
Задача реконструкции графа^[en]. Могут ли два неизоморфных простых графа с тремя или более вершинами и без меток на вершинах иметь одинаковый список подграфов, каждый из которых получен удалением одной вершины^[127]?
Задача о подмножестве системы независимости^[en] с максимальным весом. Пусть для каждого ребра графа задан неотрицательный вес. Найти подмножество системы независимости с максимальной суммой весов его рёбер^[128].
Задача о паросочетании с максимальным весом. Частный случай предыдущей задачи^[129].
Задача о максимизации. Определить в графе максимальное число вершинно независимых путей, соединяющих любую пару першин^[130].
Задача о минимизации. Определить в графе минимальное число вершин, разделяющих любую пару першин^[130].
Задача гомеоморфизма подграфов. Определить, содержит ли первый граф подграф, гомеоморфный второму графу^[131].
Задача о клике — ещё одна NP-полная задача.
Планарность графа — можно ли изобразить граф на плоскости без пересечений рёбер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

К теории графов также относится целый ряд математических проблем, не решённых на сегодняшний день.

Классификации применений теории графов

Классификация применений теории графов по степени отношения к математике^[132]:

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

Классификация применений теории графов по степени материальности взаимодействия^[133]^[134]:

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

Классификация применений теории графов по видам применяемых графов^[135]:

простые графы, то есть не мультиграфы, орграфы или псевдографы;
мультиграфы и псевдографы, но не орграфы;
простые орграфы;
(псевдо)орграфы.

Классификация применений теории графов по видам атрибутов применяемых графов^[136]:

рёбра и вершины применяемого графа не имеют атрибутов;
рёбра применяемого графа имеют атрибуты, вершины не имеют;
вершины применяемого графа имеют атрибуты, рёбра не имеют;
и рёбра, и вершины применяемого графа имеют атрибуты.

Классификация применений теории графов по областям применения.

Классификация проводится по оглавлению второй части книги^[137].

Приложения к экономике и исследованию операций.
Комбинаторные задачи.
Головоломки к игры.
Паросочетания.
Технические приложения.
Естественные науки.
Задачи изучения человека и общества.
Дополнительные приложения.
Потоки в сетях.

Классификация применений теории графов по областям применения.

Классификация проводится по имеющейся научной литературе. Список некоторых областей применения теории графов со ссылками на литературу:

Некоторые применения теории графов

Перед приложением математической силы к задачам реального мира необходимо построить математическую модель задачи. Графы — удивительно универсальный инструмент математического моделирования. Ниже представлены несколько применений теории графов, отличных от задач теории графов^[154].

Комбинаторная оптимизация. Вес ребра — один из наиболее часто используемых атрибутов графов, особенно при комбинаторной оптимизации. Например, вес ребра может представлять:

транспортные расходы;
время в пути;
пространственное расстояние;
потери мощности;
верхние границы потока;
входы и выходы для переходов в конечном автомате.

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

стоимость производства;
интервал времени в теории расписаний;
состояние марковского процесса;
состояние узла в сети соединений.

Модели на простых графах.

Археология. Пусть коллекция артефактов найдена на месте города, который существовал с 1000 года до нашей эры по 1000 год нашей эры. Тогда можно построить граф с вершинами — артефактами, и вершины смежны, когда соответствующие артефакты из одной могилы. Предположим, что артефакты, найденные в одной могиле, имеют перекрывающиеся промежутки времени использования. Если построить интервальный граф, то имеет место распределение подинтервалов исходного интервала (-1000, 1000) (возможно масштабирование), согласующееся с археологической находкой.
Социология. В социальной сети знакомств вершины — люди, а рёбра указывают на то, что соответствующие пары людей знают друг друга. Включение концепции самопознания требует в модели циклы самопознания, которым в графе соответствуют петли.
География. В географической модели вершины графа могут представлять страны (области, штаты), а рёбра — общую границу.
Геометрия. Конфигурация вершин и рёбер любого многогранника в трёхмерном пространстве образует простой граф, который называется его 1-скелетом^[en]. 1-скелеты платоновых тел — регулярные графы.
Проектирование вычислительных машин. Некоторое число процессоров соединяются вместе на одном чипе для многопроцессорного компьютера, который может выполнять параллельные алгоритмы. В графовой модели для такой сети взаимосвязей вершина — отдельный процессор, ребро — прямая связь между двумя процессорами. Спецификация параллельных архитектур иллюстрирует некоторые взаимодействия между теорией графов и абстрактной алгеброй.
Строительство. Двумерный каркас из стальных балок, соединенных шарнирами, которые позволяют каждой балке поворачиваться в плоскости, жёсткий, если ни одна из его балок не может поворачиваться. Проблема определения того, является ли каркас жёстким, может быть сведена к связности в двудольном графе.
Физическая химия. Углеводород — химическая молекула, состоящая из атомов водорода и углерода. Он насыщен, если в нем содержится максимальное число атомов водорода для его атомов углерода. Насыщение происходит, когда присутствуют только простые связи, то есть когда структурная модель углеводорода — простой граф. Атом водорода имеет один электрон всегда 1-валентен в молекуле. Атом углерода 4-валентный и имеет четыре электрона на своей внешней оболочке. Насыщенные углеводороды бутан и изобутан имеют одинаковую химическую формулу [math]\ce{ C4H10 }[/math], но их графы неизоморфны, поэтому они изомеры.
Информатика. Для сети из [math]\displaystyle{ n }[/math] компьютеров существует [math]\displaystyle{ {n\choose 2} = \frac{n^2 - n}{2} }[/math] возможных пар компьютеров, которые могут быть напрямую соединены. Если все пары связаны, то [math]\displaystyle{ n }[/math] компьютеров подключены, но многие из связей не нужны. Если компьютеры соединены минимальным количеством рёбер, то эти рёбра образуют дерево и количество рёбер в дереве на единицу меньше, чем количество вершин.
Юриспруденция. Пусть корпорация ABC разработает и выпустит на рынок компьютерный чип, а вскоре корпорация DEF выпустит на рынок чип с поразительным операционным сходством. Если ABC докажет, что схема DEF — перестройка схемы ABC, то есть что схемы изоморфны, будет основание для иска о нарушении патентных прав. Если ABC будет проверять сохранение структуры для каждого узла чипа DEF, то задача может занять слишком много времени. Знание организации микросхем может сэкономить время.
Теория алгоритмов. Пусть некоторый распределенный алгоритм^[en] работает в сети межсоединений^[en] с архитектурой — массивом [math]\displaystyle{ 8 \times 8 \times 32 }[/math]. И пусть доступная сеть соединений — 13-мерный граф гиперкуба [math]\displaystyle{ Q_{13} }[/math]. Если 13-мерный граф гиперкуба содержит подграф — сетку размером [math]\displaystyle{ 8 \times 8 \times 32 }[/math], то алгоритм можно напрямую перенести в этот гиперкуб.
Информатика. Величины k вершинной k-связности и рёберной k-связности используются в количественной модели живучести сети, которая представляет собой способность сети сохранять соединения между своими узлами после удаления некоторых рёбер или узлов.
Информатика. В сети связи ошибка — разрушение (удаление) вершины или ребра из моделирующего графа. Таким образом, чем выше связность вершин и рёбер, тем надежнее сеть. Чем меньше соединений используется для подключения, тем дешевле сеть. Получаем следующую задачу оптимизации: при k меньшем n найти k-связный n-вершинный граф, имеющий наименьшее число рёбер.
Теория кодирования. Космический аппарат передаёт некоторое закодированное числами изображение, где числа — значения темноты для точек изображения. Преимущество кодирования изображения кодом Грея заключается в том, что если ошибка из-за «космического шума» приводит к неправильному прочтению одной двоичной цифры в числе, то интерпретация этого числа слабо отклонится от истинного значения темноты. Код Грея порядка [math]\displaystyle{ n }[/math] соответствует гамильтонову циклу в графе гиперкуба [math]\displaystyle{ Q_n }[/math].
Проектирование вычислительных машин. Один из методов миниатюризации непланарной электронной сети — нанесение изоляции между плоскими слоями неизолированных проводников, которые соединяют узлы. Размер и стоимость чипа уменьшаются при минимизации количества слоев. Простой подход к проектированию многослойных схем заключается в использовании «совмещённых чертежей отрезков» остовных подграфов, которые индуцируют рёберное разбиение. Это означает, что узлы в каждом слое находятся в одном и том же положении на плоскости, и каждый слой рисуется рёбрами-отрезками.
Теория связи. Минимум радиолокационных станций, необходимых для наблюдения за несколькими стратегическими объектами — число доминирования соответствующего графа.
Транспорт. Пусть стихийное бедствие обрушилось на регион, состоящий из небольших деревень. Вершины графа — деревни в регионе. Ребро указывает на то, что станция скорой медицинской помощи, созданная в одной из деревень, может также обслуживать другую. Тогда минимальное доминирующее множество графа описывает способ обслуживания региона с минимальным количеством станций первой помощи.
Информатика. Рассмотрите задачу размещения ферзей на шахматной доске: каждая клетка доски либо занята ферзём, либо достигается ферзём за один ход. Определение минимального числа ферзей эквивалентно нахождению числа доминирования графа с 64 вершинами, где рёбра соответствует ходам ферзей.

Модели на корневых деревьях.

Базы данных. Многие информационные структуры информатики основаны на деревьях. Каталоги и подкаталоги (или папки и подпапки), содержащие файлы пользователя компьютера, обычно представляются операционной системой в виде вершин корневого дерева.
Базы данных. Двоичные деревья поиска хранят специально упорядоченные данные для эффективного поиска. В частности, если [math]\displaystyle{ n }[/math] вершин двоичного дерева поиска используются соответствующим образом для хранения ключей [math]\displaystyle{ n }[/math] элементов данных, то поиск может быть завершён за время выполнения [math]\displaystyle{ O(\log(n)) }[/math].
Теория алгоритмов. Конструирование больших компьютерных программ, реализующих сложные стратегии принятия решений, часто основано на корневых деревьях.
Базы данных. Корневые деревья используются для хранения информации, организованной по категориям и подкатегориям. Десятичная классификация Дьюи для библиотек является одним из таких примеров.
Лингвистика. Корневое дерево можно использовать для синтаксического анализа предложения на естественном языке.
Теория алгоритмов. Для связного графа с выделенной вершиной дерево кратчайшего пути^[en] как корневое дерево — компактный способ отображения кратчайшего пути от выделенной вершины до любой другой. Поиск в ширину сначала создает дерево кратчайшего пути для невзвешенного графа, а алгоритм Дейкстры создает такое дерево для взвешенного графа.
Информатика. При обходе дерева выражений^[en] результирующее выражение будет отображаться в префиксной, постфиксной или инфиксной нотации в зависимости от того, какой из обходов используется. Для выражения инфикса требуются круглые скобки, которые можно включить в рекурсивный обход по порядку, создав левую круглую скобку в начале каждого обхода поддерева и правую — в конце каждого обхода поддерева.
Теория кодирования. Двоичное дерево можно использовать для построения префиксного кода для заданного набора символов. Для этого конечные вершины двоичного дерева помечаются данными символами, рёбра — 0 и 1 слева направо, тогда кодовое слово будет составлено из меток рёбер на пути от корня к символу.

Модели на раскрашенных графах.

Теория связи. При назначении частоты вещания радиопередатчикам в одном регионе некоторым парам передатчиков требуются разные частоты, чтобы избежать помех. Графовая модель используется для решения задачи минимизации количества назначенных различных частот. Предположим, что если два передатчика находятся на расстоянии менее 100 км друг от друга, они должны транслироваться на разных частотах. Тогда строится граф, вершины которого — передатчики, а рёбра указывают на пары на расстоянии менее 100 км друг от друга. Проблема назначения радиочастот во избежание помех эквивалентна задаче такой раскраски вершин графа, что смежные вершины имеют разные цвета. Минимальное количество частот будет равно минимальному количеству цветов.
Химия. Пусть вершины графа — различные химические вещества, используемые в производственно процессе, рёбра — пара химических веществ, которая может взорваться при смешивании. Тогда хроматическое число графа — минимальное число складских помещений, требующихся для хранения порознь пар взрывоопасных веществ.
Исследование операций. Пусть верины графа — учебные курсы в университете, ребро соединяет два курса тогда и только тогда, когда хотя бы один студент записался на оба курса. Такие курсы не могут проходить одновременно. Тогда хроматическое число графа — минимальное число разнесённых по времени академических часов в расписании занятий, при котором у студентов не возникнет конфликт учебных курсов.
Теория алгоритмов. Пусть верины графа — переменные компьютерной программы, ребро соединяет две переменные, которые могут быть активны одновременно. Тогда хроматическое число графа — минимальное число регистров, необходимых для избежания возможной пробуксовки — состояния постоянного свопинга.
Исследование операций. Пусть верины графа — учебные курсы в университете, ребро соединяет два курса тогда и только тогда, когда хотя бы три студента записались на оба курса. Такие курсы не могут проходить одновременно. Но число разнесённых по времени академических часов в расписании занятий меньше хроматического числа графа, при котором у студентов не возникнет конфликт учебных курсов. Тогда приходится планировать так, чтобы свести к минимуму количество конфликтов. Если рёбрам графа присваивается вес в зависимости от степени нежелательности конфликта, например, ребро связывает учебные курсы одного и того же преподавателя, то надо найти раскраску с общим наименьшим весом рёбер с одноцветными концами.
Проектирование вычислительных машин. Несколько электронных устройств находятся на печатной плате. Соединительные провода, выходящие из устройств, должны быть окрашены по-разному, чтобы их можно было различить. Наименьшее количество требуемых цветов — ребёрное хроматическое число моделирующей сети.

Модели на мультиграфах и псевдографах.

География. В географической модели вершины мультиграфа могут представлять страны (области, штаты), а рёбра — дороги, пересекающие общую границу.
Химия. Например, молекула бензола имеет двойные связи для некоторых пар своих атомов, поэтому она моделируется мультиграфом. Атом углерода имеет валентность 4 и моделируется вершиной мультиграфа степени 4, атом водорода имеет валентность 1 и моделируется вершиной степени 1
Транспорт. Специальная тележка, оснащенная датчиком, ездит по участкам сети железнодорожных путей для поиска дефектов. Можно ли спланировать движение тележки так, чтобы она диагностировала каждый участок путей ровно один раз, а затем вернулась в исходную точку? Проблема эквивалентна определению того, является ли мультиграф эйлеровым.
Проектирование вычислительных машин. Графы случайного обмена^[en] служат моделями для параллельных архитектур, подходящих для выполнения различных распределённых алгоритмов, включая перетасовку карт и быстрое преобразование Фурье. Вершины псевдографа случайного обмена [math]\displaystyle{ SE_n }[/math] являются битовыми строками длины [math]\displaystyle{ n }[/math].
Проектирование вычислительных машин. Компьютер состоит из нескольких модулей и их контактов. Физическое положение модулей определено, и контакты нужно соединить проводами. Контакты небольшого размера, и к любому моет быть прикреплено не более двух проводов. Чтобы свести к минимуму шум и упростить проводку, общая длина провода должна быть минимальна. Требуемую конструкцию даёт гамильтонов путь с минимальным весом.
Транспорт. Каждые выходные частная школа перевозит n детей на m автобусных остановок. Родители встречают своих детей на автобусных остановках. Школе принадлежит k автобусов с разной вместимостью. Как построить маршруты автобусов с минимальной общей стоимостью? Вершины графа — школа и остановки, вес рёбер — расстояния между ними. В каждый автобус можно посадить несколько групп детей, выходящих на разных остановах, так, чтобы не превысить вместимость автобуса. Стоимость автобусного маршрута равна стоимости гамильтонова цикла минимального веса. Таким образом, задача состоит в том, чтобы разбить m автобусных остановок на k подмножеств так, чтобы сумма стоимости маршрутов всех автобусов была минимальна.
Исследование операций. В университете есть несколько преподавателей для чтения нескольких учебных курсов. Требуется рассчитать минимальное количество академических часов в расписании занятий, необходимых для планирования всех курсов, чтобы одновременно не преподавались два раздела одного и того же курса. Строим двудольный граф на долях преподавателей и учебных курсов, рёбра соединяют преподавателей с их курсами (преподаватель может читать разные курсы, и один курс могут читать разные преподаватели). Подбор преподавателей для курсов можно осуществить за некоторый промежуток времени. Если цвет рёбра — академический час в дневном расписании, то окраска рёбер двудольного графа — возможное расписание для разделов курсов. Минимальная окраска рёбер использует наименьшее количество академических часов.

Модели на простых орграфах.

Картография. Карту улиц города можно представить в виде смешанного графа следующим образом. Вершины этого графа — объекты города, а ориентированные и простые рёбра — соответственно улицы с односторонним и двусторонним движением.
Социология. Иерархию можно представить в виде ориентированного дерева. Например, иерархию принятия решений в компании. Графы и орграфы используются для моделирования социальных отношений, а не только физических сетей.
Экология. Взаимоотношения питания между видами растений и животных экосистемы называются пищевой сетью и моделируются простым орграфом. Каждый вид в системе представлен вершиной, а дуги направлены от вида, который питается, к тому виду, которым питается первый вид.
Экономика. В крупных проектах при планировании часто возникают задачи, которые не могут начаться до завершения других. Вершины орграфной модели — задачи, дуга от одной вершины к другой означает, что вторая задача не может начаться до завершения первой задачи. Для упрощения диаграммы не рисуются дуги, получающиеся транзитивностью.
Программирование. Компьютерная программа — набор блоков программирования с соответствующим потоком управления. Орграф — естественная модель для этой декомпозиции: вершина — блок программирования связан, и если управление по последней инструкции одного блока передаётся первой инструкции другого блока, то рисуется дуга из первого блока во второй. Блок-схемы обычно не имеют кратных дуг.
Электротехника. Определить электрический ток в каждой ветви электрической цепи, используя Закон Ома, первое правило Кирхгофа и второе правило Кирхгофа. Эффективная стратегия решения — с помощью остовного дерева найти минимальный набор контуров орграфа, соответствующих уравнений которых достаточно для решения задачи. Фундаментальный базис циклов — основа для пространства циклов, поэтому его соответствующие уравнения составят полный набор линейных алгебраических уравнений и задача будет решена.
Программирование. Пусть на одной машине обрабатывается n заданий. Известно время, необходимое для обработки любого задания после любого другого. Как упорядочить задания, чтобы минимизировать общее время? Рисуем орграф с n вершинами — заданиями и с соответствующими весами дуг. Тогда искомую последовательность заданий даёт гамильтонов путь с минимальным весом.
Экономика. Пусть известна цена на новый автомобиль и рост цены каждый год, прогнозируются годовые эксплуатационные расходы и стоимость перепродажи. Как, начиная с нового автомобиля, минимизировать чистые затраты на владение и эксплуатацию автомобиля? Строим орграф с числом вершин, на 1 больше числа лет эксплуатации, дуги которого идут от меньших годов к большим и имеют вес, равный стоимости покупки нового автомобиля в год начала дуги и его содержания до начала года конца дуги. Проблема сводится к нахождению кратчайшего пути от первой вершины до последней.
Радио. Пейджинговая сеть моделируется орграфом: вершина орграфа — человек, дуга — односторонняя прямая связь от человека к человеку. Чтобы отправить оповещение от человека к человеку, не обязательно иметь прямую связь, должен быть только направленный путь. Транзитивное замыкание орграфа определяет все пары вершин, для которых существует путь из одной вершины в другую.
Программирование. Пусть процедура из нескольких операций выполняется на одной машине, и имеется естественный частичный порядок операций. Линейное расширение^[en] этого набора операций решило бы проблему линейного упорядочения операций на машине.
Экономика. Модель орграфа используется при планировании крупных сложных проектов для достижения двух целей: запланировать мероприятия так, чтобы время завершения проекта было минимально; определить мероприятия, задержка которых приведет к задержке проекта. Если продолжительность каждого мероприятия известна, то для решения этих проблем используют метод критического пути (CPM).

Модели на (псевдо)орграфах.

Цепь Маркова. В марковском процессе вероятность перехода из одного состояния в другое зависит только от текущего состояния. В графовой модели цепи Маркова каждая дуга помечена вероятностью перехода из состояния в начальной вершине в состояние в концевой вершине, и сумма вероятностей на исходящих дугах из каждой вершины равна 1. Диаграмма Маркова — пример взвешенного графа.
Лексический анализ. Исходный код компьютерной программы можно рассматривать как строку символов. Лексический сканер должен сканировать эти символы по одному за раз и распознавать, какие символы «сочетаются», образуя синтаксический токен или лексему. Такой сканер может быть смоделирован с помощью помеченного орграфа. Первая вершина — начальное состояние до сканирования символов. Вторая вершина — состояние принятия, в котором подстрока из отсканированных символов — действительный идентификатор. Третья вершина — состояние отклонения — подстрока отброшена как недопустимый идентификатор. Метки дуг указывают, какие символы вызывают переход из начального состояния в концевое состояние.
Теория игр. Пусть игрок, начиная с 3 долларов, играет в следующую игру. Бросаются две монеты. Если выпадет два орла, то игрок выиграет 3 доллара, иначе потеряет 1 доллар. Игрок играет до тех пор, пока либо не потеряет все деньги, либо будет иметь не менее 5 долларов. Графовая модель — граф цепи Маркова.

Применение эйлерова цикла и задачи о китайском почтальоне.

Теория кодирования. Пусть вращающийся барабан имеет 16 различных секторов. Присвоим 0 или 1 каждому сектору, поместив проводящий материал в некоторые сектора и непроводящий в другие. Затем неподвижными датчиками «считываем» 4-битную строку, соответствующую четырем секторам, попавшим на датчики. Если 16-битовая строка секторов барабана — (2, 4)-последовательность де Брёйна, то положение барабана можно определить по 4-битной подстроке, которую улавливают датчики. Это более экономично, чем 4-битный код в каждом секторе. (2, 4)-последовательность де Брёйна строится с помощью (2, 4)-орграфа де Брёйна.
Городское хозяйство. Орграф — сеть улиц с односторонним движением, жирные дуги — улицы, которые необходимо подмести, вес ребра — время прохождения улицы без подметания, а время, необходимое для подметания улицы, вдвое больше. Какой маршрут минимизирует общее время для подметания всех необходимых улиц, начиная и заканчивая заданной вершиной?
Информатика. Построить плоттером несколько тысяч копий сети, если для построения горизонтального ребра требуется вдвое больше времени, чем для вертикального. Задача маршрутизации плоттера так, чтобы общее время было минимально, моделируется как задача китайского почтальона.
Социология. Пусть некоторые пары в отделе из шести человек должны встретиться конфиденциально в одном и том же конференц-зале. Можно ли организовать конференции из двух человек так, чтобы один из участников каждой конференции (кроме последней) также участвовал в следующей, но никто не участвовал в трёх последовательных конференциях?
Генетика. В цепи РНК (рибонуклеиновой кислоты) каждое звено представляет собой один из четырёх возможных нуклеотидов. При попытке идентифицировать цепь РНК в неизвестном образце существующая технология не позволяет напрямую идентифицировать длинные цепи. Существует метод фрагментации и субфрагментации длинной цепи РНК на идентифицируемые подцепи. Стратегия Хатчинсона^[en] состоит в том, чтобы построить орграф Эйлера, дуги которого помечены фрагментами, так что каждый эйлеров путь соответствует цепочке РНК.
Комбинаторика. Обобщая предыдущее применение в генетике, РНК можно представить как строку номеров нуклеотидов. Пусть для данной строки цифр [math]\displaystyle{ f_i }[/math] — число цифр [math]\displaystyle{ i }[/math] в строке, [math]\displaystyle{ f_{ij} }[/math] — число подстрок [math]\displaystyle{ ij }[/math] в строке. Тогда информация, заложенная в РНК, зависит только от чисел [math]\displaystyle{ f_i }[/math] и [math]\displaystyle{ f_{ij} }[/math], [math]\displaystyle{ i, j = 1, 2, \dots, n }[/math], [math]\displaystyle{ f_{ii} = 0 }[/math]. Для реконструкции строки строим орграф по матрице смежности [math]\displaystyle{ (f_{ij}) }[/math], где вместо [math]\displaystyle{ f_{ii} = 0 }[/math] стоят [math]\displaystyle{ f_i }[/math]. Тогда все различные эйлеровы пути дадут все возможные подходящие строки.

Некоторые алгоритмы теории графов

Алгоритмы представлены в сжатом формате, без подробностей компьютерной реализации. Имеется множество проектов, предлагающих преобразовать алгоритмы в компьютерные программы^[154].

Рекурсивная графическая последовательность. Рекурсивный алгоритм, который определяет, является ли невозрастающая последовательность последовательностью степеней вершин некоторого графа.
Определение изоморфизма графов полным перебором. Два графа изоморфны, если их наборы вершин можно упорядочить так, чтобы их матрицы смежности были идентичны.
Прямой левый обход дерева (NLR). Сначала обходим левое поддерево, вносим в список каждую вершину только при появлении её впервые.
Обратный левый обход дерева (LRN). Сначала обходим левое поддерево, вносим в список каждую вершину только при появлении её в последний раз.
Центрированный левый обход дерева (LNR). Сначала обходим левое поддерево, вносим в список каждую вершину, имеющую левое поддерево, только при её появлении во второй раз, остальные вершины вносим в список при их появлении в первый раз.
Поиск в двоичном дереве поиска. На каждой итерации исключаем либо левое, либо правое поддерево из остальной части поиска в зависимости от того, что целевой ключ соответственно больше или меньше ключа в текущей вершине.
Добавление в двоичное дерево поиска. С итеративной точки зрения двоичный поиск выполняется до тех пор, пока он не завершится на конечной вершине. Затем новый ключ присваивается новой вершине, которая становится левым или правым поддеревом этой конечной вершины в зависимости от сравнения нового ключа с ключом конечной вершины.
Алгоритм Хаффмана. В префиксном коде, который использует более короткие кодовые слова для кодирования более часто встречающихся символов, сообщения обычно требуют меньше битов, чем в коде, который этого не делает. Алгоритм Хаффмана строит именно такой эффективный префиксный код, объединяя в исходном лесу два дерева наименьшего веса в новое дерево.
Добавление в дерево приоритетов^[en]. Сначала добавляют новую вершину на первое свободное место в дереве приоритетов, а затем перемещают её вверх к корню, пока её приоритет не станет меньше или равен приоритету родительской вершины.
Удаление из дерева приоритетов. Сначала удаляемая вершина заменяется вершиной, занимающей крайнее правое место на нижнем уровне дерева приоритетов. Затем эта вершина итеративно стекает вниз, меняясь местами с потомком, имеющим больший приоритет, пока её приоритет не превысит приоритеты обоих потомков.
Кодирование Прюфера. Последовательность Прюфера длиной [math]\displaystyle{ n - 2 }[/math] строится из данного дерева с [math]\displaystyle{ n }[/math] вершинами, занумерованными числами [math]\displaystyle{ 1, 2, \dots, n }[/math], путём удаления вершин, пока не останется [math]\displaystyle{ 2 }[/math] вершины.
Декодирование Прюфера. Закодированное дерево восстанавливается по последовательности Прюфера [math]\displaystyle{ p_1, p_2, \dots, p_{n-2} }[/math] и списку номеров вершин дерева [math]\displaystyle{ 1, 2, \dots, n }[/math].
Построение остовного дерева. Начиная с заданной вершины графа строится остовное дерево с корнем в заданной вершине, используя любую схему поиска новых вершин дерева, смежных со старыми вершинами.
Построение остовного леса. Начиная с заданной вершины каждой компоненты несвязного графа строится остовное дерево текущей компоненты с корнем в заданной вершине, используя любую схему поиска новых вершин дерева, смежных со старыми вершинами.
Поиск в глубину (DFS). Начиная с заданной вершины графа строится дерево поиска следующим образом. На графе выбирается новая вершина, смежная с самой последней обнаруженной вершиной уже построенного дерева. Если это невозможно, происходит возвращение к предыдущей обнаруженной вершине и попытка повторяется. В итоге поиск продвигается вглубь графа (отсюда и название «в глубину»).
Поиск в ширину (BFS). Начиная с заданной вершины графа строится дерево поиска следующим образом. Поиск «разветвляется» от заданной вершины и увеличивает дерево, выбирая смежные ребра с вершинами дерева, расположенными как можно ближе к заданной вершине. В итоге поиск продвигается по ширине графа слоями, равноудалёнными от заданной вершины (отсюда и название «в ширину»).
Минимальное остовное дерево Прима. Ищется остовное дерево связного взвешенного графа с минимальной суммой весов рёбер. Начинаем с любой вершины графа и на каждой итерации строим дерево Прима добавлением новой вершины, соединённой с деревом ребром с минимальным весом.
Кратчайший путь Дейкстры. Ищутся кратчайшие пути от заданной вершины взвешенного графа сразу до всех других вершин. Начинаем с заданной вершины графа и на каждой итерации добавляем к обработанным вершинам новую, соединённую ребром с одной из обработанных вершин и наиболее близкую к заданной вершине.
Применение поиска в глубину.

Поиск мостов. На заданном связном графе ищутся мосты с помощью первого прохода поиска в глубину до первого возврата и стягивания всех рёбер цикла в одну вершину.
Топологическая сортировка. На заданном бесконтурном орграфе производится нумерация вершин, начиная с максимального номера, с помощью первого прохода поиска в глубину до первого возврата и нумерации последней вершины пути текущим максимальным номером с удалением этой вершины из последующих поисков.
Поиск точек сочленения. На заданном связном графе ищутся точки сочленения с помощью поиска в глубину, специальной нумерации вершин дерева поиска в глубину и сравнения этих номеров.
Поиск блоков. Для заданного связного графа ищутся все его блоки. Предыдущий алгоритм используется как подпрограмма.
Алгоритм Тарри^[en] выхода из лабиринта. Никогда не возвращайтесь, если есть альтернатива, и никогда не проходите второй раз в том же направлении. Другими словами, всегда проходите по новому пути, прежде возвратиться, что делает этот алгоритм разновидностью поиска в глубину.
Алгоритм ближайшего соседа в задаче коммивояжёра. Самая простая эвристика TSP — ближайший сосед. Это жадный алгоритм: выбирается самый дешёвый способ отправиться куда-нибудь ещё. Другими словами, алгоритм ближайшего соседа — обход по глубине, при котором выбираются рёбра наименьшего веса.
Алгоритм поиска компонент сильной связности. Алгоритм, использующий поиск в глубину в комбинации с двумя стеками. Стратегия поиска взаимно достижимых вершин состоит в том, чтобы отслеживать, как дуги, не принадлежащие дереву, соединяют его вершины.

Жадный алгоритм решения задачи о подмножестве системы независимости^[en] с максимальном весом. Пусть для каждого ребра графа задан неотрицательный вес, и задана система независимости графа. Перебираем все рёбра графа, начиная с максимального веса, и строим из них подмножество системы независимости с максимальной суммой весов рёбер.
Жадный алгоритм решения задачи о паросочетании с максимальном весом. Частный случай предыдущего алгоритма.
Построение оптимального [math]\displaystyle{ k }[/math]-связного графа с [math]\displaystyle{ n }[/math] вершинами. Фрэнк Харари разработал процедуру построения [math]\displaystyle{ k }[/math]-связного графа Харари [math]\displaystyle{ H_{k, n} }[/math] на [math]\displaystyle{ n }[/math] вершинах, имеющего минимальное количество [math]\displaystyle{ \left \lceil \frac{kn}{2} \right \rceil }[/math] ребер для [math]\displaystyle{ k \geqslant 2 }[/math]. Построение графа Харари [math]\displaystyle{ H_{k, n} }[/math] начинается с [math]\displaystyle{ n }[/math]-циклического графа, вершины которого последовательно пронумерованы числами [math]\displaystyle{ 0, 1, 2, \dots, n - 1 }[/math] по часовой стрелке по периметру. Построение [math]\displaystyle{ H_{k, n} }[/math] зависит от соотношения [math]\displaystyle{ k }[/math] и [math]\displaystyle{ n }[/math] и распадается на три случая.
Построение эйлерова цикла. В связном графе, все вершины которого имеют чётную степень, выбираем любую вершину и считаем её эйлеровым циклом. На каждой итерации добавляем любой цикл из новых рёбер, имеющий с текущим эйлеровым циклом общую вершину.
Построение (2, n)-последовательности де Брёйна. Строим (2, n)-орграф де Брёйна. Выбираем в этом орграфе вершину и строим ориентированный эйлеров цикл орграфа, начиная с выбранной вершины. Последовательно, начиная с выбранной вершины, обходим эйлеров цикл и собираем однобитовые метки дуг графа в последовательность де Брёйна.
Построение цикла почтальона. Прослеживаем рёбра по кратчайшим путям взвешенного связного графа между вершинами нечётной степени. Если все рёбра пути между двумя вершинами нечётной степени дублируются, то степени этих двух вершин становятся чётными, а чётность степени каждой внутренней вершины пути остаётся неизменной.
Алгоритм минимального остовного дерева и его удвоения в задаче коммивояжёра. Находим минимальное остовное дерево. Удваиваем каждое ребро дерева, получаем эйлеров граф. Строим эйлеров цикл. Строим гамильтонов цикл из эйлерова цикла, используя при обрыве эйлерова цикла короткие пути.
Алгоритм минимального остовного дерева и паросочетаний в задаче коммивояжёра. Находим минимальное остовное дерево. Строим эйлеров граф, добавляя к остовному дереву рёбра из некоторого паросочетания. Строим эйлеров цикл. Строим гамильтонов цикл из эйлерова цикла, используя при обрыве эйлерова цикла короткие пути.
Простая проверка планарности двусвязного графа. Алгоритм требует [math]\displaystyle{ O(n^2) }[/math] вычислительных шагов. Сначала рисуем любой цикл двусвязного графа. Затем добавляем циклы до тех пор, пока граф не будет построен (планарный) или рёбрам придётся пересечься (непланарный).
Жадная раскраска вершин. Последовательный алгоритм, который быстро проходит вершины графа в некоторой заданной последовательности и назначает каждой вершине первый доступный цвет. Эта раскраска вряд ли будет минимальной, и маловероятно, что какой-либо алгоритм с полиномиальным временем может выполнить это, поскольку задача вычисления хроматического числа графа NP-полная.
Жадная раскраска вершин с наибольшей степенью. На каждом шаге среди неокрашенных вершин с максимальной степенью выбирается та, которая имеет наибольшее число смежных вершин разных цветов.
Жадная раскраска рёбер. Аналогична жадной раскраске вершин.
Жадная раскраска рёбер максимального паросочетания. На каждом шаге среди неокрашенных рёбер ищется максимальное паросочетание и затем все его рёбра раскрашиваются одним цветом.
Алгоритм Уоршелла поиска транзитивного замыкания. Пусть дан орграф. Вычислительно эффективный алгоритм строит последовательность орграфов таких, что предыдущий орграф — подграф следующего орграфа, а последний орграф — транзитивное замыкание исходного. Следующий орграф получается из предыдущего добавлением дуги при её отсутствии, если есть путь длиной 2 из начальной вершины новой дуги к конечной.
Алгоритм Кана топологической сортировки. Это простой алгоритм построения линейного расширения^[en] частично упорядоченного множества. Идея состоит в том, чтобы всегда выбирать минимальный элемент на каждом шаге алгоритма.
Вычисление самого раннего времени события. На каждой итерации во взвешенном ациклическом орграфе крупного сложного проекта выбирается вершина, в которую не входит ни одна дуга, и значения самого раннего времени её последующих вершин соответственно обновляются. Затем эта вершина удаляется из орграфа, и начинается следующая итерация. Алгоритм вычисляет самые длинные пути от начальной вершины до каждой другой.
Вычисление самого позднего времени события. Аналогичен расчету самого раннего времени события, но выполняется после вычисление самого раннего времени события в обратном направлении от вершины орграфа конца проекта, которая инициализируется самым ранним временем события.

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

См. также

Словарь терминов теории графов

Примечания

↑ Акимов О. Е. Дискретная математика: логика, группы, графы, 2003, с. 238.
↑ ^2,0 ^2,1 ^2,2 Карпов Д. В. Теория графов. 2017 или позже, с. 2—3.
↑ ^3,0 ^3,1 ^3,2 Оре О. Графы и их применение, 1965, с. 6.
↑ Уилсон Р. Введение в теорию графов, 1977, с. 5.
↑ ^5,0 ^5,1 Bondy J. A., Murty U. S. R. Graph Theory, 2008, с. ix.
↑ Басакер Р., Саати Т. Конечные графы и сети, 1974, с. 7.
↑ Bondy J. A., Murty U. S. R. Graph Theory, 2008, с. vii.
↑ ^8,0 ^8,1 Берж К. Теория графов и её применения, 1962, с. 5.
↑ Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов, 1990, с. 3.
↑ Харари Ф., Палмер Э. Перечисление графов, 1977, с. 255.
↑ Кристофдес Н. Теория графов. Алгоритмический подход, 1978, с. 7.
↑ ^12,0 ^12,1 ^12,2 Харари Фрэнк. Теория графов, 2003, с. 13.
↑ ^13,0 ^13,1 Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики, 1996, с. 288.
↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736.
↑ ^15,0 ^15,1 ^15,2 ^15,3 ^15,4 Харари Фрэнк. Теория графов, 2003, с. 13—17.
↑ ^16,0 ^16,1 ^16,2 ^16,3 ^16,4 ^16,5 ^16,6 ^16,7 ^16,8 ^16,9 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 11.
↑ ^17,0 ^17,1 M. Camille Jordan. Sur les assemblages de lignes, 1869.
↑ Романовский И. В. Дискретный анализ, 2003, с. 185.
↑ Gross J. L., Yellen J. Handbook of graph theory, 2004, p. 35.
↑ Sylvester J. J. Chemistry and algebra, 1878, p. 284.
↑ ^21,0 ^21,1 ^21,2 Dénes König. Theorie der endlichen und unendlichen Graphen, 1936, с. 24.
↑ ^22,0 ^22,1 Dénes König. Theory of finite and infinite graphs, 1990, p. 30.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 151—152.
↑ ^24,0 ^24,1 ^24,2 ^24,3 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 12.
↑ Протоколы заседаний Конференции Императорской Академии Наук с 1725 по 1803 года. Том I. 1725—1743, 1897, с. 220—221.
↑ ^26,0 ^26,1 ^26,2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 15.
↑ ^27,0 ^27,1 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 26.
↑ Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 31—32.
↑ ^29,0 ^29,1 Харари Фрэнк. Теория графов, 2003, с. 17.
↑ Харари Фрэнк. Теория графов, 2003, с. 18.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 97—99.
↑ Харари Фрэнк. Теория графов, 2003, с. 126.
↑ ^33,0 ^33,1 Харари Фрэнк. Теория графов, 2003, с. 127—128.
↑ Биографический очерк Харари, 2005.
↑ ^35,0 ^35,1 Харари Фрэнк. Теория графов, 2003, с. 5.
↑ ^36,0 ^36,1 ^36,2 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xi.
↑ ^37,0 ^37,1 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 145.
↑ Dénes König. Theorie der endlichen und unendlichen Graphen, 1936.
↑ Dénes König. Theory of finite and infinite graphs, 1990.
↑ Уилсон Р. Введение в теорию графов, 1977, с. 6.
↑ ^41,0 ^41,1 Харари Фрэнк. Теория графов, 2003, с. 21.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xi—xii.
↑ Акимов О. Е. Дискретная математика: логика, группы, графы, 2003, с. 236—237.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xii.
↑ Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов, 1981, с. 47.
↑ Reinhard Diestel. Graph Theory, 2016, Notes, с. 33.
↑ Дистель Р. Теория графов, 2002, с. 43.
↑ Кормен Т. Х. и др. Алгоритмы: построение и анализ, 2009, с. 608.
↑ ^49,0 ^49,1 ^49,2 ^49,3 Оре О. Графы и их применение, 1965, с. 15—19.
↑ Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 39.
↑ Зыков А. А. Основы теории графов, 2004, с. 512—517.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, p. 469.
↑ Берж К. Теория графов и её применения, 1962, с. 7.
↑ Reinhard Diestel. Graph Theory, 2016, p. 1.
↑ Дистель Р. Теория графов, 2002, с. 15.
↑ Харари Фрэнк. Теория графов, 2003, с. 21—22, 27—28, 31—32.
↑ Reinhard Diestel. Graph Theory, 2016, 1.1—1.2, 1.6, 1.10.
↑ Дистель Р. Теория графов, 2002, 1.1—1.2, 1.6, 1.10.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение G — от англ. graph и нем. Graph — граф, V — англ. vertex — вершина, E — англ. edge — ребро.
↑ Татт У. Теория графов, 1988, с. 16.
↑ Басакер Р., Саати Т. Конечные графы и сети, 1974, с. 11.
↑ ^62,0 ^62,1 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 5. Обозначение K — от нем. komplett — полный.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение deg — от англ. degree — степень.
↑ Харари Фрэнк. Теория графов, 2003, с. 23—24.
↑ Reinhard Diestel. Graph Theory, 2016, 1.1, 1.10.
↑ Дистель Р. Теория графов, 2002, 1.1, 1.10.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение G — от англ. graph и нем. Graph — граф, V — англ. vertex — вершина, E — англ. edge — ребро.
↑ Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 21. Обозначение D — от англ. direct — направлять.
↑ Харари Фрэнк. Теория графов, 2003, с. 26—27, 83—84.
↑ Reinhard Diestel. Graph Theory, 2016, 1.3—1.4, 1.8.
↑ Дистель Р. Теория графов, 2002, 1.3—1.4, 1.8.
↑ Харари Фрэнк. Теория графов, 2003, с. 48—51.
↑ Reinhard Diestel. Graph Theory, 2016, 1.5.
↑ Дистель Р. Теория графов, 2002, 1.5.
↑ Reinhard Diestel. Graph Theory, 2016, Annotation.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 2.
↑ Дистель Р. Теория графов, 2002, Глава 2.
↑ ^78,0 ^78,1 Дистель Р. Теория графов, 2002, Глава 3.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 3.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 1.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 4.
↑ Дистель Р. Теория графов, 2002, Глава 4.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 5.
↑ Дистель Р. Теория графов, 2002, Глава 5.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 6.
↑ Дистель Р. Теория графов, 2002, Глава 6.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 7.
↑ Дистель Р. Теория графов, 2002, Глава 7.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 8.
↑ Харари Фрэнк. Теория графов, 2003, с. 28—30.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 9.
↑ Дистель Р. Теория графов, 2002, Глава 9.
↑ Харари Фрэнк. Теория графов, 2003, с. 85—88.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 10.
↑ Дистель Р. Теория графов, 2002, Глава 10.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 11.
↑ Дистель Р. Теория графов, 2002, Глава 11.
↑ Алон Н., Спенсер Дж. Вероятностный метод, 2013, 1.1. Вероятностный метод.
↑ Reinhard Diestel. Graph Theory, 2016, Chapter 12.
↑ Дистель Р. Теория графов, 2002, Глава 12.
↑ Reinhard Diestel. Graph Theory, 2016, 1.9.
↑ Дистель Р. Теория графов, 2002, 1.9.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, p. 197.
↑ Харари Фрэнк. Теория графов, 2003, с. 54—56.
↑ Оре О. Графы и их применение, 1965, с. 9.
↑ Дистель Р. Теория графов, 2002, с. 33—34.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 248—249.
↑ Оре О. Графы и их применение, 1965, с. 33.
↑ Оре О. Теория графов, 1980, с. 53.
↑ ^110,0 ^110,1 Одним росчерком, 1940.
↑ Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 89—90.
↑ Дистель Р. Теория графов, 2002, с. 139—140.
↑ Харари Фрэнк. Теория графов, 2003, с. 17—18.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 371.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, В этой книге проблема четырёх красок не упоминается.
↑ Оре О. Графы и их применение, 1965, с. 143—144.
↑ Оре О. Теория графов, 1980, с. 9.
↑ Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики, 1996, с. 290—292.
↑ Перельман Я. И. Живая математика, 1967, с. 24.
↑ Оре О. Теория графов, 1980, с. 66.
↑ Dénes König. Theorie der endlichen und unendlichen Graphen, 1936, III. Kapitel. Das Labyrinthenproblem..
↑ Оре О. Графы и их применение, 1965, с. 22.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 272.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 22.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 48—50, 176—179.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 64.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 83.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 208.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 209.
↑ ^130,0 ^130,1 Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 232.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 295.
↑ Харари Фрэнк. Теория графов, 2003, с. 1.
↑ Gross J. L., Yellen J. Handbook of graph theory, 2004, с. 9.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 1.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 22—26.
↑ Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 48—26.
↑ Басакер Р., Саати Т. Конечные графы и сети, 1974, Часть II. Приложения теории графов.
↑ Каменецкий И. С., Маршак Б. И., Шер Я. А. Анализ археологических источников: Возможности формализованного подхода, 2013.
↑ Шалыто А. А. Алгоритмизация и программирование задач логического управления, 1998.
↑ Nils J. Nilsson. Artificial intelligence and a new synthesis, 1998.
↑ Мелихов А. Н. Ориентированные графы и конечные автоматы, 1971.
↑ Лубенцова В. С. Математические модели и методы в логистике, 2008.
↑ Евстигнеев В. А. Применение теории графов в программировании, 1985.
↑ Паниотто В. И. Структура межличностных отношений : методика и математические методы исследования, 1975.
↑ Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР, 1990.
↑ Кормен Т. Х. и др. Алгоритмы: построение и анализ, 2009.
↑ Теория графов и сетей при моделировании процессов УВД, 2009.
↑ Маджидов Т. И., Баскин И. И., Антипин И. С., Варнек А. А. Введение в хемоинформатику, 2013—2016.
↑ Яблонский Г. С., Быков В. И., Горбань А. Н. Кинетические модели каталитических реакций, 1983.
↑ Химические приложения топологии и теории графов, 1987.
↑ Деза М. М., Сикирич М. Д. Геометрия химических графов: полициклы и биполициклы, 2013.
↑ Chemical graph theory : introduction and fundamentals, 1991.
↑ Фомин Г. П. Математические методы и модели в коммерческой деятельности, 2009.
↑ ^154,0 ^154,1 Gross J. L., Yellen J. Graph theory and its applications, 2006.

Литература

Акимов О. Е. Дискретная математика: логика, группы, графы. 2-е изд., доп. М.: Лаборатория Базовых Знаний, 2003. 376 с.: ил. ISBN 5-93208-025-6.
Алон Н., Спенсер Дж. Вероятностный метод / Пер. 2-го англ. изд. М.: БИНОМ. Лаборатория знаний, 2013. 320 с., ил. ISBN 978-5-9963-1316-7.
Басакер Р., Саати Т. Конечные графы и сети / Пер. с английского В. Н. Буркова, С. Е. Ловецкого, В. Б. Соколова. Под ред А. И. Теймана. М.: Наука, 1974. 366 с., ил.
Берж К. Теория графов и её применения / Пер. с французского А. А. Зыкова. М.: Изд-во иностранной литературы, 1962. 319 с., ил.
Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики. М.: Просвещение, 1996. 320 с., ил. ISBN 5-09-006575-6.
Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 366 с., ил.
Деза М. М., Сикирич М. Д. Геометрия химических графов: полициклы и биполициклы. М.—Ижевск: Изд-во Института компьютерных исследований, 2013. 384 с., ил. ISBN 978-5-4344-0130-2.
Дистель Р. Теория графов / Пер. с англ. Новосибирск: Изд-во Института математики, 2002. 225 с., ил. ISBN 5-86134-101-Х.
Евстигнеев В. А. Применение теории графов в программировании / Под ред. А. П. Ершова. М.: Наука, 1985. 352 с., ил.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов / Под ред. А. П. Ершова. М.: Наука, 1990. 383 с., ил. ISBN 5-02-013992-0.
Зыков А. А. Основы теории графов. М.: Вузовская книга, 2004. 662 с.: ил. ISBN 5-9502-0057-8.
Каменецкий И. С., Маршак Б. И., Шер Я. А. Анализ археологических источников: Возможности формализованного подхода. Изд. 2-е. М.: ИА РАН, 2013. 182 с.: ил. ISBN 978-5-94375-153-0.
Карпов Д. В. Теория графов. 2017 или позже. 555 с., ил.
Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. : Пер. с англ. М.: Издательский дом «Вильямс», 2009. 1290 с., ил. ISBN 978-5-8459-0857-5 (рус.). ISBN 0-07-013151-1 (англ.).
Кристофдес Н. Теория графов. Алгоритмический подход. Пер. с англ. Э. В. Вершкова и И. В. Коновальцева. Под. ред. Г. П. Гаврилова. М.: Мир, 1978. 432 с., ил.
Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 214 с., ил. ISBN 5-256-00748-3.
Лубенцова В. С. Математические модели и методы в логистике / Под ред. В. П. Радченко. Самара: Изд-во Самарского государственного технического университета, 2008. 157 с.: ил. ISBN 978-5-7964-1140-7.
Маджидов Т. И., Баскин И. И., Антипин И. С., Варнек А. А. Введение в хемоинформатику. Части 1—4. Казань: Изд-во Казанского университета, 2013—2016.
Мелихов А. Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971. 416 с., ил.
Одним росчерком. Вычерчивание фигур одной непрерывной линией / Сост. Я. И. Перельман. Л.: Дом занимательной науки, 1940. С 17 рис.
Оре О. Графы и их применение / Пер. с англ. Л. И. Головиной. Под ред. И. М. Яглома. М.: Мир, 1965. 174 с.: ил.
Оре О. Теория графов. 2-е изд. стереотип. / Пер. с англ. И. Н. Врублевской. Под ред. Н. Н. Воробьева. М.: Наука, 1980. 336 с.: ил.
Паниотто В. И. Структура межличностных отношений : методика и математические методы исследования. Киев: Наукова думка, 1975. 124 с., ил.
Перельман Я. И. Живая математика. Математические рассказы и головоломки. Изд. 8, перераб. и доп. / Под ред. и с доп. В. Г. Болтянского. М.: Наука, 1967. 160 с. с илл.
Протоколы заседаний Конференции Императорской Академии Наук с 1725 по 1803 года. Том I. 1725—1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Tome I. 1725—1743. С.-Петербург: Типография ИАН, 1897. 883 с.
Романовский И. В. Дискретный анализ. 3-е изд., перераб. и доп. СПб.: Невский Диалект; БХВ-Петербург, 2003. 320 с.: ил. ISBN 5-7940-0114-3. ISBN 5-94157-330-8.
Татт У. Теория графов / Пер. с англ. Г. П. Гаврилова. М.: Мир, 1988. 424 с., ил. ISBN 5-03-001001-7.
Теория графов и сетей при моделировании процессов УВД : Учеб. пособие / Сост. В. А. Карнаухов. Ульяновск: УВАУ ГА(И), 2009. 63 с.
Уилсон Р. Введение в теорию графов / Пер. с англ. И. Г. Никитиной. Под ред. Г. П. Гаврилова. М.: Мир, 1977. 207 с.: ил.
Фляйшнер Г. Эйлеровы графы и смежные вопросы / Пер. с англ. В. А. Евстигнеева, А. В. Косточки и Л. С. Мельникова. Под ред. Л. С. Мельникова. М.: Мир, 2002. 335 с.: ил. ISBN 5-03-003115-4 (рус.). ISBN 0-444-88395-9 (англ.). [Fleischner H. Eulerian Graphs and Related Topics. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
Фомин Г. П. Математические методы и модели в коммерческой деятельности: учебник. 3-е изд., перераб. и доп. М.: Финансы и статистика; ИНФРА-М, 2009. 637 с.: ил. ISBN 978-5-279-03353-9 (Финансы и статистика). ISBN 978-5-16-003660-1 (ИНФРА-М).
Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов: Учебное пособие / Пер. с нем. Е. Е. Перегуда; Пол ред. С. В. Мациевского. Калининград: Изд-во РГУ им. И. Канта, 2008. 204 с.: ил. ISBN 978-5-88874-880-0.
Харари Фрэнк. Теория графов / Пер. с англ. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд-е 2-е. М.: Едиториал УРСС, 2003. 296 с.: ил. ISBN 5-354-00301-6.
Харари Ф., Палмер Э. Перечисление графов / Пер. с англ. Г. П. Гаврилова. М.: Мир, 1977. 324 с.: ил.
Химические приложения топологии и теории графов / Пер. с англ. Под ред. Р. Кинга. М.: Мир, 1987. 560 с.: ил.
Шалыто А. А. Алгоритмизация и программирование задач логического управления. СПб.: СПбГУ ИТМО, 1998. 56 с., ил.
Яблонский Г. С., Быков В. И., Горбань А. Н. Кинетические модели каталитических реакций. Новосибирск: Наука, 1983. 253 с.: ил. ISBN 5-354-00301-6.
Bondy J. A., Murty U. S. R. Graph Theory. Springer, 2008. 651 p. ISSN 0072-5285. ISBN 978-1-84628-969-9. e-ISBN 978-1-84628-970-5. DOI 10.1007/978-1-84628-970-5.
Chemical graph theory : introduction and fundamentals / edited by D. Bonchev and D. Rouvray. New York: Abacus Press, 1991. ISBN 0-85626-454-7.
M. Camille Jordan. Sur les assemblages de lignes // J. Reine Angew. Math. 1869. Vol. 70. P. 185—190.
Reinhard Diestel. Graph Theory. GTM 173, 5th edition 2016/17. Springer-Verlag, Heidelberg. Graduate Texts in Mathematics, Volume 173. ISBN 978-3-662-53621-6.
Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140.
Gross J. L., Yellen J. Graph theory and its applications. Second edition. Boca Raton–London–New York: Chapman & Hall/CRC, 2006.
Gross J. L., Yellen J. Handbook of graph theory. CRC Press, 2004. ISBN 978-1-58488-090-5. P. 35.
Frank Harary. Биографический очерк на сайте ACM SIGACT от 4 января 2005 года.
Dénes König. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft M. B. H., 1936.
Dénes König. Theory of finite and infinite graphs. Boston: Birkhäuser, 1990.
Nils J. Nilsson. Artificial intelligence and a new synthesis. San Francisco, California: Morgan Kaufmann Publishes, Inc., 1998. 535 p. ISBN 1-55860-467-7 (cloth). ISBN 1-55860-535-5 (paper).
J. J. Sylvester (February 7, 1878) "Chemistry and algebra," Nature, 17 : 284. doi:10.1038/017284a0.

Ссылки

Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c. http://vuz.exponenta.ru/PDF/book/GrMaple.pdf http://eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
Сергей Мельников. Сим и Крэм под «электронным микроскопом» (рус.) // Наука и жизнь. — 1996. — Вып. 3. — С. 144—145. В статье идёт речь об игре на графе Сим, придуманной Густавом Симмонсом.
WikiGrapp — толковый словарь по теории графов
Алгоритмы и краткие описания программ на C++
Дискретная математика, алгоритмы, апплеты, визуализация графов
Intelligent Graph Visualizer (автоматическое размещение на плоскости, поиск кратчайшего пути, поиск центра и др.)
Graph Theory Software
Visual Graph: программа, предоставляющая пользователю, широкий набор средств и методов для визуализации и поиска информации в графах

[_6324b9d880fa1370-1] Акимов О. Е. Дискретная математика: логика, группы, графы, 2003, с. 238.

[_ecc3ea6527267b93-2] 2,0 ^2,1 ^2,2 Карпов Д. В. Теория графов. 2017 или позже, с. 2—3.

[_40a8d623d4da35e2-3] 3,0 ^3,1 ^3,2 Оре О. Графы и их применение, 1965, с. 6.

[_394bbcf279aa032a-4] Уилсон Р. Введение в теорию графов, 1977, с. 5.

[_fb90e4c2d6e79cdd-5] 5,0 ^5,1 Bondy J. A., Murty U. S. R. Graph Theory, 2008, с. ix.

[_9e8b87059f90f6ed-6] Басакер Р., Саати Т. Конечные графы и сети, 1974, с. 7.

[_f9f3badcb7449fac-7] Bondy J. A., Murty U. S. R. Graph Theory, 2008, с. vii.

[_57e0bd47567ef789-8] 8,0 ^8,1 Берж К. Теория графов и её применения, 1962, с. 5.

[_b8178190f68b5538-9] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов, 1990, с. 3.

[_de5459c85de6a8e8-10] Харари Ф., Палмер Э. Перечисление графов, 1977, с. 255.

[_8fc89966c8773f30-11] Кристофдес Н. Теория графов. Алгоритмический подход, 1978, с. 7.

[_08382cdb1d0bb9ae-12] 12,0 ^12,1 ^12,2 Харари Фрэнк. Теория графов, 2003, с. 13.

[_a2663831c3615e1c-13] 13,0 ^13,1 Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики, 1996, с. 288.

[_077379f1e34a3979-14] Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736.

[_0e0f9a1a17c7e9d4-15] 15,0 ^15,1 ^15,2 ^15,3 ^15,4 Харари Фрэнк. Теория графов, 2003, с. 13—17.

[_de73563d3dd42675-16] 16,0 ^16,1 ^16,2 ^16,3 ^16,4 ^16,5 ^16,6 ^16,7 ^16,8 ^16,9 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 11.

[_1e7adfb39d405dff-17] 17,0 ^17,1 M. Camille Jordan. Sur les assemblages de lignes, 1869.

[_eee100f96011c06e-18] Романовский И. В. Дискретный анализ, 2003, с. 185.

[_97bad9b9e51b34ca-19] Gross J. L., Yellen J. Handbook of graph theory, 2004, p. 35.

[_43300661fe48d513-20] Sylvester J. J. Chemistry and algebra, 1878, p. 284.

[_2635818073430232-21] 21,0 ^21,1 ^21,2 Dénes König. Theorie der endlichen und unendlichen Graphen, 1936, с. 24.

[_7e19330461db3388-22] 22,0 ^22,1 Dénes König. Theory of finite and infinite graphs, 1990, p. 30.

[_be481ec81454ccf4-23] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 151—152.

[_e8d0d13d442f6d98-24] 24,0 ^24,1 ^24,2 ^24,3 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 12.

[_cdc91c912c0412ac-25] Протоколы заседаний Конференции Императорской Академии Наук с 1725 по 1803 года. Том I. 1725—1743, 1897, с. 220—221.

[_01f2c23d522ceb59-26] 26,0 ^26,1 ^26,2 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 15.

[_bdaf99551d9956db-27] 27,0 ^27,1 Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 26.

[_4c0ca547863f4072-28] Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 31—32.

[_2c9018db321b95f2-29] 29,0 ^29,1 Харари Фрэнк. Теория графов, 2003, с. 17.

[_e04dc5db07653577-30] Харари Фрэнк. Теория графов, 2003, с. 18.

[_e546852d2b52b8c7-31] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 97—99.

[_6974e25cd35c6969-32] Харари Фрэнк. Теория графов, 2003, с. 126.

[_ecf5c6e084e14339-33] 33,0 ^33,1 Харари Фрэнк. Теория графов, 2003, с. 127—128.

[_132d50f45f772865-34] Биографический очерк Харари, 2005.

[_6542a4c77c773f49-35] 35,0 ^35,1 Харари Фрэнк. Теория графов, 2003, с. 5.

[_f1f2b2c8223bee76-36] 36,0 ^36,1 ^36,2 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xi.

[_f09f28402809e17f-37] 37,0 ^37,1 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 145.

[_ca6e45e0b3920988-38] Dénes König. Theorie der endlichen und unendlichen Graphen, 1936.

[_dc00d5fc48c24087-39] Dénes König. Theory of finite and infinite graphs, 1990.

[_593aadf28d6f87eb-40] Уилсон Р. Введение в теорию графов, 1977, с. 6.

[_e52124e4283603c3-41] 41,0 ^41,1 Харари Фрэнк. Теория графов, 2003, с. 21.

[_20f3c9e9d65b7182-42] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xi—xii.

[_3c0c37de762631c8-43] Акимов О. Е. Дискретная математика: логика, группы, графы, 2003, с. 236—237.

[_41ebfd0fd913bc95-44] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. xii.

[_4edc53781d284f88-45] Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов, 1981, с. 47.

[_97f16214ea194fa3-46] Reinhard Diestel. Graph Theory, 2016, Notes, с. 33.

[_b146dc6fe80eefcb-47] Дистель Р. Теория графов, 2002, с. 43.

[_8dd579c1e3d8649c-48] Кормен Т. Х. и др. Алгоритмы: построение и анализ, 2009, с. 608.

[_5bcdee4aea38910a-49] 49,0 ^49,1 ^49,2 ^49,3 Оре О. Графы и их применение, 1965, с. 15—19.

[_aeccae4c890d3f1b-50] Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 39.

[_98b86f234c672a54-51] Зыков А. А. Основы теории графов, 2004, с. 512—517.

[_46be7e52864f3b3e-52] Gross J. L., Yellen J. Graph theory and its applications, 2006, p. 469.

[_6d80cb4763f674c3-53] Берж К. Теория графов и её применения, 1962, с. 7.

[_22748d67e817e951-54] Reinhard Diestel. Graph Theory, 2016, p. 1.

[_f9f500581df043dc-55] Дистель Р. Теория графов, 2002, с. 15.

[_f82759ca0fc595c3-56] Харари Фрэнк. Теория графов, 2003, с. 21—22, 27—28, 31—32.

[_7402404ae8efc390-57] Reinhard Diestel. Graph Theory, 2016, 1.1—1.2, 1.6, 1.10.

[_17c0ac72938424e2-58] Дистель Р. Теория графов, 2002, 1.1—1.2, 1.6, 1.10.

[_7dca217ea5e4c814-59] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение G — от англ. graph и нем. Graph — граф, V — англ. vertex — вершина, E — англ. edge — ребро.

[_2dec5309d6ee1c98-60] Татт У. Теория графов, 1988, с. 16.

[_7966e6c1b942fd9a-61] Басакер Р., Саати Т. Конечные графы и сети, 1974, с. 11.

[_99e9f63d726c78fc-62] 62,0 ^62,1 Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 5. Обозначение K — от нем. komplett — полный.

[_147a720cb11b4378-63] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение deg — от англ. degree — степень.

[_bfb534bf82aa2e03-64] Харари Фрэнк. Теория графов, 2003, с. 23—24.

[_dea690bca4f9d9c4-65] Reinhard Diestel. Graph Theory, 2016, 1.1, 1.10.

[_b1baba2719b84bde-66] Дистель Р. Теория графов, 2002, 1.1, 1.10.

[_704474448bb192a0-67] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 2. Обозначение G — от англ. graph и нем. Graph — граф, V — англ. vertex — вершина, E — англ. edge — ребро.

[_d3dd86590522c02a-68] Фрич Р., Перегуд Е. Е., Мациевский С. В. Избранные главы теории графов, 2008, с. 21. Обозначение D — от англ. direct — направлять.

[_8db245929c6633a8-69] Харари Фрэнк. Теория графов, 2003, с. 26—27, 83—84.

[_9633aa82ad5371fc-70] Reinhard Diestel. Graph Theory, 2016, 1.3—1.4, 1.8.

[_140d303b21b6b1b6-71] Дистель Р. Теория графов, 2002, 1.3—1.4, 1.8.

[_97f3bf51f24da91e-72] Харари Фрэнк. Теория графов, 2003, с. 48—51.

[_9b70b36731bfc2c2-73] Reinhard Diestel. Graph Theory, 2016, 1.5.

[_0fce657befa6c270-74] Дистель Р. Теория графов, 2002, 1.5.

[_46100ada466006a1-75] Reinhard Diestel. Graph Theory, 2016, Annotation.

[_627b778dbfe511e3-76] Reinhard Diestel. Graph Theory, 2016, Chapter 2.

[_0923fa2b7ebacba6-77] Дистель Р. Теория графов, 2002, Глава 2.

[_144d5d2b85c34e6d-78] 78,0 ^78,1 Дистель Р. Теория графов, 2002, Глава 3.

[_5e04e48dbe8f2cfc-79] Reinhard Diestel. Graph Theory, 2016, Chapter 3.

[_4880068db12ec8e2-80] Reinhard Diestel. Graph Theory, 2016, Chapter 1.

[_2f4e7d8da3225785-81] Reinhard Diestel. Graph Theory, 2016, Chapter 4.

[_3c35c42b9b666cc4-82] Дистель Р. Теория графов, 2002, Глава 4.

[_2bcb9a8da29aa21e-83] Reinhard Diestel. Graph Theory, 2016, Chapter 5.

[_46a0d72ba1cd3f8b-84] Дистель Р. Теория графов, 2002, Глава 5.

[_44ee8b8db099d4df-85] Reinhard Diestel. Graph Theory, 2016, Chapter 6.

[_2d7ce62b93cc5aca-86] Дистель Р. Теория графов, 2002, Глава 6.

[_3a85788daa3667e8-87] Reinhard Diestel. Graph Theory, 2016, Chapter 7.

[_31da492b950e8cb1-88] Дистель Р. Теория графов, 2002, Глава 7.

[_0bd0118d8ecb45b1-89] Reinhard Diestel. Graph Theory, 2016, Chapter 8.

[_4e0b3d652db4e179-90] Харари Фрэнк. Теория графов, 2003, с. 28—30.

[_0772ae8d8d8913ca-91] Reinhard Diestel. Graph Theory, 2016, Chapter 9.

[_6af8c32bb6dd1bdf-92] Дистель Р. Теория графов, 2002, Глава 9.

[_bd5e81b84565cd05-93] Харари Фрэнк. Теория графов, 2003, с. 85—88.

[_59289ec80590939a-94] Reinhard Diestel. Graph Theory, 2016, Chapter 10.

[_b51cdc023ef12c25-95] Дистель Р. Теория графов, 2002, Глава 10.

[_5cab81c806184701-96] Reinhard Diestel. Graph Theory, 2016, Chapter 11.

[_aacdf90238a326be-97] Дистель Р. Теория графов, 2002, Глава 11.

[_e4de8fcb010ec122-98] Алон Н., Спенсер Дж. Вероятностный метод, 2013, 1.1. Вероятностный метод.

[_6706fcc80c702754-99] Reinhard Diestel. Graph Theory, 2016, Chapter 12.

[_c3f1ea0246a40a7f-100] Дистель Р. Теория графов, 2002, Глава 12.

[_2f406f66f3459286-101] Reinhard Diestel. Graph Theory, 2016, 1.9.

[_7532a97c285aa1bc-102] Дистель Р. Теория графов, 2002, 1.9.

[_ab0aac54d4ee8ce0-103] Gross J. L., Yellen J. Graph theory and its applications, 2006, p. 197.

[_7393f3ae0b5203e4-104] Харари Фрэнк. Теория графов, 2003, с. 54—56.

[_f5400323aadca0a7-105] Оре О. Графы и их применение, 1965, с. 9.

[_244972ffbd603559-106] Дистель Р. Теория графов, 2002, с. 33—34.

[_95824a65c30d28d6-107] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 248—249.

[_e0ada5cec90fae0e-108] Оре О. Графы и их применение, 1965, с. 33.

[_1f9b945cd9f08a5c-109] Оре О. Теория графов, 1980, с. 53.

[_cc5eae7d065ea385-110] 110,0 ^110,1 Одним росчерком, 1940.

[_17d904b81e5abaf7-111] Фляйшнер Г. Эйлеровы графы и смежные вопросы, 2002, с. 89—90.

[_5de1484809a626b0-112] Дистель Р. Теория графов, 2002, с. 139—140.

[_e553046a40ee9739-113] Харари Фрэнк. Теория графов, 2003, с. 17—18.

[_8dc97c59ea7cd486-114] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 371.

[_4033842092bfeaab-115] Gross J. L., Yellen J. Graph theory and its applications, 2006, В этой книге проблема четырёх красок не упоминается.

[_3de620f22614cb8b-116] Оре О. Графы и их применение, 1965, с. 143—144.

[_d97f3d718df7b947-117] Оре О. Теория графов, 1980, с. 9.

[_22d35115d0b3dc1e-118] Виленкин Н. Я., Шибасов Л. П., Шибасова З. Ф. За страницами учебника математики, 1996, с. 290—292.

[_475addd33fee389f-119] Перельман Я. И. Живая математика, 1967, с. 24.

[_3c917f446708c260-120] Оре О. Теория графов, 1980, с. 66.

[_cf8bc7262a86da22-121] Dénes König. Theorie der endlichen und unendlichen Graphen, 1936, III. Kapitel. Das Labyrinthenproblem..

[_579ee8c5ef0f5308-122] Оре О. Графы и их применение, 1965, с. 22.

[_e212515c9dcf75b8-123] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 272.

[_7720d8c155bd2519-124] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 22.

[_a222d1cf252ca64f-125] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 48—50, 176—179.

[_2ea2a2a01d44e07b-126] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 64.

[_d3738214c4b72a6c-127] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 83.

[_1686779802f01fe1-128] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 208.

[_0c379497fca2187a-129] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 209.

[_4b1aa17d5834fd04-130] 130,0 ^130,1 Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 232.

[_e31fc24d374406fb-131] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 295.

[_47b5b8c76d2c0225-132] Харари Фрэнк. Теория графов, 2003, с. 1.

[_cbfe8c3be93f7153-133] Gross J. L., Yellen J. Handbook of graph theory, 2004, с. 9.

[_89deac23c3cb0834-134] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 1.

[_92bdd23a3eef7f19-135] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 22—26.

[_3ee6ad09a020cf15-136] Gross J. L., Yellen J. Graph theory and its applications, 2006, с. 48—26.

[_1600047b5a15fb1a-137] Басакер Р., Саати Т. Конечные графы и сети, 1974, Часть II. Приложения теории графов.

[_331ba559a7889d6a-138] Каменецкий И. С., Маршак Б. И., Шер Я. А. Анализ археологических источников: Возможности формализованного подхода, 2013.

[_30525c9ee35b3c03-139] Шалыто А. А. Алгоритмизация и программирование задач логического управления, 1998.

[_e8e4ab6c0d8243dd-140] Nils J. Nilsson. Artificial intelligence and a new synthesis, 1998.

[_e3ded4bd9671184b-141] Мелихов А. Н. Ориентированные графы и конечные автоматы, 1971.

[_21f4001ea0672eda-142] Лубенцова В. С. Математические модели и методы в логистике, 2008.

[_c966b01e85fe8ebd-143] Евстигнеев В. А. Применение теории графов в программировании, 1985.

[_f5f4cf0505b3fae5-144] Паниотто В. И. Структура межличностных отношений : методика и математические методы исследования, 1975.

[_f42d861fc60e4a71-145] Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР, 1990.

[_65915301f2f0cbce-146] Кормен Т. Х. и др. Алгоритмы: построение и анализ, 2009.

[_b7a1dceaa34a0c24-147] Теория графов и сетей при моделировании процессов УВД, 2009.

[_d122b394fb3e5535-148] Маджидов Т. И., Баскин И. И., Антипин И. С., Варнек А. А. Введение в хемоинформатику, 2013—2016.

[_0be0d6443bc3d431-149] Яблонский Г. С., Быков В. И., Горбань А. Н. Кинетические модели каталитических реакций, 1983.

[_77da990e12f3f6a4-150] Химические приложения топологии и теории графов, 1987.

[_330ade5566ca5b07-151] Деза М. М., Сикирич М. Д. Геометрия химических графов: полициклы и биполициклы, 2013.

[_2bf0f61a49b7c35f-152] Chemical graph theory : introduction and fundamentals, 1991.

[_8ce1b7c0fe2a66fd-153] Фомин Г. П. Математические методы и модели в коммерческой деятельности, 2009.

[_fbe89725d7272f01-154] 154,0 ^154,1 Gross J. L., Yellen J. Graph theory and its applications, 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]

[75]

[76]

[77]

[78]

[79]

[80]

[81]

[82]

[83]

[84]

[85]

[86]

[87]

[88]

[89]

[90]

[91]

[92]

[93]

[94]

[95]

[96]

[97]

[98]

[99]

[100]

Алгоритмы на графах
Поиск уплотнений	Алгоритм Брона — Кербоша Алгоритм Косарайю Алгоритм Мальгранжа Алгоритм Тарьяна Алгоритм Демукрона Приближенный алгоритм поиска p-медиан Задача о самом длинном пути Топологическая сортировка Шарнир (теория графов) Алгоритм Каргера (минимальный разрез)
Максимизация потока	Алгоритм Диница Алгоритм Малхотры — Кумара — Махешвари Алгоритм проталкивания предпотока Алгоритм Форда — Фалкерсона Алгоритм Эдмондса — Карпа Транспортная сеть
Паросочетания	Алгоритм сжатия цветков Алгоритм Хопкрофта — Карпа Алгоритм FKT
Связь графов	Алгоритм Гавела — Хакими(графичность последовательности) Расстояние редактирования графа Задача поиска изоморфного подграфа
Другое	Алгоритм для дерева сочленений (извлекает маргинализацию) Алгоритм Катхилла — Макки (уменьшения ширины ленты) Итеративное сжатие (идея рекурсии) Шаблон:Алгоритмы поиска на графах

Алгоритмы поиска на графах
Неинформированные методы	Двунаправленный поиск Лучевой поиск Лексикографический поиск в ширину Поиск в ширину Поиск по критерию стоимости Поиск в глубину Поиск с возвратом Поиск восхождением к вершине Поиск с ограничением глубины Поиск в глубину с итеративным углублением
Информированные методы	Альфа-бета-отсечение Метод ветвей и границ Поиск по первому наилучшему совпадению A* B* D* Поиск точки перехода IDA* Рекурсивный поиск по первому наилучшему совпадению SMA*
Кратчайшие пути	Волновой алгоритм Алгоритм Беллмана — Форда Алгоритм Дейкстры Алгоритм Джонсона Алгоритм Левита Алгоритм Флойда — Уоршелла Поиск по краям
Минимальное остовное дерево	Алгоритм Борувки Алгоритм Прима Алгоритм Краскала
Другое	Алгоритм Британского музея Алгоритм Эдмондса Обход дерева Алгоритм ближайшего соседа в задаче коммивояжёра