Терминология
Граф состоит из вершин, соединённых рёбрами. Мы будем обозначать буквой \(n\) количество вершин графа, а буквой \(m\) – количество рёбер. Рёбра нумеруются числами \(1,2,\ldots,n.\) На рисунке ниже изображён граф с \(5\) вершинами и \(7\) рёбрами.
Оценим количество рёбер в произвольном графе, который содержит \(n\) вершин. Очевидно, это неотрицательное число, которое сверху ограничено некоторой величиной, зависящей от \(n.\) Максимальное количество рёбер в таком графе, где между любой парой вершин есть ребро. В таком графе \(\frac{n(n-1)}{2}\) рёбер (из каждой вершины исходит ровно \(n-1\) рёбер, всего \(n\) вершин, но каждое ребро было посчитано дважды). Следовательно, для любого графа верно неравенство:
\(0 \leq m \leq \frac{n(n-1)}{2}.\)
Путь ведёт из одной вершины в другую и проходит по рёбрам графа. Длиной пути называется количество ребёр в нём. Простой путь – это путь, в котором все вершины различны. На рисунке ниже показан простой путь \(1 → 3 → 4 → 5\) длины \(3\) из вершины \(1\) в вершину \(5.\)
Циклом называется путь, в котором последняя вершина совпадает с первой. Простой цикл – это цикл, в котором все вершины различны (кроме первой и последней). На рисунке ниже изображён простой цикл \(1 → 3 → 4 → 1.\)
Граф называется связным, если между любыми двумя вершинами существует путь. На рисунке ниже левый граф связный, а правый – нет, потому что из вершины \(4\) нельзя попасть ни в какую другую.
Связные части графа называются его компонентами связности. Граф на рисунке ниже состоит из трёх компонент связности: \(\{1, 2, 3\}, \ \{4, 5, 6, 7\}\) и \(\{8\}.\)
В ориентированном графе (орграфе) по каждому ребру можно проходить только в одном направлении. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. На рисунке ниже показан пример ориентированного графа. В нём имеется путь \(3 → 1 → 2 → 5\) из вершины \(3\) в вершину \(5\), но не существует пути из вершины \(5\) в вершину \(3.\)
Кратные (параллельные) рёбра – это рёбра, которые соединяют одну и ту же пару вершин. Если две вершины соединены более чем одним ребром, говорят, что граф содержит кратные рёбра. Петля – это ребро, которое соединяет вершину саму с собой. Граф, который не содержит петель и кратных рёбер, называется простым. На рисунке ниже красным выделено кратное ребро, а синим обозначена петля.
Во взвешенном графе каждому ребру сопоставлен вес. Часто веса интерпретируются как длины рёбер, а длиной пути считается сумма весов составляющих его рёбер. На рисунке ниже изображён взвешенный граф, длина пути \(1 → 3 → 4 → 5\) равна \(1 + 7 + 3 = 11.\) Это кратчайший путь из вершины \(1\) в вершину \(5.\)
Две вершины называются соседними, или смежными, если они соединены ребром. Степенью вершины называется число соседних с ней вершин. На рисунке ниже показаны степени всех вершин графа. Так, степень вершины \(2\) равна \(3,\) потому что ее соседями являются вершины \(1, 4\) и \(5.\)
Сумма степеней всех вершин графа равна \(2m\), где \(m\) – число рёбер, поскольку каждое ребро увеличивает степени ровно двух вершин на единицу. Таким образом, сумма степеней вершин всегда чётна. Граф называется регулярным, если степени всех его вершин одинаковы (равны некоторой константе \(d\)). Граф называется полным, если степень каждой его вершины равна \(n − 1\), т. е. в графе присутствуют все возможные рёбра. Граф называется пустым, если степень каждой его вершины равна \(0\), т. е. граф без рёбер.
В ориентированном графе полустепенью захода вершины называется число рёбер, оканчивающихся в этой вершине, а полустепенью исхода – число рёбер, начинающихся в вершине. Вершина ориентированного графа называется истоком, если в неё не входит ни одно ребро, и стоком, если из неё не выходит ни одного ребра. На рисунке ниже показаны полустепени захода и исхода для каждой вершины графа. Например, для вершины \(2\) полустепень захода равна \(2,\) а полустепень исхода – \(1.\) Так же вершины \(1\) и \(5\) являются истоками, \(4\) – стоком.
Граф называется двудольным, если его вершины можно раскрасить в два цвета, так что цвета любых двух соседних вершин различны. На рисунке ниже изображены двудольный граф и его раскраска.
Критерий Кёнига. Граф является двудольным тогда и только тогда, когда все его циклы – чётны.
Представление графа
Есть несколько способов представить граф в алгоритмах. Выбор структуры данных зависит от размера графа и способа его обработки в алгоритме. Ниже рассмотрены три популярных представления.
Списки смежности
В этом случае каждой вершине \(u\) сопоставляется список смежности, включающий вершины, соединенные с \(u\) ребром. Списки смежности – самый популярный способ представления графов, они позволяют эффективно реализовать большинство алгоритмов.
Списки смежности удобно хранить в списке списков, который объявлен следующим образом:
g = [[] for _ in range(n + 1)]
Переменная \(n\) выбрана так, чтобы в списке поместились все списки смежности. Например, граф на рисунке ниже
можно сохранить так:
g[1].append(2)
g[2].append(3)
g[2].append(4)
g[3].append(4)
g[4].append(1)
Неориентированные графы можно хранить аналогично, только каждое ребро нужно учитывать в двух списках смежности (для обоих направлений).
Для взвешенных графов список смежности вершины \(u\) содержит пару \((v,w),\) если существует ребро с весом \(w,\) направленное от \(u\) к \(v.\) Граф на рисунке ниже
можно сохранить следующим образом:
g[1].append((2, 5))
g[2].append((3, 7))
g[2].append((4, 6))
g[3].append((4, 5))
g[4].append((1, 2))
Списки смежности позволяют эффективно находить вершины, в которые можно перейти из данной по одному ребру. Следующий цикл обходит все вершины, в которые можно попасть из вершины \(u\):
for v in g[u]:
# обработать вершину v
Матрица смежности
Матрица смежности показывает, какие рёбра есть в графе. С её помощью можно эффективно проверить, существует ли ребро между двумя вершинами. Матрицу можно хранить в виде двумерного спика \(g[n][n]\), где элемент \(g[u][v]\) равен \(1,\) если существует ребро, ведущее из вершины \(u\) в вершину \(v,\) а в противном случае равен \(0.\) Так, матрица смежности для графа на рисунке ниже
имеет вид:
\(\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}\)
Если граф взвешенный, то представление в виде матрицы смежности можно обобщить: если две вершины соединены ребром, то в матрице хранится вес этого ребра. Так, граф на рисунке ниже
представляется следующей матрицей:
\(\begin{bmatrix} 0 & 5 & 0 & 0 \\ 0 & 0 & 7 & 6 \\ 0 & 0 & 0 & 5 \\ 2 & 0 & 0 & 0 \end{bmatrix}\)
Недостаток матрицы смежности заключается в том, что она содержит \(n^2\) элементов, большая часть которых обычно равна \(0.\) Поэтому такое представление не годится для больших графов.
Список рёбер
Список рёбер содержит все ребра графа в некотором порядке. Это представление удобно, если алгоритм обрабатывает все ребра и не требуется находить рёбра, начинающиеся в заданной вершине.
Список рёбер можно хранить в списке \(g,\) где наличие пары \((u,v)\) означает, что существует ребро из вершины \(u\) в вершину \(v.\) Граф на рисунке ниже
можно представить следующим образом:
g.append((1, 2))
g.append((2, 3))
g.append((2, 4))
g.append((3, 4))
g.append((4, 1))
Для взвешенных графов каждый элемент списка рёбер имеет вид \((u,v,w),\) это означает, что существует ребро с весом \(w,\) ведущее из вершины \(u\) в вершину \(v.\) Например, граф на рисунке ниже
можно представить следующим образом:
g.append((1, 2, 5))
g.append((2, 3, 7))
g.append((2, 4, 6))
g.append((3, 4, 5))
g.append((4, 1, 2))