Том 11. Карты метро и нейронные сети. Теория графов - [4]

* * *

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

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

* * *

ГРАФЫ И ЧИСЛА

Если две вершины графа могут соединяться не более чем одним ребром, то такой граф можно выразить таблицей чисел, или матрицей. Связный граф ABCDE, изображенный на рисунке, можно представить в виде следующей таблицы. Если соответствующие вершины соединены ребром, в ячейке записывается 1, если нет — 0.

ПЕРЕДАЧА СООБЩЕНИЙ И ОШИБКИ

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

* * *

Геометрические и полные графы

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

Подобными графами можно представить маршруты городских автобусов или маршруты патрулей. Число вершин V равно числу ребер А.

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

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

Графы, в которых любая пара вершин соединена ребром, называются полными. На следующих рисунках приведены полные графы с числом вершин от 2 до 7. Полный граф с n вершинами обозначается К_n.

Подсчитать число ребер полного графа К_n очень просто: каждая вершина должна соединяться с n — 1 вершиной, число вершин равно n, следовательно, значение выражения n(n — 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n — 1)/2 — биномиальному коэффициенту 

, равному числу всех возможных пар на множестве из n элементов. Зависимость между числом ребер и n является квадратичной, следовательно, число ребер К_n  будет возрастать очень быстро.

* * *

ТЕОРЕМА ТУРАНА

В 1941 году Пал Туран поставил следующую задачу. Пусть дан простой граф G с n вершинами, число р(р >= 2) — число вершин полного р-вершинного подграфа графа G (иными словами, К_р). Вопрос таков: каково максимальное число ребер графа, который не содержит подобный р-вершинный подграф? Удивительно, но число ребер не может быть больше, чем n²р/2(р -1). Эта теорема и ее очень красивое доказательство занимают важное место в теории графов.

* * *

Плоские графы

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

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

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

* * *

ЭЛЕГАНТНЫЕ ПЛОСКИЕ ГРАФЫ

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

* * *

Задача о колодцах и враждующих семьях

Задача звучит так: в трех домах а, Ь, с живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца е, f, g. Один из колодцев всегда полон, два других пусты. Соседи хотят проложить дорожки так, чтобы из каждого дома можно было попасть к каждому колодцу. Никакие две дорожки не должны пересекаться, чтобы каждый мог избежать встреч с соседями. Можно ли проложить девять дорожек таким способом?

На рисунке слева показана первая попытка соединить дома а, Ь, с и колодцы е, f, g. Такой граф обозначается К_3,3. Получилось множество нежелательных пересечений. На рисунке справа тот же граф изображен иначе, но избежать пересечений по-прежнему не удалось. Заметим, что если убрать дорожку от дома