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

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

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

• Схема метрополитена
• Родословное древо
• Карта подводных оптоволоконных магистралей
• Семантический анализ новостных лент
• Логистика
• Телекоммуникации
• Банковские операции

---

Графы

Неориентированный граф

Неориентированный граф

- совокупность множества вершин и множества соединяющих рёбер. Имеет неупорядоченные пары.

$G=(V,E)$

Пример:

$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$e_1=v_1{v}_2=v_2{v}_1$
$e_2=v_1{v}_4=v_4{v}_1$
$e_3=v_4{v}_3=v_3{v}_4$
$e_4=v_1{v}_3=v_3{v}_1$
$e_5=v_2{v}_3=v_3{v}_2$

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

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

- граф, в котором рёбра имеют определённое направление. Имеет упорядоченные пары.

$G=(V,E)$

Пример:

$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$e_1=v_2{v}_1$
$e_2=v_1{v}_4$
$e_3=v_3{v}_4$
$e_4=v_1{v}_3$
$e_5=v_3{v}_2$

Смешанный граф

Смешанный граф

- граф, в котором рёбра имеют как определённые, так и неопределённые направления. Имеет как упорядоченные, так и неупорядоченные пары.

$G=(V,E)$

Пример:
$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$e_1=v_1{v}_2=v_2{v}_1$
$e_2=v_1{v}_4$
$e_3=v_4{v}_3=v_3{v}_4$
$e_4=v_1{v}_3=v_3{v}_1$
$e_5=v_3{v}_2$

Псевдограф

Псевдограф

- граф, содержащий петли.

Петля:

• Пара одинаковых элементов множества вершин V вида $v_x{v}_x$ называется петлёй.
• Ребро, концы которого есть одна и та же вершина, называют петлёй.

Пример:

$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$e_1=v_1{v}_2=v_2{v}_1$
$e_2=v_1{v}_4=v_4{v}_1$
$e_3=v_4{v}_3=v_3{v}_4$
$e_4=v_1{v}_3=v_3{v}_1$
$e_5=v_2{v}_3=v_3{v}_2$
$e_6=v_2{v}_2$ - Петля

Мультиграф

Мультиграф

- граф, содержащий кратные рёбра

Кратные рёбра:
Два и более ребра, соединяющие одни и те же две вершины, называются кратными.

Пример:

$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$e_1=v_1{v}_2=v_2{v}_1$
$e_2=v_1{v}_4=v_4{v}_1$
$e_3=v_4{v}_3=v_3{v}_4$
$e_4=v_1{v}_3=v_3{v}_1$
$e_5=v_2{v}_3=v_3{v}_2$ - Кратное с $e_6$
$e_6=v_2{v}_3=v_3{v}_2$ - Кратное с $e_5$

Полный граф

Полный граф

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

Пример:

Подграф

Подграф

Граф $G_1(V_1,E_1)$ называется подграфом графа $G(V,E)$ ($G_1\subseteq G$), если $V_1\subseteq V$ и $E_1\subseteq E$. Это граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.

Исходный граф (Пример):

Собственный подграф

Это подграф, где $V_1\subset V$ и $E_1\subset E$. (отличен от исходного графа)

Остовный подграф

Это подграф, содержащий все вершины, то есть $V_1=V$.

Пример:

Вершинно-порождённый подграф

Неориентированный подграф $G_1=(V_1,E_1)$ называется вершинно-порождённым подграфом неориентированного графа $G=(V,E)$, если он получен путём выбора некоторого подмножества вершин $V$ и присоединения к ним всех соответствующих рёбер.

Пример:

Рёберно-порождённый подграф

Неориентированный подграф $G_1=(V_1,E_1)$ называется рёберно-порождённым подграфом неориентированного графа $G=(V,E)$, если он получен путём выбора некоторого подмножества рёбер $E$ с сохранением, естественно, соответствующих вершин.

Дерево

Определения

(Неориентированное) дерево — это связный ациклический граф.

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

Элементы ориентированного дерева

• Корень — это вершина с нулевой степенью захода.
• Концевые вершины (листья) — это вершины с нулевой степенью исхода (из которых не исходит ни одна дуга).

Свойства

1. Любое дерево с $n$ вершинами содержит $n-1$ ребро.
2. Конечный связный граф является деревом тогда и только тогда, когда $n-m=1$ (где $n$ — число вершин, $m$ — число рёбер).
3. Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственной простой цепью.

Пример (Ориентированное дерево):

• Корень: Вершина 1.
• Листья: Вершины 4, 2, 7, 8.

Остовное дерево (Остов)

Определение

Остовное дерево (Остов) — это ациклический связный подграф некоторого связного неориентированного графа, в который входят все его вершины.

Свойства

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

Пример: Граф-решетка. Синим выделены ребра, образующие остов.

Взвешенные графы

Основные понятия

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

Максимальное остовное дерево — аналогично, но с максимальным весом.

Задачи

• Минимальный остов: Задача о минимизации общей стоимости строительства дорог.
• Максимальный остов: Задача о максимальной суммарной скорости передачи данных между вычислительными узлами в компьютерной сети.

Алгоритмы построения минимального остова

1. Алгоритм Краскала
2. Алгоритм Прима
3. Алгоритм Борувки
4. Алгоритм Дейкстры (Примечание: обычно используется для поиска кратчайших путей, но упомянут в контексте лекции).

Пример (Взвешенный граф):

Разреженный граф

Разреженный граф

Разреженный граф — это граф, в котором число рёбер значительно меньше максимально возможного. Обычно разреженный граф имеет примерно столько же рёбер, сколько вершин, т.е. $m=O(n)$.

Примеры:

• Транспортные и дорожные сети: Количество дорог (рёбер) ненамного превышает количество перекрёстков (вершин).
• Веб-граф: Интернет-сайты (вершины) и гиперссылки (рёбра), идущие с одних сайтов на другие.

Плотный граф

Плотный граф

Плотный граф — это граф, в котором число рёбер близко к максимально возможному (как у полного графа). Например, в плотном графе каждая пара вершин соединена одним ребром, т.е. $m=O(n^2)$.

Примеры:

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

Эйлеровы графы

Эйлеров граф

Это граф, содержащий эйлеров цикл.

Полуэйлеров граф

Это граф, содержащий эйлеров путь.

Гамильтоновы графы

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

Это граф, содержащий гамильтонов цикл.

Полугамильтонов граф

Это граф, содержащий гамильтонов путь.

Планарные графы

Определения

Планарный граф — граф, который изоморфен плоскому графу.

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

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

• Внешняя грань — неограниченная область.

Правильные многогранники

• Тетраэдр — 4 треугольника.
• Куб (гексаэдр) — 6 квадратов.
• Октаэдр — 8 треугольников.
• Додекаэдр — 12 правильных пятиугольников.
• Икосаэдр — 20 равносторонних треугольников.

Изоморфность и укладка Для любого планарного графа $G$ существует плоская укладка, в которой все ребра — прямолинейные отрезки.

---

Смежность, инцидентность, достижимость

Смежность

Смежность

Вершины u и v, соединённые ребром $u\mapsto v$, называют смежными, а также концами ребра {u,v}.
u и v в таком случае связаны отношением непосредственной достижимости.

Пример:
$V=\{v_1,v_2,v_3,v_4\}$
$E=\{e_1,e_2,e_3,e_4,e_5\}$
$v_1$ - смежная с $v_2,v_3,v_4$
$v_2$ - смежная с $v_1,v_3$
$v_3$ - смежная с $v_1,v_2,v_4$
$v_4$ - смежная с $v_1,v_3$

Списки смежности

Списки, в которых каждой вершине графа сопоставляется список смежных ей вершин.

Пример:

$v_1$: $v_2,v_3,v_4$
$v_2$: $v_1,v_3$
$v_3$: $v_1,v_2,v_4$
$v_4$: $v_1,v_3$

Матрица смежности

Так называется матрица $M:p\times p$

$m_{i,j}=\{\begin{array}{ll}1,& ij\in E;\\ 0& ij\notin E.\end{array}$

для неориентированного графа

$b_{ij}=\{\begin{array}{ll}1,& \text{i-я и j-я вершины смежные;}\\ 0,& \text{иначе;}\end{array}$

для ориентированного графа

$b_{ij}=\{\begin{array}{ll}1,& \text{из i-й вершины в j-ю ведет дуга;}\\ 0,& \text{иначе.}\end{array}$

Пример:

	$v_1$	$v_2$	$v_3$	$v_4$
$v_1$	0	1	1	1
$v_2$	1	0	1	0
$v_3$	1	1	0	1
$v_4$	1	0	1	0

Инцидентность

Инцидентность

Ребро e называют инцидентным вершине v, если она является одним из его концов.
Два ребра, инцидентные одной вершине, так же как и две вершины, инцидентные одному ребру - смежные

Пример:

Вершины $v_1,v_2$ - смежны
Вершины $v_2,v_4$ - не смежны
Ребра $e_1$ и $e_2$ - смежны

Списки инцидентности

Списки, в которых каждому ребру графа сопоставляется список инцидентных ему вершин.

Пример:
$e_1$: $v_1{v}_2$
$e_2$: $v_1{v}_4$
$e_3$: $v_3{v}_4$
$e_4$: $v_1{v}_3$
$e_5$: $v_2{v}_3$

Матрица инцидентности

Так называется матрица $B:n\times m$ (где $n$ — количество вершин, $m$ — количество ребер):

$b_{ij}=\{\begin{array}{ll}1,& v_i\in e_j;\\ 0& v_i\notin e_j.\end{array}$

Для неориентированного графа:
$b_{ij}=\{\begin{array}{ll}1,& \text{вершина }{v}_i\text{ инцидентна ребру }{e}_j;\\ 0,& \text{иначе;}\end{array}$

Для ориентированного графа:
$b_{ij}=\{\begin{array}{ll}1,& \text{из вершины }{v}_i\text{ исходит дуга }{e}_j;\\ -1,& \text{в вершину }{v}_i\text{ заходит дуга }{e}_j;\\ 0,& \text{иначе.}\end{array}$

Пример:

	$e_1$	$e_2$	$e_3$	$e_4$	$e_5$
$v_1$	1	1	0	1	0
$v_2$	1	0	0	0	1
$v_3$	0	0	1	1	1
$v_4$	0	1	1	0	0

Достижимость

Достижимость

Отношение достижимости

В неориентированном графе Вершина v достижима из вершины u, если существует цепь из u в v.

В ориентированном графе Вершина v ориентированного графа G достижима из вершины u этого же графа, если существует путь $v_0,v_1,v_2\dots v_n$, такой, что $u=v_0,v=v_n$.

Матрица достижимости

Это квадратная матрица $T$ порядка $|V|$ ($n\times n$), каждый элемент $T_{ij}$ которой равен 1, если $j$-я вершина достижима из $i$-й вершины, и равен 0 иначе.

$T_{ij}=\{\begin{array}{ll}1,& \text{если }\exists ⟨i,j⟩;\\ 0,& \text{иначе.}\end{array}$

Согласно определению достижимости, элементы $T_{ii}=1$.

Пример: Граф из 4 вершин ($a,b,c,d$) и 5 дуг.

Матрица $T$ для вершин в порядке $a,b,c,d$: $T=\left(\begin{array}{cccc}1& 1& 0& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 1\\ 1& 1& 0& 1\end{array}\right)$

---

Леммы и алгоритмы

Лемма Эйлера

Лемма Эйлера

Формулировка

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

${\sum }_{v\in V}deg(v)=2|E|$

Доказательство

Посчитаем количество инцидентных пар $(v,e)$, где $e$ — ребро и $v$ — одна из его концевых вершин, двумя разными способами.

Каждая вершина $v$ принадлежит $\mathrm{deg}(v)$ парам, где $\mathrm{deg}(v)$ — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней.

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

Для ориентированного графа

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

${\sum }_{v\in V}(d^{+}(v)+d^{-}(v))=2q$

Другая формулировка

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

Пример:

Сумма полустепеней исхода по часовой стрелке, начиная от А:
$2+1+1+1=5$
Сумма полустепеней захода против часовой стрелки, начиная от А: $2+1+1+1=5$

Верна ли лемма Эйлера для мультиграфов?

Да, прибавляя любое кратное ребро, которое связывает 2 вершины, сумма всех степеней увеличивается на 2.

Верна ли лемма Эйлера для псевдографов?

В случае псевдографа вклад каждой петли, инцидентной вершине u, в d(u) равен 2. Тогда лемма Эйлера верна не только жля графов и мультиграфов, но и для псевдографов.

Лемма о рукопожатиях

Лемма о рукопожатиях

Формулировка

В любом графе число вершин чётной степени чётно.

Лемма о цепи

Лемма о цепи

Формулировка

Если есть цепь, соединяющая вершины u,v, то есть простая цепь, соединяющая вершины u,v.

Доказательство

Рассмотрим в графе (u,v) - маршрут наименьшей длины.

Нужно показать, что этот маршрут является простой цепью.

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

Алгоритм Флойда — Уоршелла

Общие сведения

Алгоритм Флойда — Уоршелла (1962) предназначен для нахождения замыкания транзитивности графа (матрицы достижимости).

• Авторы: Роберт Флойд, Стивен Уоршелл.
• Сложность: $O(n^3)$ (для графа из $n$ вершин).

Описание алгоритма

Пошаговая инструкция

1. Пусть $E_0=B$ (матрица смежности графа).
2. Строим последовательность матриц $E_1,E_2,\dots ,E_n$.
3. Для построения матрицы $E_k$ рассматриваем $k$-й столбец матрицы $E_{k-1}$:
   • Строки, у которых в $k$-м столбце стоит 0, просто копируем в новую матрицу $E_k$.
   • Строки с номером $i$, у которых в $k$-м столбце стоит 1, объединяем с помощью операции ИЛИ ($\vee$) с $k$-й строкой матрицы $E_{k-1}$. Результат записываем в $E_k$.
4. Итоговая матрица достижимости $C$ вычисляется как объединение единичной матрицы $E$ (рефлексивность) и полученной матрицы $E_n$: $C=E\vee E_n$

Пример выполнения

Исходный граф и матрица $E_0$

$$E_0=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$$

(Примечание: Граф содержит 4 вершины. Вершины пронумерованы как 1, 2, 3, 4).

Шаг 1. Матрица $E_1$ ($k=1$)

• Рассматриваем 1-й столбец матрицы $E_0$: $(0,0,0,0{)}^T$.
• Во всех строках в 1-м столбце стоят нули $\Rightarrow$ все строки просто копируются. $E_1=E_0=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$

Шаг 2. Матрица $E_2$ ($k=2$)

• Рассматриваем 2-й столбец матрицы $E_1$: $(1,0,1,0{)}^T$.
• Строки 2 и 4 (значение 0): Копируем.
• Строки 1 и 3 (значение 1): Выполняем дизъюнкцию с 2-й строкой.
  • Строка 2: $(0,0,0,0)$.
  • Строка 1: $(0,1,1,0)\vee (0,0,0,0)=(0,1,1,0)$.
  • Строка 3: $(0,1,0,1)\vee (0,0,0,0)=(0,1,0,1)$. $E_2=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$ (Матрица не изменилась, так как 2-я строка пустая).

Шаг 3. Матрица $E_3$ ($k=3$)

• Рассматриваем 3-й столбец матрицы $E_2$: $(1,0,0,1{)}^T$.
• Строки 2 и 3 (значение 0): Копируем.
• Строки 1 и 4 (значение 1): Выполняем дизъюнкцию с 3-й строкой.
  • Строка 3: $(0,1,0,1)$.
  • Строка 1: $(0,1,1,0)\vee (0,1,0,1)=(0,1,1,1)$.
  • Строка 4: $(0,0,1,0)\vee (0,1,0,1)=(0,1,1,1)$. $E_3=\left(\begin{array}{cccc}0& 1& 1& 1\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 1& 1& 1\end{array}\right)$

Шаг 4. Матрица $E_4$ ($k=4$) и Итог

• Рассматриваем 4-й столбец матрицы $E_3$: $(1,0,1,1{)}^T$.
• Строка 2 (значение 0): Копируем.
• Строки 1, 3, 4 (значение 1): Выполняем дизъюнкцию с 4-й строкой.
  • Строка 4: $(0,1,1,1)$.
  • Все объединения с этой строкой дадут $(0,1,1,1)$ (так как она уже “полная” для этого примера). $E_4=\left(\begin{array}{cccc}0& 1& 1& 1\\ 0& 0& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

Финальная матрица достижимости: $C=E\vee E_4$. $C=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

Алгоритм Краскала

Описание

1. В начале текущее множество рёбер устанавливается пустым.
2. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.
3. Когда таких рёбер больше нет, алгоритм завершён.
4. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.

Эффективнее для разреженных графов!

Сложность

$O(m\cdot \log n)$

• $n$ — число вершин
• $m$ — число рёбер

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

Алгоритм Прима

Описание

1. Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшим весом.
2. Найденное ребро и соединяемые им две вершины образуют дерево. Затем рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшего веса.
3. Выбираемое на каждом шаге ребро присоединяется к дереву.
4. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.
5. Результатом работы алгоритма является минимальное остовное дерево.

Эффективнее для плотых графов!

Сложность

$O(n^2)$

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

Формула Эйлера для планарных графов

Формулировка

Если $G=(V,E)$ — связный планарный граф с $p$ вершинами и $q$ ребрами, то для каждой его укладки на плоскости верно равенство:

$p-q+r=2$

• $p$ — число вершин
• $q$ — число рёбер
• $r$ — число граней (включая внешнюю) в этой укладке.

Следствие

Сумма степеней граней равна удвоенному числу рёбер: ${\sum }_{i=1}^r\mathrm{deg}(f_i)=2q$

• $\mathrm{deg}(f_i)$ — степень грани (число ребер, ограничивающих грань).

---

Элементы графа

Маршрут

Маршрут

Описание	Обозначение	Условие
Последовательность вершин и ребер (не обязательно различных)	$v_0{e}_1{v}_1{e}_2\dots v_{k-1}{e}_k{v}_k$	в которой $e_i=v_{i-1}{v}_i$ т.е. любые две вершины соединены ребром
Последовательность вершин (не обязательно различных)	$v_0{v}_1{v}_2\dots v_{k-1}{v}_k$	любые два последовательных элемента являются смежными вершинами
Последовательность ребер (не обязательно различных)	$e_1,e_2,\dots ,e_n$	если существует последовательность вершин $v_0,v_1,v_2,\dots ,v_n$ (не обязательно различных), таких, что ребро $e_i$ инцидентно вершинам $v_{i-1}$ и $v_i$

Замкнутый маршрут

Если $v_0=v_n$, то маршрут называется замкнутым, то есть его концы совпадают.

Пример:

• Вершины и ребра: $1,a,4,d,3,e,4,d,3,c,2,h,2$
• Ребра: $a,b,e,d,c,h$

• Маршрут: a b d b c
• Замкнутый маршрут: a b d b c a

Цепь

Цепь

Маршрут, в котором все рёбра различны.

Простая цепь

Маршрут, в котором все вершины и рёбра различны.

Замкнутая цепь

Если $v_0=v_n$, то цепь называется замкнутой, то есть её концы совпадают.

Длина цепи

Для конечной цепи $v_0,v_1\dots v_n$ число $n$ (число рёбер) называют длиной цепи.
Цепь длины 0 — произвольная вершина графа.

Пример:

• Цепь: a b d c b
• Простая цепь: a b c d e

Цикл

Цикл

Замкнутый маршрут, в котором все рёбра различны (замкнутая цепь).

Простой цикл

Замкнутый маршрут, в котором все вершины различны (простая замкнутая цепь).

Пример:

• Цикл: a b f e d b c a
• Простой цикл: a b c a

Ациклический граф

Неориентированный граф, не содержащий циклов.

Пример:

Путь

Путь

Пример:

• Маршрут: 1 2 4 1 2 3
• Путь этого маршрута: 1 2 4 1

Простой путь

Пример:

• Простой путь для маршрута выше: 1 2 3
  

Контур

Контур

Замкнутый маршрут, в котором все его дуги различны (замкнутый путь).

Пример (Контур, но не простой): a11 a3 a4 a7 a1 a12 a9 Повторяется вершина $x_1$ и $x_6$.

Замкнутый контур (Простой контур)

Замкнутый маршрут, в котором все вершины различны (простой замкнутый путь).

Примеры:

• a3 a6 a11
• a3 a4 a7 a10 a9 c11

Бесконтурный граф

Ориентированный граф, не содержащий контуров.

Пример: [!INFO]- Маршруты, цепи, циклы, пути, контуры, мосты

Маршруты, цепи, циклы, пути, контуры, мосты

Мост

Мост

Ребро графа $G(V,E)$ называется мостом, если его удаление увеличивает число компонент связности графа.

Пример:

• Мостом является ребро $de$.
• При его удалении граф распадается на две компоненты связности: левую ($\{a,b,c,d\}$) и правую ($\{e,f,g,h,i,j\}$).

Эйлеров путь и цикл

Эйлеров путь (эйлерова цепь)

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

Эйлеров цикл (эйлерова линия)

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

---

Связность графа

Неориентированный граф

Неориентированный граф

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

Пример:

• Какие вершины связные, а какие нет?
  • Связные: $\{1,6\}$, $\{2,7\}$, $\{3,4,5,8\}$.
  • Не связные: например, 1 и 2, или 6 и 8.

Связный граф

Граф называется связным, если любые две вершины в нем связны. (Существует лишь одна компонента связности).

В противном случае граф называется несвязным.

Компонента связности

Компонентой связности (или просто компонентой) графа $G$ называется его максимальный связный подграф. Это связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа $G(V,E)$.

Примеры:

• Связный граф: Все вершины соединены.
• Несвязный граф: 2 компоненты связности ($\{a,b,c\}$ и $\{f,g\}$).
• Несвязный граф с 3 компонентами: Одна из компонент — изолированная вершина $a$.

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

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

Виды связности вершин

• Связные (односторонне связные): Существует путь из $v_1$ в $v_2$ ИЛИ из $v_2$ в $v_1$.
• Сильно связные: Существует путь из $v_1$ в $v_2$ И из $v_2$ в $v_1$.
• Слабо связные: Вершины связны в неориентированном графе $G^{\prime }(V^{\prime },E^{\prime })$, полученном отменой ориентации ребер.

Ассоциированный граф

Неориентированный граф $G_1(V_1,E_1)$ называют ассоциированным с ориентированным графом $G(V,E)$, если его множество вершин совпадает с множеством вершин орграфа, а ребро существует тогда и только тогда, когда между вершинами есть дуга (в любом направлении).

$E_1=\{\{u,v\}:(u,v)\in E\vee (v,u)\in E,u\ne v\}$

Типы связности орграфа

• Связный (односторонне связный): Любые две вершины связны (достижимость хотя бы в одну сторону).
• Сильно связный: Любые две вершины сильно связны (взаимная достижимость).
• Слабо связный: Ассоциированный с ним неориентированный граф связный.

Примеры:

• $G_1$ (Сильно связный): Можно попасть из любой точки в любую.
• $G_2$ (Связный / Односторонне): Есть пути, но не везде можно вернуться обратно.
• $G_3$ (Слабо связный): Граф “держится вместе” только если убрать стрелки.

Компоненты и бикомпоненты

Компоненты и бикомпоненты ориентированного графа

Определения

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

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

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

Пример:

• Граф является слабо связным.
• Бикомпоненты ($B$):
  • $B_1=\{v_1\}$
  • $B_2=\{v_2,v_3\}$
  • $B_3=\{v_4,v_5\}$
  • $B_4=\{v_6,v_7\}$
• Компоненты ($C$):
  • $C_1=\{v_1,v_2,v_3,v_4,v_5\}$
  • $C_2=\{v_4,v_5,v_6,v_7\}$
• Свойство: Любая бикомпонента или не пересекается с компонентой, или целиком в неё входит.

Матрица достижимости

Для графа из примера: $C=\left(\begin{array}{ccccccc}1& 1& 1& 1& 1& 0& 0\\ 0& 1& 1& 1& 1& 0& 0\\ 0& 1& 1& 1& 1& 0& 0\\ 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 1& 1\end{array}\right)$

Алгоритм поиска бикомпонент

1. В бикомпоненту входят взаимно достижимые вершины.
2. Для двух вершин $i$ и $j$ должно выполняться: $c_{ij}=c_{ji}=1$
3. Нужно просмотреть $i$-ю строку и $i$-й столбец матрицы и сформировать множество номеров вершин: $P=\{p:c_{ip}=c_{pi}=1\}$
4. Различные бикомпоненты не пересекаются.

Алгоритм поиска компонент

1. Выписываем для каждой вершины $v_i$ множество $K_i$, состоящее из вершин, которые достижимы из $i$ ИЛИ из которых достижима $i$: $c_{ij}=1\vee c_{ji}=1$
2. Для примера:
   • $K_1=\{v_1,v_2,v_3,v_4,v_5\}$
   • $K_2=K_3=K_1$
   • $K_4=K_5=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$
   • $K_6=K_7=\{v_4,v_5,v_6,v_7\}$
3. Компонента строится как пересечение множеств $K$.
   • $C_1$ (содержащая $v_1$): $K_1\cap K_2\cap K_3\cap K_4\cap K_5=K_1=\{v_1..v_5\}$.
   • $C_2$ (содержащая $v_4$, отличная от $C_1$): $K_4\cap K_5\cap K_6\cap K_7=K_7=\{v_4..v_7\}$. [!DANGER]- Матричные методы анализа графов

Нахождение количества путей

Пусть $B$ — матрица смежности орграфа. Если возвести матрицу смежности в квадрат ($B^2$), то элемент $b_{ik}^{(2)}$ будет равен числу путей длины 2, идущих из $x_i$ в $x_k$.

Обобщение Если $b_{ik}^p$ является элементом матрицы $B^p$, то $b_{ik}^p$ равно числу путей (не обязательно простых) длины $p$, идущих из $x_i$ в $x_k$.

Матрица достижимости ($C$)

Матрица достижимости содержит информацию о существовании пути между любыми вершинами. $c_{ij}=1$, если вершина $x_j$ достижима из $x_i$, иначе $0$.

Алгоритм построения Для графа с $n$ вершинами матрица достижимости определяется через булеву сумму степеней матрицы смежности: $C=E\vee B\vee B^2\vee \cdots \vee B^{n-1}$

• $E$ — единичная матрица (пути длины 0).
• $B^k$ — информация о путях длины $k$.
• $\vee$ — логическое сложение (дизъюнкция).

Матрица сильной связности ($S$)

Матрица сильной связности содержит информацию обо всех сильно связанных вершинах (вершины $x_i$ и $x_j$ взаимно достижимы). Элемент $s_{ij}=1$, если существует путь из $x_i$ в $x_j$ И из $x_j$ в $x_i$.

Алгоритм построения $S=C\&C^T$

• $C$ — матрица достижимости.
• $C^T$ — транспонированная матрица достижимости.
• $\&$ — логическое умножение (конъюнкция), поэлементно.

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

1. Матрица смежности $B$ и её степени:

$$B=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right),B^2=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right),B^3=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$$

(Примечание: $B^2$ показывает пути длины 2, например, из 1 в 4 есть путь $1\to 3\to 4$).

2. Матрица достижимости $C=E\vee B\vee B^2\vee B^3$: $C=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

3. Матрица сильной связности $S=C\&C^T$:

$$S=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)\&\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 0& 1& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& 1\end{array}\right)$$

• Блок $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ в правом нижнем углу показывает, что вершины 3 и 4 образуют сильную компоненту (взаимно достижимы).
• Вершины 1 и 2 образуют свои отдельные компоненты (на диагонали 1, но связей с другими в $S$ нет).

Матричные методы анализа графов

Нахождение количества путей

Пусть $B$ — матрица смежности орграфа. Если возвести матрицу смежности в квадрат ($B^2$), то элемент $b_{ik}^{(2)}$ будет равен числу путей длины 2, идущих из $x_i$ в $x_k$.

Обобщение Если $b_{ik}^p$ является элементом матрицы $B^p$, то $b_{ik}^p$ равно числу путей (не обязательно простых) длины $p$, идущих из $x_i$ в $x_k$.

Матрица достижимости ($C$)

Матрица достижимости содержит информацию о существовании пути между любыми вершинами. $c_{ij}=1$, если вершина $x_j$ достижима из $x_i$, иначе $0$.

Алгоритм построения Для графа с $n$ вершинами матрица достижимости определяется через булеву сумму степеней матрицы смежности: $C=E\vee B\vee B^2\vee \cdots \vee B^{n-1}$

• $E$ — единичная матрица (пути длины 0).
• $B^k$ — информация о путях длины $k$.
• $\vee$ — логическое сложение (дизъюнкция).

Матрица сильной связности ($S$)

Матрица сильной связности содержит информацию обо всех сильно связанных вершинах (вершины $x_i$ и $x_j$ взаимно достижимы). Элемент $s_{ij}=1$, если существует путь из $x_i$ в $x_j$ И из $x_j$ в $x_i$.

Алгоритм построения $S=C\&C^T$

• $C$ — матрица достижимости.
• $C^T$ — транспонированная матрица достижимости.
• $\&$ — логическое умножение (конъюнкция), поэлементно.

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

1. Матрица смежности $B$ и её степени:

$$B=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right),B^2=\left(\begin{array}{cccc}0& 1& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 1\end{array}\right),B^3=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right)$$

(Примечание: $B^2$ показывает пути длины 2, например, из 1 в 4 есть путь $1\to 3\to 4$).

2. Матрица достижимости $C=E\vee B\vee B^2\vee B^3$: $C=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)$

3. Матрица сильной связности $S=C\&C^T$:

$$S=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 1& 1& 1\\ 0& 1& 1& 1\end{array}\right)\&\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 0& 1& 1\end{array}\right)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 1& 1\end{array}\right)$$

• Блок $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ в правом нижнем углу показывает, что вершины 3 и 4 образуют сильную компоненту (взаимно достижимы).
• Вершины 1 и 2 образуют свои отдельные компоненты (на диагонали 1, но связей с другими в $S$ нет).

---

Эйлеровы пути и циклы

Эйлеров путь и цикл

Эйлеров путь (эйлерова цепь)

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

Эйлеров цикл (эйлерова линия)

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

Эйлеров граф

Это граф, содержащий эйлеров цикл.

Полуэйлеров граф

Это граф, содержащий эйлеров путь.

Необходимое и достаточное условия (Критерии)

Для неориентированного графа

Критерий существования эйлерова цикла

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

Критерий существования эйлерова пути

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

• Если таких вершин 0 — существует цикл (частный случай пути).
• Если таких вершин 2 — путь начинается в одной нечетной вершине и заканчивается в другой.

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

Для ориентированного графа

Критерий существования эйлерова цикла

Эйлеров цикл в ориентированном графе существует тогда и только тогда, когда граф сильно связан и для каждой вершины графа её входящая степень равна её исходящей степени ($d^{-}(v)=d^{+}(v)$).

Ориентированный граф $G=(V,E)$ содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда он слабо связен и существуют две вершины $p\in V$ и $q\in V$ (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами:

$$\begin{array}{c}\text{indeg}(q)=\text{outdeg}(q)+1\\ \text{indeg}(p)=\text{outdeg}(p)-1\end{array}$$

а все остальные вершины имеют одинаковые полустепени исхода и захода: $\text{outdeg}(v)=\text{indeg}(v)\forall v\in V\setminus \{p,q\}$

Алгоритм Флёри (1883)

Нахождение эйлерова цикла

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

Задача китайского почтальона (1962)

Постановка задачи (Мэй-Ку Куан)

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

Решение

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

Алгоритм решения

1. Перечислите все нечётные вершины.
2. Перечислите все совершенные паросочетания на этих нечётных вершинах.
3. Для каждого паросочетания найдите рёбра, соединяющие соответствующие вершины, с минимальным весом.
4. Найдите паросочетание, сумма весов которого минимальна.
5. Добавьте к исходному графу рёбра, найденные на Шаге 4 (дублирование ребер).
6. Длина оптимального маршрута китайского почтальона равна сумме всех исходных рёбер графа и сумме длин рёбер, добавленных на Шаге 5.
7. Постройте эйлеров цикл в полученном мультиграфе.

Практическое применение

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

---

Гамильтоновы пути и циклы

Определения

Гамильтонов путь (гамильтонова цепь)

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

Гамильтонов цикл

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

Условия существования (Неориентированный граф)

Необходимое и достаточное условие

Теорема Бонди-Хватала (1976)

Граф является гамильтоновым тогда и только тогда, когда его замыкание — гамильтонов граф. (Этот результат обобщает утверждения Дирака и Оре).

Замыкание графа Замыкание графа $G$ с $n$ вершинами строится добавлением в $G$ ребра $(u,v)$ для каждой пары несмежных вершин $u$ и $v$, сумма степеней которых не меньше $n$ ($\text{deg}(u)+\text{deg}(v)\ge n$). Операция повторяется, пока такие пары существуют.

Достаточные условия

(Из выполнения этих условий следует существование цикла, но обратное неверно).

Условие Дирака (1952)

Если каждая вершина соединена рёбрами более чем с половиной других вершин, то в графе есть гамильтонов цикл. $\forall v\in V:\text{deg}(v)\ge \frac{n}{2}$

Условие Оре (1960)

Пусть в графе $N$ вершин. Если сумма степеней любых двух несмежных вершин не меньше $N$, то в графе есть гамильтонов цикл. $\forall u,v\notin E:\text{deg}(u)+\text{deg}(v)\ge N$

Практическое применение

Задачи

• Организация путешествий.
• Доставка товаров.
• Распределение продуктов в сетях супермаркетов.

Задача коммивояжёра (TSP)

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