diff options
17 files changed, 2647 insertions, 54 deletions
diff --git a/graphs-exam/graphs-exam.pdf b/graphs-exam/graphs-exam.pdf Binary files differindex b6eea17..4cfeb9e 100644 --- a/graphs-exam/graphs-exam.pdf +++ b/graphs-exam/graphs-exam.pdf diff --git a/graphs-exam/graphs-exam.tex b/graphs-exam/graphs-exam.tex index 338b357..571c862 100644 --- a/graphs-exam/graphs-exam.tex +++ b/graphs-exam/graphs-exam.tex @@ -12,6 +12,8 @@ \usepackage{amssymb} \usepackage{braket} % \set \usepackage{hyperref} +\usepackage{graphicx} +\graphicspath{ {./images/} } \renewcommand{\emptyset}{\varnothing} \renewcommand{\qedsymbol}{$\blacksquare$} @@ -20,8 +22,15 @@ \input{style.tex} +\title{Теория графов} +\date{\the\year} + \begin{document} +\maketitle + +\tableofcontents + \chapter*{Введение} \section{Декартово произведение. Бинарные отношения. Пустое и универсальное @@ -309,7 +318,7 @@ $0_n$. \end{definition} \begin{definition} - Полный двудольный граф вида называется звездным графом или звездой. + Полный двудольный граф вида $K_{1,n}$ называется звездным графом или звездой. \label{def:star} \end{definition} @@ -602,6 +611,17 @@ layoff. Критерий графичности Эрдеша-Галлаи.} \end{definition} \begin{definition} + Немым изображением графа называют его изображение, в котором опущены имена + меток. +\end{definition} + +Очевидно, что два графа изоморфны $\iff$ они допускают одинаковое немое +изображение. + +Очевидно, что отношение изоморфизма является отношением эквивалентности. Классы +этого отношения называются абстрактными графами. + +\begin{definition} Метод канонических представителей: \begin{enumerate} \item Определить способ кодирования объектов; @@ -644,8 +664,8 @@ layoff. Критерий графичности Эрдеша-Галлаи.} \begin{definition} Два ребра $\set{u_1, v_1}$ и $\set{u_2, v_2}$ называются подобными, если существует автоморфизм $\varphi$, такой, что образом первого ребра будет - второе ребро ($\varphi(\set{u_1, v_1}) = \set{u_2, v_2}$). Если $\varphi(u) = - u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$. + второе ребро ($\varphi(\set{u_1, v_1}) = \set{u_2, v_2}$). Если $\varphi(u_1) + = u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$. \end{definition} \begin{definition} @@ -738,6 +758,15 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \section{Отказоустойчивые реализации. Вершинные и реберные расширения. Минимальные, неприводимые, тривиальные, точные расширения.} +Пусть граф является функциональной моделью некоторой технической системы. +Вершины графа соответствуют элементам, а рёбра --- связям. Элементы могут +иметь различные типы, и в этом случае вершинам приписывают метки. + +Система, представленная орграфом $\vec{G_1}$, моделируется системой, +представленной графом $\vec{G_2}$, если $\vec{G_1}$ вкладывается в $\vec{G_2}$ +с сохранением типов элементов (вершина одного типа переходит в вершину того же +типа). + \begin{definition} Под отказом элемента системы будем понимать удаление из графа системы соответствующей вершины и всех её рёбер или дуг. @@ -759,6 +788,14 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл Система $\Sigma^*$ --- $k$-отказоустойчивая реализация системы $\Sigma$. \end{definition} +Если рассматривать вместо отказов вершин отказы рёбер, то будет определение +рёберной отказоустойчивости. Если рассматривать отказы элементов (вершин или +рёбер), то будет комбинированная отказоустойчивость. + +Отказоустойчивость – это способность системы противостоять ошибке и продолжать +работу в присутствии этой ошибки. Два уровня – полная отказоустойчивость и +амортизация отказов. + \begin{definition} Система $\Sigma^*$ называется оптимальной $k$-отказоустойчивой реализацией (вершинной) системы $\Sigma$, если выполняются следующие условия: @@ -828,27 +865,13 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \begin{lemma} Если в графе $G$ минимальная из степеней вершин $d > 0$, то МВ-kР не содержит вершин степени меньше $d + k$. + \label{lem:mv-kr-less} \end{lemma} - -\begin{lemma} - Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин - $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$. -\end{lemma} - -\begin{lemma} - Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит - не менее, чем $kd$ дополнительных рёбер. -\end{lemma} - -\begin{lemma} - \textbf{TODO:} ЧТО?? - +\begin{proof} $G = (V, \alpha)$, $d > 0$ --- минимальная из степеней вершин. $G^* = (V^*, \alpha^*)$ и в $G^*$ $d(v) < d + k$. -\end{lemma} - -\begin{lemma} + Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин, смежных с $v$. (Если $d(v) < k$, то удаление всех вершин, смежных с $v$, и $k - d(v)$ произвольных вершин, отличных от $v$). @@ -856,24 +879,27 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл В получившемся графе степень вершины $v < d$. Очевидно, что $G$ нельзя будет вложить в получившийся граф, это противоречит предположению $\implies d(v) < d + k$. -\end{lemma} +\end{proof} \begin{lemma} - \textbf{TODO:} ЧТО?? №2 - + Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин + $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$. +\end{lemma} +\begin{proof} $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин. $G^* = (V^*, \alpha^*)$ и в $G^*$ менее чем $m + k$ вершин имеют степень $\geq d$. -\end{lemma} - -\begin{lemma} Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин наибольшей степени. В получившемся графе меньше, чем $m$ вершин будут иметь степень не меньшую $d$. И, очевидно, что граф $G$ нельзя будет вложить в получившийся граф. -\end{lemma} +\end{proof} \begin{lemma} + Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит + не менее, чем $kd$ дополнительных рёбер. +\end{lemma} +\begin{proof} $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин. В $G^*$ по крайней мере на $k$ вершин степени $\geq d$ больше, чем в графе @@ -882,11 +908,11 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл Рассмотрим граф, получающийся удалением $k$ вершин максимальной степени. Исходный граф по условию вкладывается в получившийся граф, а сам граф отличается от МВ-kР не менее, чем на $dk$ рёбер. -\end{lemma} +\end{proof} \begin{definition} Граф $G = (V, \alpha)$ называется $n$-вершинной цепью и обозначается $P_n$, - или его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким + если его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким способом, чтобы $\alpha$ имело вид: \begin{equation*} \alpha = \set{\set{v_i, v_{i + 1}}, i = \overline{1, n - 1}} @@ -894,13 +920,13 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \end{definition} \begin{definition} - Вершины $u$ и $v$ называются подобными, если существует автоморфизм $\varphi : - \varphi(u) = v$. -\end{definition} - -\begin{definition} - Граф, все вершины которого подобны, называется вершинно"=симметрическим - (вершинно"=транзитивным). + Граф $G = (V, \alpha)$ называется $n$-вершинным циклом и обозначается $C_n$, + если его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким + способом, чтобы $\alpha$ имело вид: + \begin{equation*} + \alpha = \set{\set{v_i, v_{i + 1}}, + i = \overline{1, n - 1} \cup \set{v_1, v_n}} + \end{equation*} \end{definition} \begin{theorem}[О МВ-1В цепи, Хейз] @@ -908,8 +934,8 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл $C_{n + 1}$. \end{theorem} \begin{proof} - По лемме ??? для любого МВ-1Р цепи не может содержать вершин степени меньше - двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$. + По лемме \ref{lem:mv-kr-less} для любого МВ-1Р цепи не может содержать вершин + степени меньше двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$. С другой стороны, цикл $C_{n + 1}$ имеет все вершины степени 2, то есть имеет минимально возможное число рёбер $\implies C_{n + 1}$ --- МВ-1Р цепи $P_n$. @@ -931,18 +957,91 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл Цикл $C_{n + 1}$ является ТВ-1Р цепи $P_n$. \end{definition} -\textbf{TODO:} Лекция 3, страница 67 --- Лекция 5 +\begin{theorem}[О МВ-1Р циклов, Хейз] + Графы, построенные по предлагаемым схемам, являются МВ-1Р циклов. + + \begin{center} + \includegraphics[width=0.8\textwidth]{lec4-mv-1r-hayes} + \end{center} + \label{thm:cycles-mv-1r} +\end{theorem} +\begin{proof} + По лемме \ref{lem:mv-kr-less} любое МВ-1Р цикла не может содержать вершин + степени $< 3$. + + С учётом теоремы Эйлера, число нечётных вершин должно быть чётно. Минимальное + вершинное 1-расширение цикла $C_n$ с чётным числом вершин не может иметь + все вершины степени 3 $\implies$ по крайней мере одна вершина должна иметь + степень $> 3$. Построенное расширение в точности удовлетворяет требованиям + минимальности. + + Непосредственной проверкой убеждаемся, что графы, построенные по предлагаемой + схеме, являются В-1Р соответствующего цикла $\implies$ предлагаемые схемы + позволяют строить МВ-1Р. +\end{proof} + +\begin{theorem}[МВ-1Р циклов, Абросимов] + Графы, построенные по предлагаемым схемам, являются МВ-1Р цикла с соответствующим + числом вершин и при $n > 5$ строят графы, не изоморфные соответствующим + реализациям из теоремы \ref{thm:cycles-mv-1r}. + + \begin{center} + \includegraphics[width=0.8\textwidth]{lec4-mv-1r-abrosimov} + \end{center} +\end{theorem} +\begin{proof} + \textbf{TODO}: Написать доказательство +\end{proof} + \section{Минимальные реберные расширения, основные свойства. Минимальные реберные 1-расширения цепей и циклов.} -\dots +\begin{theorem}[МР-1Р цепи, Харари, Хейз] + МР-1Р цепи $P_n$ при $n > 2$ является цикл $C_n$. Причём МР-1Р единственное + с точностью до изоморфизма. +\end{theorem} +\begin{proof} + \textbf{TODO}: Написать доказательство +\end{proof} + +\begin{theorem}[О МР-1Р цикла, Харари, Хейз] + Графы, построенные по схемам из теоремы \ref{thm:cycles-mv-1r}, позволяют + строить МР-1Р соответствующих циклов. + \begin{center} + \includegraphics[width=0.8\textwidth]{lec4-mr-1r-harari} + \end{center} +\end{theorem} + +\begin{theorem}[МР-1Р цикла, Абросимов] + Графы, построенные по предлагаемым схемам, являются МР-1Р цикла с + соответствующим числом вершин, и при $n > 6$ строят графы, не изоморфные + соответствующим реализациям из теоремы \ref{thm:cycles-mv-1r}. + \begin{center} + \includegraphics[width=0.8\textwidth]{lec4-mr-1r-abrosimov} + \end{center} +\end{theorem} \section{Связь точных расширений и симметричности.} -\dots +\begin{theorem} + Только полные и вполне несвязные графы $K_n$ и $0_n$ имеют ТВ-kР при $\forall + k \in \mathbb{N} > 1$. +\end{theorem} + +\begin{theorem} + При $k = 1$ граф является ТВ-kР $\iff$ он является вершинно"=симметрическим + графом (у него все вершины подобны). +\end{theorem} +\begin{theorem} + При $k = 1$ граф является ТР-kР $\iff$ он является рёберно"=симметрическим. +\end{theorem} +\begin{remark} + Для орграфов задача описания точных $k$-расширений пока не имеет полного + решения. +\end{remark} \chapter{Основные типы неориентированных графов} @@ -974,70 +1073,1661 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \label{def:chain} \end{definition} +\begin{definition} + Длиной пути называется количество входящих в его состав рёбер. + + Очевидно, что в $n$-вершинном графе цепь не может иметь длину больше, чем $n - + 1$, а цикл не может иметь длину больше, чем $n$. + \label{def:path-length} +\end{definition} + +\begin{definition} + Вершины $u$ и $v$ называются связанными в $G$, если существует путь, концами + которого они являются. + + Очевидно, что если вершины $u$ и $v$ связанные, то это возможно лишь тогда, + когда существует соединяющая их цепь. + \label{def:connected-vert} +\end{definition} + +\begin{definition} + Если вершины $u$ и $v$ связанные, то наименьшая из длин путей, соединяющих + $u$ и $v$, называется расстоянием между $u$ и $v$. Обозначается $d(u, v)$. + + Для неориентированного графа $d(u, v) = d(v, u)$. +\end{definition} + +\begin{definition} + Наибольшее из расстояний от вершины до всех оставшихся вершин называется + эксцентриситетом вершины. $E(u)$ --- эксцентриситет, $E(u) = \max d(u, v), + v \in V$. +\end{definition} + +\begin{definition} + Минимальное из значений эксцентриситетов вершин графа называется его радиусом + $r(G) = \min E(u)$, максимальное --- диаметром $d(G) = \max E(u)$. +\end{definition} + +\begin{definition} + Вершины, имеющие эксцентриситет, равный радиусу графа, называются + центральными. +\end{definition} + +\begin{definition} + Множество центральных вершин называется центром графа. +\end{definition} + +\begin{definition} + Вершины, эксцентриситет которых равен диаметру графа, называются окраинами или + периферийными, а множество таких вершин в графе называется окраиной или + периферией. +\end{definition} + +\begin{definition} + Будем считать, что каждая вершина удалена от себя на расстояние 0 и связана + сама с собой. + + Тогда отношение связности в графе $G$ будет отношением эквивалентности. +\end{definition} + +\begin{definition} + Классы отношения связность графа называются его связными компонентами или + просто компонентами. +\end{definition} + +\begin{definition} + Граф с универсальным отношением связности называется связным графом. Граф + с тождественным отношением связности называется вполне несвязным. +\end{definition} + \section{Теорема о связности двух нечетных вершин. Достаточное условие связности.} -\dots +\begin{theorem} + Если вершины $u$ и $v$ являются единственными нечётными вершинами графа $G$, + то они связаны в этом графе. +\end{theorem} +\begin{proof} + Предположим, противное, то есть $u$ и $v$ не связаны в графе $G = (V, \alpha)$. + Обозначим через $G_1$ и $G_2$ компоненты связности графа $G$, содержащие + соответственно вершины $u$ и $v$. + + В графе $G_1$ вершина $u$ является единственной нечётной вершиной, что + противоречит теореме Эйлера (количество нечётных вершин должно быть чётно). +\end{proof} + +\begin{theorem}[Достаточное условие связности] + Если граф $G = (V, \alpha)$ с $n$ и $m$ рёбрами такой, что для него + выполняется условие $m > C_{n - 1}^2 = \frac{(n - 1)(n - 2)}{2}$, то $G$ --- + связный. +\end{theorem} +\begin{proof} + От противного. Предположим, что в графе $G$ выполняется неравенство $m > C_{n + - 1}^2 = \frac{(n - 1)(n - 2)}{2}$ и он не является связным. + + Тогда граф $G$ имеет по крайней мере две компоненты. Пусть $G_1$ --- некоторая + компонента связности графа $G$ и пусть она содержит $k$ вершин. + + Рассмотрим два случая: + \begin{enumerate} + \item + $2 \leq k \leq n - 2$. В $G_2$ $(n - k)$ вершин. Каждое ребро графа $G$ + входит или в состав $G_1$, или в состав $G_2$. Если предположить, что + $G_1$ и $G_2$ --- полные графы, то число рёбер в них будет $C_k^2$ и + $C_{n - k}^2$, $m \leq C_k^2 + C_{n - k}^2$. + \begin{align*} + C_k^2 + C_{n - k}^2 &= \frac{k(k - 1)}{2} + \frac{(n - k)(n - k - 1)}{2} = \\ + &= \frac{k^2 - k + n^2 - nk - n - nk + k^2 + k}{2} = \\ + &= \frac{n^2 - (2k + 1)n + 2k^2}{2} + \end{align*} + + Из условия теоремы: $m > C_{n - 1}^2 = \frac{(n - 1)(n - 2)}{2}$. + + \begin{align*} + C_{n - 1}^2 - m &\geq C_{n - 1}^2 - (C_k^2 + C_{n - k}^2) = \\ + &= \frac{(n - 1)(n - 2)}{2} - \frac{n^2 - (2k + 1)n + 2k^2}{2} = \\ + &= kn - n - k^2 + 1 = (k - 1)n - (k^2 - 1) = \\ + &= (k - 1)(n - (k + 1)) > 0 + \end{align*} + + Получаем $C_{n - 1}^2 \geq m$. Противоречие. + \item + Пусть $G_1$ содержит только одну вершину, $k = 1$. Тогда в $G_2$ входит + $n - 1$ вершина. $m \leq C_{n - 1}^2$ --- противоречие. + + Аналогично при $k = n - 1$. + \end{enumerate} +\end{proof} \section{Точки сочленения, мосты.} -\dots +\begin{definition} + Вершина, удаление которой приводит к увеличению числа компонент связности, + называется точкой сочленения. А ребро с таким свойством называется мостом. +\end{definition} \section{Деревья. Лист и корень. Характеристическая теорема о деревьях. Теорема о центре дерева.} -\dots +\begin{definition} + Дерево --- связный граф без циклов. + + При $n = 1$ получается тривиальное дерево. При $n = 4$ получается $P_4$ и + $K_{1, 3}$. При $n = 5$ получается $P_5, K_{1, 4}$ и ещё одно дерево. +\end{definition} + +\begin{definition} + Вершина дерева, имеющая степень 1, называется висячей вершиной или листом. +\end{definition} + +Дерево может иметь выделенную вершину --- корень. Дерево с корнем называется +корневым, а без корня --- свободным. + +\begin{theorem}[О характеризации деревьев, Кэли] + Граф с $n$ вершинами и $m$ рёбрами $\iff$ является деревом, когда выполняется + одно из следующих условий: + \begin{enumerate} + \item Любые две вершины графа соединены единственной цепью; + \item Граф связный и $n = m + 1$; + \item Граф ациклический и $n = m + 1$. + \end{enumerate} +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть граф $G$ имеет $n$ вершин, $m$ рёбер и является деревом. Покажем, что + условия 1--3 выполняются. + + Пусть $u$ и $v$ --- две вершины $G$, между которыми существует по крайней + мере две различные цепи. Очевидно, что в $G$ можно выделить цикл. + + Докажем, что $n = m + 1$. Рассмотрим деревья при $n = 1, 2$. + \begin{align*} + n = 1 &\implies m = 0 \\ + n = 2 &\implies m = 1 + \end{align*} + + Пусть это справедливо для деревьев с числом вершин меньше, чем $n$. + + Рассмотрим $T_{n + 1}$. Пусть $u$ и $v$ --- две смежные вершины в этом + дереве. Удалим из $T$ ребро $\set{u, v}$. В силу первого пункта, $\set{u, v}$ + --- мост, и после его удаления дерево $T$ распадётся на две компоненты + (два дерева). + + В одном из них $k$ вершин, во втором --- $(n + 1) - k$ вершин. + \begin{align*} + &G_1 : n_1 = k = m_1 + 1 \\ + &G_2 : n_2 = (n + 1) - k = m_2 + 1 \\ + &\implies n_1 + n_2 = n + 1 = (m_1 + 1 + m_2) + 1 \\ + &\implies n + 1 = m + 1 + \end{align*} + + \textbf{Достаточность.} + + \begin{enumerate} + \item + Пусть в графе $G$ между любыми двумя вершинами существует единственная + цепь. Предположим, что в нём есть цикл, содержащий вершины $u$ и $v$. + Тогда между вершинами $u$ и $v$ будет две цепи $\implies$ противоречие + $\implies$ $G$ --- связный и не содержит циклов, то есть --- это дерево. + \item + $G$ --- связный и $n = m + 1$. Покажем, что в $G$ нет циклов. + + Предположим, что это не так. Удалим из $G$ одну висячую вершину вместе с + её ребром. Получим граф $G_1 : 1 = n - m = n_1 - m_1$. Продолжаем + процесс с графом $G_1$ пока будут оставаться висячие вершины. + \begin{equation*} + 1 = n - m = n_1 - m_1 = \dots = n_k - m_k + \end{equation*} + + По теореме Эйлера $\ds\sum_{v_i \in G_k} d(v_i) = 2m_k$. + + $d(v_i) \geq 2 \implies 2n_k \leq \sum_{i = 1}^{n_k} d(v_i) = 2m_k$. + + Получаем $n_k \leq m_k$ --- противоречие. + \item + Пусть $G$ --- ациклический и $n = m + 1$. Допустим, что $G$ связный. + + Пусть это не так. $G = G_1 \cup G_2 \cup \dots \cup G_k,\, k \geq 2$. + Так как $G$ ациклический, то любая его компонента ациклический граф. + Причём он является связным, то есть деревом. Для любой компоненты выполняется + $n_i = m_i + 1,\, i = 1, \dots, k$. + + Тогда имеет место следующее: + \begin{equation*} + n = \sum_{i = 1}^k n_i = \sum_{i = 1}^k (m_i + 1) = \sum_{i = 1}^k + m_i + k = m + k + \end{equation*} + + Так как $k \geq 2$, получаем противоречие. + \end{enumerate} +\end{proof} + +\begin{theorem}[О центре дерева, Жордан] + Центр дерева состоит либо из одной вершины, либо из двух смежных вершин. +\end{theorem} +\begin{proof} + Рассмотрим маленькие деревья. $T_1$ --- центр состоит из одной вершины. + $T_2$ --- центр состоит из двух смежных вершин. + + ММИ. Пусть справедливо для $T_n$. Рассмотрим $T_{n + 1}$. + + Удалим в дереве $T_{n + 1}$ все листья. Очевидно, что для любой вершины + дерева эксцентриситет достигается на висячих вершинах. Удаление всех листьев + приведёт к уменьшению эксцентриситета оставшихся вершин на 1. Следовательно, + в дереве $T_{n + 1}$ и в получившемся после удаления листьев дереве центры + будут состоять из одних и тех же вершин. Получившееся дерево будет иметь не + более $n$ вершин. Для него выполняется предположение. + + Следовательно, верно и для $T_{n + 1}$. +\end{proof} + +\begin{definition} + Дерево с одной центральной вершиной называется центральным. С двумя --- + бицентральным. +\end{definition} \section{Изоморфизм деревьев: алгоритм Эдмондса, алгоритм WAV. Кодирование деревьев.} -\dots +\begin{itemize} + \item Алгоритм проверяет изоморфизм деревьев, + \item Все вершины дерева получают метки, + \item Если метки корней совпадут, деревья являются изоморфными. +\end{itemize} + +Два корневых дерева будут изоморфны только если количество уровней и число +вершин на этих уровнях будет одинаковым. + +Алгоритм: +\begin{enumerate} + \item + Каждой вершине будем приписывать метки следующим образом: листовые вершины + --- метка 0. Для остальных вершин расставление меток будет начинаться с + последнего уровня (от листьев); + \item + На текущем уровне каждая вершина получает метку, являющуюся списком вершин + --- её потомков, то есть вершин, смежных с ней и расположенных уровнем ниже + (или выше, в зависимости от нумерации уровней). Кроме этого к метке + добавляется длина наибольшей цепи от вершины до достижимых из неё листьев + по пути сверху вниз; + \item + Получившиеся кортежи сравниваются с соответствующими кортежами второго + дерева. Полученные кортежи на уровне упорядочиваются лексикографически и + нумеруются. Если соответствие установить нельзя, то деревья неизоморфны. + \item + Если соответствие удалось установить, то вершина получает новую метку, + равную номеру её кортежа, и переходим дальше на шаг 2. +\end{enumerate} + +Для использования алгоритма Эдмондса для проверки изоморфизма двух свободных +деревьев необходимо выполнить этот алгоритм один раз, если деревья являются +центральными, и два раза, если деревья являются бицентральными. + +При этом в качестве корня первого дерева выбирается любая из центральных вершин, +и алгоритм дважды применяется ко второму дереву, у которого в качестве корня +выбирается каждая из центральных вершин. + +Если хотя бы в одном из двух случаев получили совпадение всех кортежей, то +деревья изоморфны. + +Другой подход --- между двумя центральными вершинами добавляется вершина, и +алгоритм выполняется для такого дерева. + +\textbf{TODO:} другие кодировки. + +\textbf{Алгоритм WAV (Walk-around valency code)}. Данный алгоритм позволяет +построить канонический код свободного дерева. На каждом шаге алгоритма есть +множество $A$ помеченных вершин и множество $B$ вершин без меток. Метки --- +строки из чисел. + +\begin{enumerate} \setcounter{enumi}{-1} + \item Множество $A$ состоит из листьев дерева, каждый лист имеет метку 0; + \item + Составим множество $R$ таких вершин из $B$ (то есть вершин без меток), + которые смежны максимум с одной другой вершиной из $B$. + \item + Для каждой вершины $x \in R$ составляем метку и меток смежных вершин, + которые уже принадлежат $A$. Записываем эти метки в лексикографическом + порядке и в качестве префикса добавляем количество этих меток (то есть + количество смежных вершин из $A$). + \item + \begin{enumerate} + \item + Если в $B$ остаётся только одна вершина $x$, то её метка --- код + дерева, а алгоритм завершён, + \item + Если в $B$ ровно два элемента, определим, какая из меток идет первой в + лексикографическом порядке. Вставляем эту метку после первого элемента + другой метки. Затем увеличиваем на 1 первый элемент получившейся + последовательности. В этом случае получается, что мы выбираем одну из + центральных вершин нашего бицентрального дерева в качестве корня. И эта + метка --- код дерева. + \item + Иначе мы перемещаем вершины, входящие на этом шаге в $R$, из множества + $B$ в $A$. Переходим на шаг 1. + \end{enumerate} +\end{enumerate} \section{Уровневые коды. Канонические коды. Код Прюфера.} -\dots +\begin{definition} + Канонический код графа --- выбранный по определённым правилам один из кодов + изоморфных графов. Уникальная строка, которая не зависит от порядка + нумерации вершин. +\end{definition} + +У изоморфных графов одинаковые канонические коды, у неизоморфных --- разные. + +\begin{definition} + Каноническая нумерация --- это нумерация (перестановка) вершин графа, + гарантирующая, что изоморфные графы будут пронумерованы одинаково. +\end{definition} + +\textbf{TODO}: другие коды. \section{Сеть. Остовное (покрывающее) дерево. Алгоритмы Прима и Краскала.} -\dots +\begin{definition} + Сеть --- связный граф, в котором каждому ребру приписано некоторое число. + Это число называется весом, длиной, стоимостью и т.д. в зависимости от + способа интерпретации. Обозначается $w(u, v)$. В неориентированном графе + $w(u, v) = w(v, u)$. +\end{definition} + +\begin{definition} + Граф $G^* = (V^*, \alpha^*)$ называется покрывающим деревом или остовным + деревом для связного графа $G = (V, \alpha)$, если $G^*$ --- дерево, + $V^* = V,\, \alpha^* \subseteq \alpha$. +\end{definition} + +\begin{definition} + Вес остовного дерева --- сумма весов всех рёбер сети, входящих в состав этого + дерева. +\end{definition} + +\begin{definition} + Покрывающее дерево называется минимальным, если его вес наименьший среди + весов всех покрывающих деревьев данной сети. +\end{definition} + +Для поиска минимального остовного дерева хорошо применимы <<жадные алгоритмы>>. +Их суть состоит в следующем: на очередном шаге выбирается <<безопасное>> +ребро наименьшего веса (то есть локально-оптимальное решение). + +\begin{definition}[Алгоритм Краскала] + Минимальное остовное дерево строится следующим образом: + \begin{enumerate} + \item Все рёбра сети упорядочены в порядке возрастания весов; + \item + Первое по списку ребро окрашивается в некоторый цвет, а его концы + помечаются как принадлежащие одной компоненте (приписывается одинаковая + метка); + \item + Выберем следующее по списку ребро. Возможны следующие случаи: + \begin{enumerate} + \item + Ребро соединяет две вершины, принадлежащие одной компоненте, ребро + пропускается; + \item + Одна из вершин ребра уже имеет метку, а вторая --- нет. Ребро + окрашивается, вторая вершина получает ту же метку, что и первая; + \item + Концы ребра имеют различные метки (то есть принадлежать различным + компонентам). Ребро окрашивается, две компоненты объединяются в одну; + \item + Концы ребра не имеют меток, то есть ещё не попали ни в какую + компоненту. Ребро окрашивается, а его концы образуют новую компоненту + с новой меткой. + \end{enumerate} + \item + Если все рёбра просмотрены, то алгоритм завершён, и окрашенные рёбра + образуют МОД, иначе --- переход к шагу 3. + \end{enumerate} +\end{definition} + +\begin{theorem} + Описанный алгоритм приводит к построению минимального остовного дерева. +\end{theorem} + +\begin{remark} + В алгоритме основная вычислительная сложность заключена на этапе 1, где + осуществляется сортировка рёбер $O(m \log m)$. На этапе 3 последовательно + просматриваются все рёбра $O(m)$. В общем случае сложность $O(m \log m)$. + + Если веса --- натуральные числа, не превышающие $k$, то для сортировки можно + использовать математическую сортировку или сортировку подсчётом $O(m + k)$. +\end{remark} + +\begin{definition}[Алгоритм Прима] + Выбор безопасных рёбер (этап 3) отличается от алгоритма Краскала тем, что + безопасным считается ребро только из пункта б). + + В алгоритме Прима построение остовного дерева выглядит как увеличивающаяся + единственная компонента, а в алгоритме Краскала несколько компонент сливаются + в одну. +\end{definition} \section{Укладки графов. Укладки на сфере и в пространстве. Планарные графы. Планарность деревьев.} -\dots +\begin{definition} + Укладкой графа в пространстве $L$ называется изображение графа, при котором + вершинам графа соответствуют точки пространства, рёбрам --- жордановые + кривые, при этом рёбра могут пересекаться только, быть может в вершинах. +\end{definition} + +\begin{definition} + Укладка графа в пространстве $L = R^2$ (на плоскости) называется плоским + изображением графа. +\end{definition} + +\begin{definition} + Граф, допускающий укладку на плоскости, называется планарным. +\end{definition} + +\begin{theorem} + Всякий граф допускает укладку в $R^3$. +\end{theorem} +\begin{proof} + Построим в пространстве $R^3$ прямую $l$. Выберем на ней $n$ различных + точек по числу вершин заданного графа. Проведём через $l$ $m$ различных + плоскостей по числу рёбер. Каждое ребро графа изобразим в виде полуокружности, + соединяющей соответствующие точки на прямой $l$ и лежащей в собственной + плоскости. + + Очевидно, что рёбра могут пересекаться только в точках, расположенных на + прямой $l$, то есть в вершинах графа. +\end{proof} + +\begin{definition} + Граф допускает укладку на сфере $\iff$ он планарный (то есть допускает + укладку на плоскости). +\end{definition} +\begin{proof} + Установим проективное отношение для изображений на сфере и на плоскости. + \begin{enumerate} + \item + Плоскость $\to$ сфера. + + Пусть граф изображён в плоскости $\alpha$. Разместим сферу, на которой + требуется изобразить граф так, чтобы она касалась $\alpha$ в точке $S$. + + Обозначим диаметрально противоположную для $S$ точку через $N$. Каждой + точке $A$ на плоскости $\alpha$ сопоставим точку $A'$ на сфере, которая + является пересечением прямой $NA$ со сферой. + + В силу взаимно однозначного соответствия, если исходный граф допускает + укладку на плоскости, то он будет допускать укладку на сфере. + + \item + Сфера $\to$ плоскость. + + Проекция графа со сферы на плоскость определяется обратным + преобразованием. + + То есть каждой точке $A'$ сферы будет соответствовать точка $A$ плоскости + $\alpha$, которая является пересечением прямой $NA'$ с плоскостью + $\alpha$. + \end{enumerate} +\end{proof} + +\begin{theorem}[О планарности деревьев] + Всякое дерево является планарным графом. +\end{theorem} +\begin{proof} + Пусть $T = (V, \alpha)$ --- некоторое дерево. $v_0 \in V$ --- произвольная + вершина --- корень. Изобразим дерево поуровнево. Первый уровень --- корневая + вершина. Второй --- вершины, смежные с корневой. + + На $i$-ом уровне расположены вершины, которые удалены от корневой на + расстояние $i - 1$ (это будут вершины, смежные с вершинами $i - 1$ уровня и не + уложенные ранее). Вершины $i$-го уровня укладываются слева направо в порядке + следования смежных с ними вершин $i - 1$ уровня и так далее. + + Очевидно, что получим плоское изображение данного дерева. +\end{proof} + +\begin{definition} + Радиальная поуровневая укладка дерева --- поуровневая укладка дерева, когда + уровни имеют вид концентрических окружностей. +\end{definition} \section{Грань. Теорема Эйлера и её обобщения. Триангуляция, максимально плоский граф. Следствия из теоремы: если всякая грань k-элементный цикл, число ребер в триангуляции, необходимое условие планарности, степень вершины в триангуляции.} -\dots +Пусть дан граф $G = (V, \alpha)$ в плоском изображении. + +\begin{definition} + Гранью графа $G$ в плоском изображении называется область плоскости, + ограниченная рёбрами графа. Одной из граней является внешняя грань, + представляющая собой бесконечную по протяжённости часть плоскости. + + Количество граней в плоском изображении обозначается $r$ (иногда $f$). +\end{definition} + +\begin{theorem}[Формула Эйлера] + В плоском изображении связного планарного графа справедливо $n - m + r = 2$, + где $n, m, r$ соответственно число вершин, рёбер и граней графа. +\end{theorem} +\begin{proof} + Пусть дан граф $G = (V, \alpha)$ в плоском изображении. Предположим, что + $G$ --- дерево. У дерева $r = 1,\, m = n - 1$. Проверяем: + \begin{align*} + n - n + 1 + 1 &= 2 \\ + 2 &= 2 + \end{align*} + + Пусть граф $G$ является связным, но не является деревом. Следовательно, в нём + есть хотя бы один цикл. Удалим из любого цикла графа $G$ некоторое ребро. + + Полученный граф обозначим $G_1$. Очевидно, что $G_1$ связный и является + плоским. При этом $n_1 = n,\, m_1 = m - 1,\, r_1 = r - 1$. Таким образом, $n_1 + - m_1 + r_1 = n - m + 1 + r - 1 = n - m + r$. + + Продолжим рассуждения с графом $G_1$, если он содержит цикл. Пусть в + результате были получены графы $G_1, G_2, \dots, G_k$, где $G_k$ --- последний + граф, полученный по рассматриваемой процедуре, и он не содержит циклов. + Следовательно, $G_k$ --- дерево. При этом $n_1 - m_1 + r_1 = n_k - m_k + r_k = + n - m + r = 2$. +\end{proof} + +\begin{remark} + Для несвязного графа $n - m + r = k + 1$, где $k$ --- количество компонент + связности. +\end{remark} + +\begin{corollary} + Если в каждом плоском изображении графа всякая грань является $k$-элементным + циклом, то $\ds m = \frac{k(n - 2)}{k - 2}$. +\end{corollary} +\begin{proof} + Каждая грань --- $k$-угольник, количество граней равно $r$. Каждое ребро + будет учитываться дважды, как граница двух граней: $rk = 2m$. Отсюда $\ds r = + \frac{2m}{k}$. По формуле Эйлера: $2 = n - m + r = n - m + \ds\frac{2m}{k}$. + $2k = nk - mk + 2m$, отсюда $m = \ds\frac{k(n - 2)}{k - 2}$. +\end{proof} + +\begin{definition} + Плоский граф (конкретное изображение планарного графа на плоскости) называется + триангуляцией, если все его грани являются треугольниками. +\end{definition} + +\begin{definition} + Граф называется максимально плоским, если к нему нельзя добавить рёбра так, + чтобы получившийся граф снова был плоским. + + Очевидно, что граф является плоским $\iff$ он представляет собой триангуляцию. +\end{definition} + +\begin{corollary} + Во всякой триангуляции $m = 3n - 6$. +\end{corollary} +\begin{proof} + В любой триангуляции $3r = 2m$, то есть $r = \frac{2}{3}m$. + + По формуле Эйлера: $2 = n - m + r = n - m + \frac{2}{3}m = n - \frac{1}{3}m$, + $6 = 3n - m$. +\end{proof} + +\begin{corollary}[Необходимое условие планарности] + Во всяком планарном графе $m \leq 3n - 6$. +\end{corollary} +\begin{proof} + Пусть граф $G$ --- планарный, и задано его плоское изображение. + + Если одна из его граней не является треугольником, то проведя нужное + количество диагоналей, можно получить триангуляцию. В полученной + триангуляции выполняется $m = 3n - 6$. +\end{proof} + +\begin{corollary} + Во всякой триангуляции существует вершина, степень которой $\leq 5$. +\end{corollary} +\begin{proof} + В любой триангуляции $m = 3n - 6 \implies 6 = 3n - m$. + \begin{align*} + 6 &= 3n - \frac{1}{2} \sum_{i = 1}^n d(v_i) \\ + 12 &= 6n - \sum_{i = 1}^n d(v_i) = \sum_{i = 1}^n (6 - d(v_i)) \\ + \sum_{i = 1}^n (6 - d(v_i)) &= 12 > 0 + \end{align*} + + Существует $i$, что слагаемое $(6 - d(v_i)) > 0$. Отсюда $d(v_i) \leq 5$. +\end{proof} \section{Графы типа 1 и типа 2. Стягивание ребра, минор. Критерии планарности (Понтрягин-Куратовский, Вагнер). Прямолинейное изображение. Род поверхности, род графа, число скрещиваний.} -\dots +\begin{definition} + Назовём подразбиением ребра $\set{u, v}$ граф, который получается из исходного + графа удалением ребра $\set{u, v}$, добавлением вершины $w$ и двух рёбер + $\set{u, w}$ и $\set{w, v}$. +\end{definition} + +\begin{definition} + Говорят, что $G_1$ и $G_2$ гомеоморфны, если они могут быть получены из + некоторого графа $G$ c помощью соответствующей последовательности + подразбиения рёбер. +\end{definition} + +\begin{definition} + Графом типа 1 называются граф, гомеоморфные графу $K_5$. +\end{definition} + +\begin{definition} + Графы типа 2 --- графы, гомеоморфные $K_{3,3}$. +\end{definition} + +\begin{theorem}[Критерий планарности графов, Понтрягин-Куратовский] + Граф является планарным $\iff$ среди его частей нет графов типа 1 и 2. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Достаточно доказать, что $K_5$ и $K_{3,3}$ не планарны. Так как очевидно, что + подразбиение рёбер не изменяет планарности графа. + \begin{enumerate} + \item + $K_5$. $n = 5,\, m = C_5^2 = 10$. По следствию 3, если бы $K_5$ был + планарным, то должно было бы выполняться $m \leq 3n - 6$. + \begin{align*} + 10 &\leq 15 - 6 \\ + 10 &\leq 9 + \end{align*} + + Получили противоречие. + + \item + $K_{3,3}$. $n = 6,\, m = 9$. Если бы граф был планарен, то в его плоском + изображении имела бы место формула Эйлера. И тогда $r = 5$. Заметим, что + в $K_{3,3}$ отсутствуют трёхэлементные циклы. Следовательно, в плоском + изображении каждая грань содержала бы как минимум 4 ребра. Тогда $r = + \frac{2m}{k}$. Отсюда $\frac{4 \cdot 5}{2} \leq m \implies 10 \leq 9$. + + Получили противоречие. + \end{enumerate} +\end{proof} + +\begin{definition} + Стягивание ребра --- это операция, которая удаляет ребро из графа, а до + этого связанные ребром вершины сливаются в одну вершину. +\end{definition} + +\begin{definition} + Граф $H$ называется минором графа $G$, если $H$ можно получить из $G$ + удалением и/или стягиванием рёбер графа $G$. Граф $G$ называется стягиваемым к + графу $H$. +\end{definition} + +\begin{theorem}[Критерий планарности, Вагнер] + Граф является планарным $\iff$ графы $K_5$ и $K_{3,3}$ не являются его + минорами. +\end{theorem} + +\begin{definition} + Прямолинейным изображением графа называется такое изображение, в котором все + рёбра являются отрезками прямых. +\end{definition} + +\begin{theorem}[О прямолинейном изображении планарных графов, Фари] + Всякий планарный граф допускает плоское прямолинейное изображение. +\end{theorem} + +\begin{definition} + Граф, который нельзя уложить на плоскости, но можно уложить на торе, + называются тороидальными. +\end{definition} + +\begin{definition} + Род поверхности --- это максимальное число простых замкнутых кривых, не + разделяющих эту поверхность. Обозначим через $g$. +\end{definition} + +У тора род поверхности равен 1. Это сфера с одной <<ручкой>> или плоскость с +одним мостом. Род поверхности равен количеству <<ручек>>. + +\begin{definition} + Род графа --- минимальный род поверхности, на которой можно уложить этот граф. + Обозначается $g(G)$. Формула Эйлера с родом: $n - m + r = 2 - 2g$. + \begin{align*} + g(K_n) &= \left\lceil \frac{(n - 3)(n - 4)}{12} \right\rceil \\ + g(K_{n,n}) &= \left\lceil \frac{(n - 2)^2}{4} \right\rceil + \end{align*} +\end{definition} + +\begin{definition} + Число скрещиваний $cr(G)$ графа $G$ --- наименьшее число пересечений, получаемых + при изображении графа на плоскости. + + Очевидно, $cr(G) = 0 \iff$ граф планарный. +\end{definition} \section{Эйлеровы графы. Критерий эйлеровости графа. Критерий существования эйлерова пути.} -\dots +Рассмотрим неориентированный граф $G = (V, \alpha)$ с $n$ вершинами и $m$ +рёбрами. Максимальная длина пути в таком графе есть $m$, максимальная длина +простого пути --- $n$. + +\begin{definition} + Путь длины $m$ (то есть состоящий из всех рёбер графа) называется эйлеровым + путём. +\end{definition} + +\begin{definition} + Циклический эйлеров путь называется эйлеровым циклом (эйлеров цикл в общем + случае не является циклом, так как может не являться простым путём). +\end{definition} + +\begin{definition} + Граф, содержащий эйлеров цикл, называется эйлеровым. +\end{definition} + +\begin{definition} + Граф, содержащий эйлеров путь, но не содержащий эйлеров цикл, называется + полуэйлеровым. +\end{definition} + +\begin{itemize} + \item Число нечётных вершин графа должно быть чётно; + \item + Если все вершины графа чётные, то можно начертить этот граф без отрыва + карандаша от бумаги; + \item + Если ровно две вершины графа нечётные, то можно начертить этот граф без + отрыва карандаша от бумаги, при этом нужно начинать с одной из нечётных + вершин и завершить его в другой нечётной вершине; + \item + Граф с более чем двумя нечётными вершинами невозможно начертить одним + росчерком. +\end{itemize} + +\begin{definition} + Плоская замкнутая кривая называется уникурсальное, если она может быть + нарисована, не отрывая перо от бумаги и никакой её участок не проходится + более одного раза. + + Очевидно, что кривая будет уникурсальной $\iff$ она является контуром эйлерова + графа. +\end{definition} + +\begin{theorem}[Критерий эйлеровости графа] + Связный граф является эйлеровым $\iff$ все его вершины чётные. + \label{thm:euler-crit} +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + $G = (V, \alpha)$ --- эйлеров граф. Пусть в нём существует эйлеров путь $C$. + Пусть $u$ --- начальная и конечная вершина $C$. Отправимся из $u$ по $C$. + Пусть $v$ --- некоторая промежуточная вершина по пути $C$. + + Путь $C$ может закончиться только вершиной $u$, следовательно, заходя в $v$ по + ребру пути $C$, мы можем выйти из неё по ещё не пройденному пути $C$. Таким + образом, в каждой промежуточной вершине $v$ все рёбра разбиваются на пары + вход-выход по отношению к пути $C$. + + Вершина $u$ может просматриваться по $C$ много раз. Рёбра, которым она + принадлежит, тоже могут быть сгруппированы парами вход-выход, за исключением + первого и последнего ребра пути $C$, которое также составляет пару. + + Таким образом, каждая вершина графа $G$ принадлежит чётному числу рёбер, + следовательно, является чётной. + + \textbf{Достаточность.} + + $G = (V, \alpha)$ --- связный граф и все вершины чётные. Покажем, что в $G$ + существует циклический эйлеров путь. + + Выберем произвольную вершину $u$ графа $G$. Отправимся из неё, двигаясь + по рёбрам графа. Каждое пройденное ребро будем окрашивать. Так как все + вершины чётные, то любая вершина графа $G$ принадлежит чётному числу рёбер. + Следовательно, войдя в некоторую вершину $v$, мы имеем возможность выйти из + неё по ещё не окрашенному ребру. + + Очевидно, что путь может окончиться только в вершине $u$, когда последнее + ребро составит пару первому. Обозначим получившийся путь $C_1$. Если $C_1$ + содержит все рёбра графа, то он является эйлеровым, и мы закончили построение. + + Предположим, что не все рёбра графа оказались окрашенными. В силу связности + графа, не нарушая общности, можно считать, что одно из неокрашенных рёбер + имеет своим концом вершину $v$, входящую в $C_1$. + + Продолжаем построение циклического пути из вершины $v$ по неокрашенным рёбрам. + Повторяя рассуждения, путь закончится в $v$, обозначим его $C_2$. + + Рассмотрим в графе $G$ новый циклический путь $u C_1 v C_1 u$. Очевидно, что + построенный путь является циклическим и содержит все рёбра, включающиеся в + $C_1$ и $C_2$. Кроме того, построенный путь содержит, по крайней мере, на 3 + ребра больше, чем $C_1$. + + Если все рёбра оказались окрашенными, то построение завершено. + + Иначе продолжаем процедуру, которая в силу конечности графа, завершится + построением циклического эйлерова пути. +\end{proof} + +\begin{theorem}[Критерий существования эйлерова пути между различными вершинами] + Для того, чтобы в связном графе $G$ существует эйлеров путь, соединяющий две + различные вершины $u$ и $v$, необходимо и достаточно, чтобы $u$ и $v$ были + единственными нечётными вершинами графа $G$. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть в $G$ существует эйлеров путь, соединяющий две различные вершины $u$ и + $v$. Отправимся из $u$ в $v$ по этому пути. Все рёбра в промежуточных вершинах + разобьются на пары вход-выход. Без пары останутся только первое и последнее + ребро пути. + + \textbf{Достаточность.} + + Пусть $u$ и $v$ --- единственные нечётные вершины в связном графе $G$. + Рассмотрим два случая: + \begin{enumerate} + \item + $\set{u, v} \in \alpha$, то есть смежны. Удалим ребро $\set{u, v}$ из $G$, + то, что осталось обозначим $G_1$. + \begin{enumerate} + \item + $G_1$ --- связный. В $G_1$ все вершины имеют чётную степень. + Следовательно, по теореме \ref{thm:euler-crit} в графе $G_1$ + существует циклический эйлеров путь $C$. Тогда в графе $G$ можно + построить эйлеров путь, начиная от $u$: $u C u v$. + \item + $G_1$ --- несвязный. Тогда $G_1$ разрывается на две компоненты: + $G_{11}$ и $G_{12}$. Обе компоненты по теореме \ref{thm:euler-crit} + являются эйлеровыми графами $\implies$ содержат циклические эйлеровы + пути $C_1$ и $C_2$. Тогда в графе $G$ строят эйлеров путь: $u C_1 u v + C_2 v$. + \end{enumerate} + \item + $u$ и $v$ не смежны. Рассмотрим граф $G_2$, который получается из $G$ + добавлением ребра $\set{u, v}$. В графе $G_2$ все вершины окажутся + чётными, сохранится связность. Следовательно, граф $G_2$ является + эйлеровым, в нём существует циклический эйлеров путь $C$. + + Пройдём по $C$ из $v$, выбрав первым ребром ребро $\set{u, v}$. Закончим в + $v$. Теперь пройдём этот же путь в обратном порядке, исключив на начальном + шаге ребро $\set{u, v}$. Очевидно, что этот путь будет эйлеровым путём в + графе $G$, соединяющим вершины $u$ и $v$. + \end{enumerate} +\end{proof} \section{Гамильтоновы графы. Доказательство с нулевым разглашением гамильтонова цикла. Теорема Оре. Теорема Дирака (следствие т. Оре). Достаточное условие Поша. Достаточное условие Хватала.} -\dots +\begin{definition} + Цепь длиной $n - 1$ в $n$-вершинном графе называется гамильтоновой цепью. +\end{definition} + +\begin{definition} + Цикл длины $n$ в таком графе называется гамильтоновым циклом. Таким образом, + гамильтонов цикл --- цикл, проходящий по всем вершинам графа. +\end{definition} + +\begin{definition} + Граф, содержащий гамильтонов цикл, называется гамильтоновым. +\end{definition} + +Двудольный граф может быть гамильтоновым только если в его долях равное +количество вершин (необходимое условие). + +\begin{theorem}[Доказательство с нулевым разглашением] + Гамильтонов цикл для больших графов. $G$ --- большой граф. Пегги --- + доказывающая сторона, знает гамильтонов цикл в $G$. Виктор --- проверяющая + сторона. Пегги хочет доказать Виктору, что она знает гамильтонов цикл, при + этом: + \begin{enumerate} + \item Не выдавая при этом ни самого цикла, ни какой-либо информации о нём; + \item + Проверяющий (Виктор) не сможет на основе полученной информации доказать, + что он знает гамильтонов цикл. + \end{enumerate} + + Раунд протокола: + \begin{enumerate} + \item Пегги создаёт граф $H$, изоморфный $G$; + \item Пегги передаёт граф $H$ Виктору; + \item + Виктор выбирает случайный бит $b \in \set{0, 1}$. + \begin{enumerate} + \item + Если $b = 0$, то Виктор просит Пегги доказать изоморфизм $G$ и $H$, то + есть предоставить взаимно однозначное соответствие вершин этих двух + графов. Виктор может проверить, действительно ли $G$ и $H$ изоморфны. + \item + Если $b = 1$, то Виктор просит Пегги указать гамильтонов цикл в $H$. + \end{enumerate} + \end{enumerate} + + Для задачи изоморфизма графов на данный момент не доказана ни её + принадлежность классу $P$, ни её NP-полнота, поэтому считаем, что невозможно + из гамильтонова цикла в $H$ вычислить гамильтонов цикл в изоморфном $G$. + + В каждом раунде Виктор выбирает новый случайный бит, который неизвестен + Пегги, а Пегги предоставляет новый $H$. Чтобы Пегги могла ответить на оба + вопроса, нужно, чтобы $H$ был в самом деле изоморфен $G$, и Пегги должна знать + гамильтонов цикл в $H$ (а значит также и в $G$). + + После достаточного числа раундов, Виктор может быть уверен в том, что у Пегги + действительно есть знание о гамильтоновом цикле в $G$. Пегги не раскрывает + никакой информации о гамильтоновом цикле в $G$. Виктору сложно будет доказать + кому-либо ещё, что он сам или Пегги знают гамильтонов цикл в $G$. + + Предположим, что Пегги неизвестен гамильтонов цикл в $G$, но она хочет + обмануть Виктора. Тогда Пегги необходим неизоморфный $G$ граф $G'$, в котором + она всё-таки знает гамильтонов цикл. В каждом раунде она может передавать + Виктору либо $H'$ --- изоморфный $G'$, либо $H$ --- изоморфный $G$. + + Если Виктор попросит доказать изоморфизм графов, и ему был передан $H$, то + обман не вскроется. Если Виктор просит показать гамильтонов цикл, и ему был + передан $H'$, то обман не вскроется. Вероятность того, что Пегги всё-таки + обманет Виктора после $k$ раундов, равна $1/2^k$. + + Боб может предположить, что Виктор и Пегги в сговоре, и в каждом раунде Виктор + заранее сообщал Пегги свой выбор случайного бита, чтобы Пегги могла передавать + ему H для проверок изоморфизма и H′ для проверок гамильтонова цикла. + + Таким образом, без участия Пегги доказать, что она знает гамильтонов цикл, + можно лишь доказав, что во всех раундах протокола выбирались действительно + случайные биты. + + Задача, связанная с определением <<имеется ли в заданном графе гамильтонов + цикл>>, является NP-полной. +\end{theorem} + +\begin{theorem}[Достаточное условие гамильтоновости, Оре] + Если в связном графе с числом вершин $n \geq 3$ для любых двух несмежных + вершин $u$ и $v$ выполняется неравенство: $d(u) + d(v) \geq n$, то граф + является гамильтоновым. +\end{theorem} +\begin{proof} + Пусть дан граф $G = (V, \alpha)$, удовлетворяющий условиям теоремы. Покажем, + что в нём есть гамильтонов цикл. + + Найдём в графе $G$ цепь наибольшей длины. Обозначим эту наибольшую длину $k$. + Цепь $P$: $u_0 u_1 \dots u_k$. + + Предположим, что $u_0$ и $u_k$ не смежны. В противном случае получаем, что + $u_0 u_1 \dots u_k u_0$ --- гамильтонов цикл. + + Итак, $u_0$ и $u_k$ не смежны. Изучим свойства цепи $P$. + \begin{enumerate} + \item + Любая вершина графа $G$, смежная с $u_0$ или с $u_k$, входит в состав + цепи: иначе мы смогли бы построить цепь длины $(k + 1)$, добавив + соответствующую вершину в начало или конец цепи. + \item + Обозначим $d(u_0) = s$. По первому пункту все $s$ вершин входят в состав + цепи $P$. В порядке прохождения цепи $P$ занумеруем вершины, смежные с + $u_0$: $u_{i1} u_{i2} \dots u_{is} u_{i1} = u_1$. + + \begin{center} + \includegraphics[width=0.6\textwidth]{lec8-ore1} + \end{center} + + Обозначим через $A$ множество вершин цепи $P$, которые имеют вид + $u_{i_{t - 1}}$, то есть это вершины цепи $P$, предшествующие вершинам, + смежным с $u_0$. $|A| = s$. Сама $u_0$ тоже попадает в $A$. + + Если из $P$ выбросить вершины $A$, то есть $|P \backslash A| = (k + 1) - + s$. Заметим, что в состав $P \backslash A$ входит вершина $u_k$. + \item + По условию $d(u_0) + d(u_k) \geq n$. Следовательно, $d(u_k) \geq n - s + \geq (k + 1) - s$. $d(u_0) = s$, $(k + 1)$ --- количество вершин в самой + большой цепи. Таким образом, количество вершин, смежных с $u_k$, не + меньше, чем $(k + 1) - s$. При этом согласно пункту 1 все эти вершины + присутствуют в цепи $P$ и очевидно, что среди них нет самой $u_k$. + \item + Из $u_k$ выходит не меньше, чем $(k + 1) - s$ рёбер. Следовательно, по + крайней мере одно ребро другим концом имеет вершину, входящую в состав + $A$. + \item + Обозначим через $u_{i_{t - 1}}$ вершину из $A$, смежную с $u_k$. + Рассмотрим подграф графа $G$, порождённый вершинами, входящими в состав + цепи $P$. Обозначим его $G^*$. Докажем, что $G^*$ --- гамильтонов. + + \begin{center} + \includegraphics[width=0.6\textwidth]{lec8-ore1} + \end{center} + + Действительно, гамильтоновым циклом в нём будет $u_0 \to u_{i_t} + \overset{P}{\to} u_k \to u_{i_{t - 1}} \overset{P}{\to} u_0$. + + Если $G^* = G$, то $G$ --- гамильтонов. Иначе существует некоторая вершина + $u \not\in G^*$. В силу связности $G$, не нарушая общности, можно считать, + что $u$ смежна с $u^*$ в $P$. + + Построим гамильтонов цикл в графе $G^*$. Обозначим его через $C$. В графе + $G$ теперь можно построить цепь длины $(k + 1)$: $u u^* C$. Эта цепь + содержит все вершины цепи $P$ и вершину $u$, которая входила в состав $P$. + + Таким образом, $(k + 1) + 1 = k + 2$. Это противоречит предположению о + максимальности цепи $P$. + \end{enumerate} +\end{proof} + +\begin{corollary}[Теорема Дирака] + Если в связном графе степень любой вершины $d(u) \geq \frac{n}{2}$, то граф + гамильтонов. +\end{corollary} + +\begin{corollary}[Оре] + Если в связном графе с числом вершин $n \geq 3$ для любых двух несмежных + вершин $u$ и $v$ выполняется неравенство: $d(u) + d(v) \geq n - 1$, то в + графе есть гамильтонова цепь. +\end{corollary} + +\begin{theorem}[Достаточное условие Поша] + Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью + $d_1 \leq \dots \leq d_n$ удовлетворяет следующим двум условиям, то он + гамильтонов: + \begin{enumerate} + \item + Для всякого $k$, $1 \leq k < (n - 1) / 2$, число вершин со степенями, + меньшими или равными $k$, меньше, чем $k$; + \item + Для нечётного $n$ число вершин со степенями, меньшими или равными + $(n - 1) / 2$ не превосходит $(n - 1) / 2$. + \end{enumerate} +\end{theorem} + +\begin{theorem}[Достаточное условие Хватала] + Если граф $G$ с числом вершин $n \geq 3$ и степенной последовательностью + $d_1 \leq \dots \leq d_n$ удовлетворяет следующему условию, то он гамильтонов: + для любого $k$ верна импликация + \begin{equation*} + (d_k \leq k \leq n/2) \implies (d_{n - k} \geq n - k)$ + \end{equation*} +\end{theorem} \section{Замыкание. Критерий и достаточное условие Бонди-Хватала.} -\dots +\begin{definition} + Замыкание $[G]$ $n$-вершинного графа $G$ получается из графа $G$ добавлением + рёбер $\set{u, v}$ для всех пар вершин $u$ и $v$, для которых выполняется + условие $d(u) + d(v) \geq n$. +\end{definition} + +\begin{theorem}[Критерий гамильтоновости, Бонди-Хватал] + Граф $G$ является гамильтоновым $\iff$ его замыкание $[G]$ является + гамильтоновым. +\end{theorem} +\begin{theorem}[Достаточное условие гамильтоновости, Бонди-Хватал] + Если замыкание $[G]$ графа $G$ является полным графом, то граф $G$ --- + гамильтонов. +\end{theorem} \chapter{Пути в орграфах} +\section{Маршрут в орграфе, путь, контур. Бесконтурный орграф. Связный орграф.} + +\begin{definition} + Маршрутом в орграфе называется последовательность дуг $(v_1, v_2), (v_2, v_3), + \dots, (v_{n - 1}, v_n)$, где $(v_{i - 1}, v_i) \in \alpha)$. + + Маршрут --- последовательность дуг, в которой конец каждой дуги является + началом следующей. Говорят, что маршрут проходит через вершины $v_0 v_1 + \dots v_n$. Этим же способом можно и записывать маршрут. $v_0$ --- начальная + вершина, $v_n$ --- конечная. +\end{definition} + +\begin{definition} + Маршрут, в котором каждая дуга встречается только один раз, называется путём. +\end{definition} + +\begin{definition} + Путь, в котором начальная и конечная вершины совпадают, называется + циклическим. +\end{definition} + +\begin{definition} + Путь, каждая вершина которого принадлежит не более, чем двум его дугам --- + простой. +\end{definition} + +\begin{definition} + Простой циклический путь в орграфе называется контуром. +\end{definition} + +\begin{definition} + Простой путь, не являющийся контуром, называется ориентированной цепью + (орцепью, просто цепью). +\end{definition} + +\begin{definition} + Длиной маршрута называется число его дуг. В орграфе, в отличие от + неориентированного графа длина цикла и контура может быть меньше трёх. +\end{definition} + +\begin{definition} + Контур длины 1 (петля) называется тривиальным контуром. +\end{definition} + +\begin{definition} + Орграф, не содержащий нетривиальных контуров, называется бесконтурным. +\end{definition} + +Каждому орграфу можно поставить в соответствие единственный неориентированный +граф, называемый симметризацией, если каждую дугу, ведущую из одной вершины в +другую, заменить неориентированным ребром, соединяющим ту же пару вершин. + +\begin{definition} + $\vec{G}$ называется связным, если его симметризация является связным графом. +\end{definition} + +Если в орграфе $\vec{G}$ $n$ вершин и $m$ дуг, то максимальная длина пути в +орграфе $\vec{G}$ не больше $m$, а контура --- не больше $n$. + +\section{Критерий эйлеровости орграфа. Критерий существования эйлерова пути.} + +\begin{definition} + Путь длины $m$ в орграфе называется эйлеровым путём. +\end{definition} + +\begin{definition} + Связный орграф называется эйлеровым, если в нём существует циклический эйлеров + путь. +\end{definition} + +\begin{definition} + Контур длины $n$ в орграфе называется гамильтоновым. +\end{definition} + +\begin{definition} + Ориентированная цепь длины $(n - 1)$ в орграфе называется гамильтоновой + цепью. +\end{definition} + +\begin{definition} + Связный орграф называется гамильтоновым, если в нём существует гамильтонов + контур. +\end{definition} + +\begin{theorem}[Критерий эйлеровости орграфа] + Связный орграф $\vec{G}$ эйлеров $\iff$ $\forall v \in V$ выполняется $d^+(v) = + d^-(v)$. +\end{theorem} +\begin{proof} + \textbf{TODO}: доказательство самостоятельно +\end{proof} + +\begin{theorem}[Критерий существования эйлерова пути] + В связном орграфе $\vec{G}$ существует эйлеров путь, соединяющий две различные + вершины $u$ и $v$ тогда и только тогда, когда + \begin{equation*} + \begin{cases} + d^+(u) = d^-(u) + 1 \\ + d^-(v) = d^+(v) + 1 \\ + d^+(w) = d^-(w), w \neq u, w \neq v + \end{cases} + \end{equation*} +\end{theorem} +\begin{proof} + \textbf{TODO}: доказательство самостоятельно +\end{proof} + +Эффективных алгоритмов нахождения гамильтонова контура в орграфе не известно, а +задача проверки, существует ли в орграфе гамильтонов контур, является NP-полной. + +\section{Сеть. Поиск кратчайших путей: алгоритмы Дейкстры, Беллмана-Форда, +Флойда-Уоршелла.} + +\begin{definition} + Сетью называется граф, каждому ребру (дуге) которого приписано некоторое + число, называемое весом, длиной или стоимостью ребра (дуги). Обозначается + $w(u, v)$. $\vec{G} = (V, \alpha),\, w : \alpha \to \mathbb{R}$. +\end{definition} + +\begin{definition} + Длиной пути в сети называется сумма весов дуг, входящих в состав этого пути. +\end{definition} + +\begin{definition} + Сеть называется корневой, если в ней существует выделенная вершина $v$, + называемая корнем, и которой существует путь во все остальные вершины сети. +\end{definition} + +\begin{definition} + Путь в сети называется кратчайшим, если его длина является минимальной из всех + длин путей, соединяющих эти вершины. +\end{definition} + +По постановке задачи выделяют сети с положительными весами и сети, в которых +веса могут быть отрицательными. + +Существенным является наличие в сети контура отрицательной длины. Понятие +кратчайшего путь утрачивает смысл для всех вершин, находящихся в контуре +отрицательной длины, если он достижим из заданной вершины и для тех вершин, +которые достижимы из вершин этого контура. + +Очевидно, что любая часть кратчайшего пути также является кратчайшим путём. +Рассмотрим кратчайший путь $u_1 \dots u_k$. Если $u_i \dots u_j (i < j)$ --- +часть этого пути --- не является кратчайшим путём из $u_i$ в $u_j$, то заменив +эту часть пути на кратчайший путь, мы получили бы путь меньшей длины, что +противоречило бы тому, что исходный путь был бы кратчайшим. + +Таким образом, для задачи нахождения кратчайших путей выполняется свойство +оптимальности подзадач. + +Рассмотрим несколько вариантов задачи. +\begin{enumerate} + \item + Дана вершина $u$ и надо найти кратчайшие пути из $u$ во все остальные + вершины сети. + \item + Дана вершина $v$. Требуется найти кратчайшие пути из всех остальных вершин + в вершину $v$. + \item Даны вершины $u$ и $v$. Требуется найти кратчайший путь из $u$ в $v$. + \item Найти кратчайшие пути между всеми парами вершин сети. +\end{enumerate} + +Для каждой вершины $v$ будем хранить оценку длины кратчайшего пути до вершины +$v$ из заданной. Обозначим $\lambda(v)$. Также будем хранить непосредственного +предшественника вершины $v$ в этом пути. Обозначим $\pi(v)$. + +Во многих алгоритмах решающих задачи поиска кратчайших путей, используется +процедура релаксации дуги. Релаксация дуги состоит в выборе меньшего из двух +возможных путей: пути, который уже был построен в вершину $v$, и пути в $v$ +через вершину $u$ по дуге $(u, v)$. + +Если $\lambda(u) + w(u, v) < \lambda(v)$, то пересчитываем $\lambda(v)$ и +$\pi(v)$. +\begin{align*} + \lambda(v) &= \lambda(u) + w(u, v) \\ + \pi(v) &= u +\end{align*} + +\begin{theorem}[Алгорим Дейкстры] + Рассмотрим сеть с положительными весами. Рассмотрим задачу поиска кратчайших + путей из одной вершины до всех остальных. $v_0$ --- корень сети. + \begin{enumerate} + \item + Выполняется инициализация весов и предшественников. Множество $U = \set{ + v_0}$, + \begin{align*} + &\begin{cases} + \lambda(v_0) &= 0 \\ + \pi(v_0) &= NULL \\ + \end{cases} \\ + &\begin{cases} + \lambda(v) &= +\infty \\ + \pi(v) &= NULL \\ + \end{cases} + \end{align*} + \item + Для всех вершин $V \backslash U$, в которые есть дуга из последней + добавленной в $U$ вершины, выполняем релаксацию. + \item + Выбираем вершину из $V \backslash U$ с минимальным значением $\lambda(v)$. + Добавляем её во множество $U$: $U = U \cup \set{v}$. Если множество $U$ + совпало с множеством $V$, то алгоритм завершён. Иначе повторить пункт 2. + \end{enumerate} +\end{theorem} + +\begin{theorem} + Описанный алгоритм приводит к построению кратчайших путей из $v_0$ в заданной + корневой сети. +\end{theorem} +\begin{proof} + Требуется доказать, что после окончания работы алгоритма в каждую вершину + сети $v \neq v_0$ ведёт единственный путь, составленный из дуг, выбранных на + шаге 3 алгоритма. Этот путь является кратчайшим из $v_0$ в $v$, и его длина + равна метке вершины $v$, $\lambda(v)$. + + Доказательство индукцией по расстоянию от $v_0$ до $v$. + \begin{enumerate} + \item + Пусть $v_1$ --- некоторая вершина, ближайшая к $v_0$. После инициализации + $\lambda(v_0) = 0, \lambda(v_1) = +\infty$. После релаксации дуги $(v_0, + v_1)$ получаем $\lambda(v_1) = \lambda(v_0) + w(v_0, v_1) = w(v_0, v_1)$. + + Дуга из $v_0$ в $v_1$ является кратчайшей, тогда вершина $v_1$ будет + выбрана на третьем шаге алгоритма, и её метка будет равна длине + кратчайшего пути. А предшественник $\pi(v_1) = v_0$. + \item + Пусть доказанное утверждение справедливо для всех вершин, удалённых от + вершины $v_0$ меньше вершины $v$. В момент выбора вершины $v$ её метка + будет иметь вид $\lambda(u) + w(u, v)$, где $u$ --- некоторая вершина, + которая была выбрана в ходе алгоритма раньше. + + По предположению индукции для вершины $u$ верны все доказанные утверждения. + А именно: кратчайший путь из $v_0$ до $u$ состоит из выбранных в ходе + алгоритма дуг, а его длина равна метке вершины $u$. + + Обозначим через $p$ путь от $v_0$ до $u$. + \begin{center} + \includegraphics[width=0.4\textwidth]{lec10-dijkstra1} + \end{center} + + Пусть кратчайшим путём из $v_0$ в $v$ является путь $v_0 p^* u^* v$. В + силу оптимальности подзадачи путь $v_0 p^* u^*$ является кратчайшим путём + из $v_0$ в $u^*$. По предположению индукции путь по дугам, выбранным + в алгоритме от $v_0$ до $u^*$, является кратчайшим и имеет длину + $\lambda(u^*)$. + + Так как путь $v_0 p^* u^*$ является кратчайшим, то длина этого пути равна + $\lambda(u^*)$. Тогда длина кратчайшего пути $v_0 p^* u^* v$ будет равна + $\lambda(u^*) + w(u^*, v)$. Так как этот путь кратчайший, то его длина + не может быть больше длины $v_0 p u v$. $\lambda(u^*) + w(u^*, v) \leq + \lambda(u) + w(u, v)$. + + В ходе алгоритма при выборе вершины $v$ была использована дуга $(u, v)$, + где $u = \pi(v)$. Это означает, что эта дуга даёт минимум значения + выражения $\lambda(u) + w(u, v)$ по всем вершинам $u$, выбранным ранее + вершины $v$. + + В частности, так как дуга $(u^*, v)$ не была использована, то это + означает, что + \begin{equation*} + \lambda(u^*) + w(u^*, v) \geq \lambda(u) + w(u, v) + \end{equation*} + + С учётом неравенства, полученного ранее, получаем + \begin{equation*} + \lambda(u^*) + w(u^*, v) = \lambda(u) + w(u, v) + \end{equation*} + + Следовательно, построенный в ходе алгоритма путь является кратчайшим, и + его длина равна метке вершины $v$. + \end{enumerate} +\end{proof} + +\begin{theorem}[Алгоритм Беллмана-Форда] + Пусть в сети допускаются отрицательные веса, но не контуров отрицательной + длины, достижимых из выбранной вершины. Очевидно, что кратчайший путь в этом + случае будет являться цепью. Если в сети $n$ вершин, то длина цепи $\leq n - + 1$. + + Выполним первоначальную инициализацию меток вершина также, как в алгоритме + Дейкстры. + \begin{align*} + &\begin{cases} + \lambda(v_0) &= 0 \\ + \pi(v_0) &= NULL \\ + \end{cases} \\ + &\begin{cases} + \lambda(v) &= +\infty \\ + \pi(v) &= NULL \\ + \end{cases} + \end{align*} + + Выполним релаксацию по всем дугам сети. В результате получим оценки для всех + кратчайших путей длины 1. Будут пересчитаны метки вершин, достижимых из + выбранной вершины $v_0$ по пути длины 1. + + Проведём ещё раз релаксацию по всем дугам сети. Получим оценки кратчайших + путей длины не менее 2, и так далее. + + Выполнив $(n - 1)$ релаксацию по всем дугам сети, получим оценки кратчайших + путей длины до $(n - 1)$, то есть просто кратчайших путей из $v_0$ до + остальных. + + Если в сети отсутствуют контуры отрицательной длины, достижимые из $v_0$, то + полученные метки позволяют построить дерево кратчайших путей из вершины $v_0$. + + Если выполнить релаксацию ещё один раз, и при этом хотя бы одна метка будет + изменена, то это означает, что в сети есть контур отрицательной длины. Тогда + решение некорректно. + + Убедимся, что последняя релаксация действительно позволяет определить + наличие контура отрицательной длины. Предположим, что такой контур есть: + $v_1, v_2, \dots, v_k, v_1$. + \begin{center} + \includegraphics[width=0.5\textwidth]{lec11-bellman1} + \end{center} + + Так как контур достижим из вершины $v_0$, то после выполнения $(n - 1)$ + итерации релаксации по всем дугам сети, все вершины контура получат некоторую + метку, являющуюся оценкой кратчайшего пути. И это значение будет отлично от + $\infty$. + + Предположим, что после выполнения $n$-ой последней итерации релаксации по + всем дугам сети значения меток не изменились. В том числе в релаксациях + участвовали и дуги, входящие в состав контура. + + Раз значения меток не изменились, то это означает, что имеют место следующие + неравенства: + \begin{align*} + (v_1, v_2) &: \lambda(v_2) \leq \lambda(v_1) + w(v_1, v_2) \\ + &\dots \\ + (v_k, v_1) &: \lambda(v_1) \leq \lambda(v_k) + w(v_k, v_1) \\ + \end{align*} + + Просуммируем все неравенства + \begin{equation*} + 0 \leq w(v_1, v_2) + \dots + w(v_k, v_1) + \end{equation*} + + А по условию этот контур отрицательной длины. Таким образом, алгоритм + Беллмана-Форда действительно позволяет найти кратчайшие пути в сети с + отрицательным весом и определить наличие контура отрицательной длины, + достижимого из выбранной вершины. + + Эффективность алгоритма Беллмана-Форда --- $O(nm)$, где $m$ --- количество + дуг. +\end{theorem} + +\begin{theorem}[Алгоритм Флойда-Уоршелла] + Алгоритм позволяет строить кратчайшие пути между всеми парами вершин сети за + время $O(n^3)$. Алгоритм является динамическим. + + Обозначим через $d_{ij}^{(k)}$ кратчайший путь из вершины $i$ в вершину $j$, + среди внутренних вершин которого нет вершины с номером $> k$. + + Очевидно, что + \begin{equation*} + d_{ij}^{(0)} = \begin{cases} + w(v_i, v_j), &(v_i, v_j) \in \alpha \\ + \infty, &(v_i, v_j) \not\in \alpha + \end{cases} + \end{equation*} + + $d_{ij}^{(n)}$ будет совпадать с длиной кратчайшего пути из $i$ в $j$. + $d_{ij}^{(n)} = d_{ij}$. + + Пусть известны значения $d_{ij}^{(k)}$. Надо определить $d_{ij}^{(k + 1)}$. + Заметим, что кратчайший путь из $i$ в $j$ через вершины с номерами $\leq k + 1$ + может содержать $(k + 1)$-ю вершину или не содержать её. + + Если в пути нет вершины с номером $(k + 1)$, то $d_{ij}^{(k + 1)} = + d_{ij}^{(k)}$. Если вершина $(k + 1)$ есть в пути, то часть этого пути от + вершины $i$ до $(k + 1)$ и от $(k + 1)$ до $j$ также является кратчайшим + путём, но не содержит вершину $(k + 1)$ в качестве внутренней вершины. + \begin{equation*} + d_{ij}^{(k + 1)} = d_{i(k + 1)}^{(k)} + d_{(k + 1)j}^{(k)} + \end{equation*} + + \begin{center} + \includegraphics[width=0.5\textwidth]{lec11-floyd1} + \end{center} + + Таким образом, выбрав минимальное из указанных значений, можно рассчитать все + значения $d_{ij}^{(k + 1)}$ по предыдущим значениям. Выполнив итерации по + $k = 1, \dots, n$, будет получена матрица кратчайших путей между всеми + парами вершин. + + Для построения самих путей необходимо использовать дополнительную матрицу + предшественников, которая будет пересчитываться следующим образом: + + Если + \begin{equation*} + d_{ij}^{(k)} > d_{i(k + 1)}^{(k)} + d_{(k + 1)j}^{(k)} + \end{equation*} + то + \begin{equation*} + \pi_{ij}^{(k + 1)} = \pi_{(k + 1)j}^{(k)} + \end{equation*} + иначе + \begin{equation*} + \pi_{ij}^{(k + 1)} = \pi_{ij}^{(k)} + \end{equation*} +\end{theorem} + +\section{Достижимость. Теорема о существовании маршрута длины k. Матрица +достижимости.} + +\begin{definition} + Говорят, что в орграфе $\vec{G}$ вершина $v$ достижима из вершины $u$, если + существует путь из $u$ в $v$. + + По определению считаем, что каждая вершина достижима из самой себя вне + зависимости от существования в ней петли. +\end{definition} + +Пусть $A$ --- матрица смежности орграфа $\vec{G}$. + +\begin{theorem} + Элемент $a_{ij}^{(k)}$ матрицы $A^k$ отличен от 0 $\iff$ в орграфе существует + маршрут длины $k$ из вершины $v_i$ в $v_j$. + \label{thm:route-k-length} +\end{theorem} +\begin{proof} + ММИ по $k$. + \begin{enumerate} + \item + $k = 1$. $A^1 = A$. $a_{ij} = 1 \iff$ существует дуга $(v_i, v_j)$. Эту + дугу можно рассматривать как маршрут длины 1. + \item + Предположим, что утверждение справедливо для $k = l$. Докажем истинность + для $k = l + 1$. + \begin{align*} + a_{ij}^{(l + 1)} = 1 \iff 1 = \sum_{s = 1}^n a_{is}^{(l)} a_{sj} \iff + (\exists s_0) (a_{is_0}^{(l)} a_{s_0 j} = 1) \iff (\exists s_0) + (a_{is_0}^{(l)} = 1 \land a_{s_0 j} = 1). + \end{align*} + + Это означает с учётом предположения индукции, что существует маршрут длины + $l$ из $v_i$ в $v_{s_0}$. И есть дуга $(v_{s_0}, v_j)$. Следовательно, + существует маршрут длины $(l + 1)$. + \end{enumerate} +\end{proof} + +Обозначим через $E$ тождественную булеву матрицу (на главной диагонали стоят 1, +в остальных местах --- 0). + +\begin{corollary} + Вершина $v_j$ достижима из $v_i$ в $n$-вершинном графе $\vec{G}$ $\iff$ в + матрице $D = E + \sum_{i = 1}^{n - 1} A^i$ элемент $d_{ij} = 1$. +\end{corollary} +\begin{proof} + \textbf{Необходимость.} + + Пусть $v_j$ достижима из $v_i$. Тогда существует путь из $v_i$ в $v_j$, а + следовательно, существует и простой путь (если $v_i \neq v_j$, то это будет + цепь). Так как длина цепи не превышает $(n - 1)$, то существует путь из + $v_i$ в $v_j$, длина которого не превышает $(n - 1)$. + + Таким образом, по теореме \ref{thm:route-k-length} это означает, что для + некоторого значения $k$ выполняется $a_{ij}^{(k)},\, k \leq n - 1$. Таким + образом, если $v_i \neq v_j$, то элемент матрицы $d_{ij} = 1$, потому что + существует путь. А если $v_i = v_j$, то $d_{ij} = 1$ за счёт $E$. + + \textbf{Достаточность.} + + Пусть $d_{ij} = 1 = \ds\sum_{k = 1}^{n - 1} a_{ij}^{(k)} + e_{ij}$. + + $i \neq j : \exists k: a_{ij}^{(k)} = 1$. Следовательно, существует маршрут + длины $k$ из $v_i$ в $v_j$, то есть $v_j$ достижима из $v_i$. +\end{proof} + +\begin{definition} + Матрицу $D$ называют матрицей достижимости орграфа $\vec{G}$, а + соответствующее ей отношение $\delta \subseteq V \times V$ называется + отношением достижимости. Таким образом, если $(v_i, v_j) \in \delta \iff$ + $v_j$ достижима из $v_i$. +\end{definition} + +\section{Отношение взаимной достижимости. Сильные компоненты. Ориентация графа, +приводящая к сильно связному орграфу.} + +\begin{definition} + Симметричная часть отношения достижимости, то есть отношение $\varepsilon + = \delta \cap \delta^{-1}$, называется отношением взаимной достижимости в + орграфе. По определению $(v_i, v_j) \in \varepsilon \implies (v_i, v_j) \in + \delta \land (v_i, v_j) \in \delta^{-1} \iff (v_i, v_j) \in \delta \land (v_j, + v_i) \in \delta$. + + Очевидно, что отношение $\varepsilon$ является отношением эквивалентности: + рефлексивность следует из определения достижимости, симметричность и + транзитивность очевидны. +\end{definition} + +\begin{definition} + Классы эквивалентности отношения $\varepsilon$ называются сильными + компонентами или слоями орграфа. +\end{definition} + +\begin{definition} + Неодноэлементные сильные компоненты также называются максимальными сильно + связными подграфами данного графа. +\end{definition} + +\begin{definition} + Если отношение $\varepsilon$ универсально ($\varepsilon = V \times V$), то + есть любые две вершины орграфа взаимно достижимы, то такой орграф называется + сильно связным или просто сильным. +\end{definition} + +\begin{theorem}[Ориентация графа, приводящая к сильно связному графу] + Связный граф допускает ориентацию рёбер, превращающую его в сильно + связный орграф $\iff$ каждое его ребро входит в состав некоторого цикла. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть граф $G = (V, \alpha)$ допускает ориентацию рёбер, превращающую его в + сильно связный орграф $\vec{G} = (V, \alpha)$. + + Пусть ребро $\set{u, v}$ не входит ни в какой цикл графа $G$. Тогда это ребро + является единственным путём связывающим $u$ и $v$ (оно будет являться мостом). + + Какую бы ориентацию мы ни придали ребру $\set{u, v}$ в орграфе $\vec{G}$ + вершины $u$ и $v$ не будут взаимно достижимы. + + \textbf{Достаточность.} + + Пусть в $G$ каждое ребро принадлежит некоторому циклу. Выберем произвольный + цикл: $v_1, v_2, \dots, v_k, v_1$. + + Ориентируем входящие в его состав рёбра в порядке прохождения цикла: + \begin{align*} + \set{v_1, v_2} &\to (v_1, v_2) \\ + &\dots \\ + \set{v_k, v_1} &\to (v_k, v_1) + \end{align*} + + Если выбранный цикл содержал все вершины графа (то есть был гамильтоновым), + то произвольно ориентировав оставшиеся рёбра графа, получим сильно связный + орграф. Взаимная достижимость будет осуществляться за счёт построенного + гамильтонового контура. + + Пусть исходный цикл содержал не все вершины графа $G$. Обозначим построенный + цикл через $C$. В силу связности графа $G$ любая его вершина соединена + некоторым путём с любой другое вершиной. + + Пусть $v$ --- вершина графа $G$, не входящая в состав цикла $C$. Не нарушая + общности можно считать, что она смежна с некоторой вершиной $v_i$ из цикла + $C$. По условию ребро $\set{v, v_i}$ входит в состав некоторого цикла $C^*$. + + Двигаемся от вершины $v_i$ к вершине $v$ и далее по циклу $C^*$, ориентирую + рёбра в порядке движения, пропуская рёбра, которые были ориентированы ранее. + + В результате получим некоторый новый контур, который содержит все вершины + цикла $C$ и вершину $v$. Продолжая процесс в силу конечности графа получим + циклический путь, проходящий через все вершины графа $G$. + + Произвольным образом ориентирую остальные рёбра получаем сильно связный + орграф. +\end{proof} + \section{Источники и стоки. Фактор-граф. Конденсация и ее свойства. Бесконтурность конденсации.} % Лекция 12 @@ -1074,7 +2764,7 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \label{def:condensation} \end{definition} -% TODO: свойства конденсации +\textbf{TODO}: свойства конденсации \begin{theorem}[Бесконтурность конденсации] Конденсация всякого орграфа является бесконтурным графом. @@ -1102,6 +2792,909 @@ $K_{m, n}$ --- всегда рёберно-симметрический, есл \emph{Это противоречие}. \end{proof} +\section{Источники и стоки в бесконтурных графах. База орграфа и теорема о базе. +Следствие теоремы.} + +\begin{theorem}[Об истоках и стоках в бесконтурных графах] + Пусть $\vec{G} = (V, \alpha)$ --- бесконтурный граф, $v$ --- произвольная + вершина. Тогда из $v$ достижим некоторый сток, а $v$ достижима из некоторого + источника. + \label{thm:in-out-contour-free} +\end{theorem} +\begin{proof} + От противного. + + Рассмотрим первый случай. Пусть $v$ не является ни источником, ни стоком. + Существует по крайней мере одна дуга, исходящая из вершины $v$, и одна + входящая в отличную от $v$ вершину. Получаем трёхэлементную подцепь, + включаемую в некоторую максимальную цепь в орграфе $\vec{G}$. Пусть это + будет цепь $u_1 \to u_2 \to \dots \to v \to \dots \to u_{k - 1} \to u_k$. + + Утверждается, что $u_1$ является источником в $\vec{G}$, а $u_k$ --- стоком. + + Предположим, что $u_1$ не является источником. Тогда в $u_1$ приходит дуга + из некоторой вершины $w \neq u_1$. Если $w$ не входит в состав построенной + цепи, то длина на 1 больше, чем построенная ранее максимальная цепь, а это + противоречит максимальности. + + Если $w$ совпадает с некой вершиной построенной цепи, то получим в $\vec{G}$ + нетривиальный контур $(w u_1 u_2 \dots u_i)$. А это противоречит условию + $\implies u_1$ --- источник, и из него достижима $v$. + + Аналогично, если $u_k$ --- не сток, то из неё должна быть дуга в некоторую + вершину $u$. Если вершина $u$ не входит в состав цепи, то получим новую цепь + длины большей, чем максимальная. + + А если $u$ входит в состав цепи, то получим нетривиальный контур. + + В обоих случаях получаем противоречие. Следовательно, $u_k$ --- сток, и он + достигает я из вершины $v$. + + Аналогично рассмотрим случаи, когда вершина $v$ является источником или стоком + (заметим, что по определению любая вершина достижима из самой себя). +\end{proof} + +\begin{definition} + Базой орграфа $\vec{G} = (V, \alpha)$ называется подмножество $V^* \subseteq + V$, если выполняются два условия: + \begin{enumerate} + \item + $\delta(V^*) = V$. Срез $\delta$ по $V^* = V$. Любая вершина орграфа + достижима из некоторой вершины базы. + \item + $\delta \cap V^* \times V^* = \Delta_{V^*}$. Никакая вершина базы не + достижима из другой вершины базы. + \end{enumerate} +\end{definition} + +\begin{theorem}[О базе орграфа] + Каждая база орграфа состоит из взятых по одному представителей из источников + конденсации орграфа. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть $V^*$ --- база орграфа $\vec{G} = (V, \alpha)$. Его конденсация: + $\vec{G}/\varepsilon$. + + Если из источника $\varepsilon(u)$ конденсации $V^*$ не выбрано ни одного + представителя, то вершины $\vec{G}$, входящие в состав $\varepsilon(u)$ не + будут достижимы ни из какой вершины базы, что противоречит определению. Таким + образом, в состав базы входят представители из каждого источника конденсации. + + Пусть в $V^*$ попали два представителя одного источника конденсации $u_1 \neq + u_2$. Так как $\varepsilon(u)$ является сильно связным графом, то $u_1$ и + $u_2$ взаимно достижимы и, следовательно, одновременно не могут входить в + базу. Таким образом, все представители источников конденсации входят в базу по + одному из каждого источника. + + Пусть в базу входит некоторая вершина $v$, не содержащаяся ни в каком + источнике конденсации. Тогда $\varepsilon(v)$ не будет являться источником в + конденсации. По теореме \ref{thm:in-out-in-contour-free} достижима из + некоторого источника $\varepsilon(u)$ конденсации. По установленному ранее в + базе есть представитель из этого источника. Следовательно, $v$ достижима из + него. + + Таким образом, вершины, не входящие в состав источников конденсации, не могут + входить в базу. + + \textbf{Достаточность.} + + Пусть $V^* \subseteq V$ состоит из взятых по одному представителей из + источников конденсации. Покажем, что $V^*$ --- база. Надо показать, что + выполнены два условия: + \begin{enumerate} + \item + По теореме \ref{thm:in-out-contour-free}, любая вершина $\varepsilon(v)$ + конденсации достижима из подходящего источника $\varepsilon(u)$ + конденсации графа. + + Тогда в $\vec{G}$ вершина $v$ будет достижима из вошедшего в $V^*$ + источника $\varepsilon(u)$. Таким образом, любая вершина орграфа достижима + из подходящей вершины $V^*$. + \item + Так как вершины из $V^*$ входят в разные источники конденсации, то ни одна + из них не может быть достигнута из другой в орграфе $\vec{G}$. Таким + образом, $V^*$ --- база в орграфе $\vec{G}$. + \end{enumerate} +\end{proof} + +\begin{corollary} + Любые две базы орграфа имеют одинаковое количество элементов. +\end{corollary} +\begin{proof} + Количество элементов в базе равно числу источников конденсации. +\end{proof} + +\section{Теорема о взаимной достижимости вершин и матрице достижимости.} + +\begin{theorem} + Две вершины орграфа $v_i$ и $v_j$ взаимно достижимы в $\vec{G}$ $\iff$ в + матрице достижимости $D$ этого орграфа строки, соответствующие $v_i$ и $v_j$ + равны между собой. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть $v_i$ и $v_j$ взаимно достижимы в $\vec{G}$. Тогда любая вершина $v_k$ + будет достижима из $v_i$ $\iff$ она будет достижима из $v_j$, и наоборот. + Таким образом, если $d_{ik} = 1 \iff d_{jk} = 1$. + + \textbf{Достаточность.} + + Пусть в матрице достижимости $D$ совпадают строки, соответствующие вершинам + $v_i$ и $v_j$. По определению вершина достижима из самой себя. Тогда $d_{ii} = + 1 \land d_{jj} = 1$. Так как строки равны, то $\implies \begin{cases} + d_{ji} = 1 \\ + d_{ij} = 1 + \end{cases}$. + + Таким образом, $v_i$ и $v_j$ взаимно достижимы. +\end{proof} + +Из доказанной теоремы следует простая процедура выделения максимальных сильно +связных подграфов. Процедура состоит в последовательном просмотре строк матрицы +достижимости $D$ и выписывании тех вершин, у которых строки равны. + +Завершив эту процедуру, мы вычёркиваем одноэлементные классы, то есть +тривиальные компоненты связности. Оставшиеся классы являются максимальными +сильно связными подграфами. + +Заметим, что можно сразу определить редукцию матрицы смежности орграфа. +Очевидно, что ни источники, ни стоки не входят ни в какой максимальный сильно +связный подграф. Поэтому соответствующие им строки и столбцы матрицы смежности +можно исключить. + +В получившемся графе снова могут быть источники и стоки. Их также можно будет +исключить. Редукция повторяется, пока остаются источники и стоки. + +\section{Проверяющий тест. Теорема о минимальных проверяющих тестах.} + +Пусть орграф $\vec{G} = (V, \alpha)$ является функциональной моделью системы +$\Sigma$, допускающей один отказ. Предположим, что у нас есть возможность +проверить работоспособность любой вершины системы, то есть вершины орграфа +$\vec{G}$. + +Проверка может иметь два исходи: +\begin{itemize} + \item 0, если реакция элемента допустим (элемент исправен); + \item 1, если недопустима. +\end{itemize} + +Пусть $\Sigma$ такова, что реакция 1 наследуется всеми элементами, достижимыми +из неисправной в смысле орграфа $\vec{G}$. + +\begin{definition} + Проверяющим тестом называется некоторая совокупность проверок элементов + системы, позволяющих выяснить существует ли в системе отказ без его + локализации. +\end{definition} + +Очевидно, что для любой системы существует проверяющий тест. Например, +проверка всех элементов. + +\begin{definition} + Проверяющий тест называется минимальным, если он содержит минимально возможное + число проверок. +\end{definition} + +\begin{theorem}[О минимальных проверяющих тестах] + Проверяющий тест для системы $\Sigma$ будет минимальным $\iff$ он состоит из + проверок элементов, которые соответствуют вершинам орграфа $\vec{G}(\Sigma)$, + взятыми по одной из каждого стока конденсации $\vec{G}(\Sigma)/\varepsilon$. +\end{theorem} +\begin{proof} + Пусть система $\Sigma$ обладает упомянутыми свойствами. В частности, если + вершина $v$ неисправна, то сигнал неисправности будет поступать из всех + вершин, достижимых из $v$. В бесконтурном графе из любой вершины достижим + некоторый сток (теорема \ref{thm:in-out-countour-free}). + + Тогда при отказе любой вершины сигнал неисправности будет поступать из всех + стоков конденсации, достижимых из $\varepsilon(v)$. + + С другой стороны, никакой сток конденсации не достижим ни из какого другого. + Таким образом, минимальный проверяющий тест состоит из взятых по одному + представителю стоков конденсации. +\end{proof} + +\begin{remark} + Если рассмотреть граф $\vec{G}^{-1}$, то минимальным проверяющим тестом будет + любая база орграфа $\vec{G}^{-1}$. +\end{remark} + +\section{Бесконтурные графы. Отношение достижимости в бесконтурном графе.} + +\begin{theorem}[Отношение достижимости в бесконтурном графе] + Орграф $\vec{G} = (V, \alpha)$ будет бесконтурным графом $\iff$ его отношение + достижимости $\delta$ является отношением порядка на множестве его вершин $V$. +\end{theorem} +\begin{proof} + Порядком называется рефлексивное, транзитивное и антисимметричное отношение. + Очевидно, что отношение достижимости в любом орграфе является транзитивным. + + Оно будет являться отношением порядка, если для него будет выполняться свойство + антисимметричности ($\delta \cap \delta^{-1} = \Delta_V$). + + По определению, симметричная часть отношения достижимости, то есть $\delta + \cap \delta^{-1} = \varepsilon$, является отношением взаимной достижимости, + таким образом, утверждение теоремы означает, что критерием бесконтурности + графа является тривиальность его отношения достижимости. + + \textbf{Необходимость.} + + Пусть $\vec{G}$ --- бесконтурный граф, а его отношение взаимной достижимости + отлично от тождественного $\varepsilon \neq \Delta_V \implies$ существуют + две вершины, достижимые друг из друга, то есть существует путь $P_1$ из + $u$ в $v$, $P_2$ --- из $v$ в $u$. Какими бы ни были $P_1$ и $P_2$, всегда + можно выделить контур, состоящий из дуг, входящих в эти пути. Таким образом, + получим, что граф $\vec{G}$ содержит контур, что противоречит тому, что он + бесконтурный. + + \textbf{Достаточность.} + + Пусть отношение взаимной достижимости $\varepsilon$ тожественно $(\varepsilon + = \Delta_V)$. Предположим, что $\vec{G}$ не является бесконтурным и пусть + $C$ --- некоторый его нетривиальный контур. Выберем на контуре $C$ две + различных вершины из $u$ b $v$. + + Очевидно, что $v$ достижима из $u$, а $u$ достижима из $v$, по частям контура + $C$. Получили противоречие с тривиальностью $\varepsilon$. +\end{proof} + +\section{Правильная нумерация. Теорема о правильных нумерациях. Следствия +(неориентированные граф, диграф, база бесконтурного графа).} + +\begin{definition} + Пусть $\vec{G}$ --- бесконтурный граф $\implies$ $(V, \alpha)$ будет являться + конечным упорядоченным множеством. Очевидно, что источниками $\vec{G}$ будут + в точности минимальные элементы упорядоченного множества $(V, \alpha)$, а + стоками --- максимальные элементы. + + Нумерация вершин $\vec{G}$ называется правильной, если из существования дуги + $(v_i, v_j) \implies i \leq j$, то есть номер начальной вершины дуги не + превосходит номера конца дуги. +\end{definition} + +\begin{theorem}[О правильных нумерациях] + $\vec{G}$ допускает правильную нумерацию $\iff$ $\vec{G}$ бесконтурный. + \label{thm:correct-numbering} +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть $\vec{G} = (V, \alpha)$ --- бесконтурный. Тогда $(V, \alpha)$ является + упорядоченным множеством. Построим диаграмму упорядоченного множества $(V, + \alpha)$. Проведём нумерацию вершин $\vec{G}$, двигаясь по уровням снизу + вверх, слева направо. + + Если есть дуга $(v_i, v_j) \in \alpha$, то в силу упорядоченности $V$ будет + $v_i \leq v_j$, тогда на диаграмме упорядоченного множества $v_j$ имеет + большую высоту, чем $v_i$. В силу выбранной нумерации $i \leq j$. + + \textbf{Достаточность.} + + Пусть орграф $\vec{G}$ допускает правильную нумерацию и пусть он не является + бесконтурным $\implies$ в нём есть нетривиальный контур $v_{i_1}, v_{i_2}, + \dots, v_{i_k}, v_{i_1},\, k > 1 \implies$ так как нумерация правильная, то + имеем $i_1 < i_2 < \dots < i_k < i_1$, что невозможно. +\end{proof} + +\begin{corollary} + В любом графе можно ввести ориентацию рёбер так, чтобы он стал бесконтурным + орграфом. +\end{corollary} +\begin{proof} + Пусть $G = (V, \alpha)$ --- произвольный неориентированный граф. Выберем + произвольную нумерацию его вершин. Пусть $\set{v_i, v_j}$ --- некоторое + ребро $G$. Ориентируем его следующим образом: + \begin{equation*} + \begin{cases} + \set{v_i, v_j}, &i < j \\ + \set{v_j, v_i}, &i > j + \end{cases} + \end{equation*} + + Произведя таким образом ориентацию всех рёбер, мы получим правильную нумерацию + в построенном орграфе $\vec{G}$, и по теореме \ref{thm:correct-numbering} он + будет бесконтурным графом. +\end{proof} + +\begin{corollary} + В любом направленном графе можно переориентировать некоторые дуги так, что + в результате получится бесконтурный граф. +\end{corollary} +\begin{proof} + Полностью аналогично предыдущему следствию. +\end{proof} + +Так как в бесконтурном графе отношение взаимной достижимости $\varepsilon$ +является тождественным, то конденсация бесконтурного графа изоморфна самому +графу $(\vec{G}/\varepsilon \cong \vec{G})$. + +\begin{corollary} + Каждый бесконтурный граф имеет единственную базу, которая состоит из всех его + источников. +\end{corollary} + +Для построения правильной нумерации в бесконтурном графе можно воспользоваться +следующим алгоритмом. Пусть $v \in V,\, \vec{G} = (V, \alpha)$. $v$ --- +произвольная, $\vec{G}$ --- бесконтурный. Обозначим $A(v) = \set{u \in V : +(u, v) \in \alpha}$. Множество $P$ --- множество занумерованных вершин. +Изначально оно равно $\emptyset$. + +Пока множество $P$ отлично от множества $V$, выбираем такую вершину $v$, для +которой $A(v) = \emptyset$. Присваиваем вершине $v$ очередной номер и добавляем +в множество $P$. Удаляем вершину $v$ из всех множеств $A(u)$, куда она входит +(для тех вершин, в которые ведёт дуга из $v$). + +\begin{definition} + Рангом вершины $v$ в бесконтурном графе $\vec{G} = (V, \alpha)$ называется + её высота в упорядоченном множестве $(V, \alpha)$. +\end{definition} + +\begin{definition} + Ранжированным изображением бесконтурного графа называется орграф, получающийся + из диаграммы упорядоченного множества $(V, \alpha)$ ориентацией всех рёбер + снизу вверх и добавлением тех дуг, которые не были изображены на диаграмме. +\end{definition} + +\section{Матрица смежности бесконтурного графа. Расконтуривание. Оптимальное +расконтуривание. Теорема о минимальном расконтуривании.} + +\begin{theorem}[О матрице смежности бесконтурного графа] + Орграф $\vec{G} = (V, \alpha)$ является бесконтурным $\iff$ при некоторой + нумерации вершин его матрица смежности $A$ будет верхней треугольной матрицей, + то есть ниже главной диагонали стоят нули. + \label{thm:contour-free-matrix} +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть $\vec{G}$ --- бесконтурный граф. Тогда по теореме + \ref{thm:correct-numbering} существует правильная нумерация его вершин. + + Запишем матрицу смежности $\vec{G}$ в этой нумерации. Получим, что некоторый + элемент матрицы смежности $a_{ij} = 1 \iff (v_i, v_j) \in \alpha$. В силу + правильности нумерации $i \leq j$. То есть элемент $a_{ij}$ лежит не ниже + главной диагонали $\implies$ ниже главной диагонали нет единиц. + + \textbf{Достаточность.} + + Пусть при некоторой нумерации вершин $\vec{G}$ матрица смежности оказалась + верхней треугольной матрицей. Легко видеть, что эта нумерация будет + правильной. Рассмотрим $(v_i, v_j) \in \alpha$ --- произвольную $\iff a_{ij} = + 1,\, i \leq j$. +\end{proof} + +\begin{definition} + Расконтуривание $\vec{G} = (V, \alpha)$ --- такое множество его дуг $\alpha^* + \subseteq \alpha$, после удаления которых орграф становится бесконтурным. То + есть $\vec{G}^* = (V, \alpha \backslash \alpha^*)$ --- бесконтурный. +\end{definition} + +\begin{definition} + Расконтуривание называется минимальным, если никакая его собственная часть не + является расконтуриванием. +\end{definition} + +\begin{definition} + Расконтуривание называется оптимальным, если оно содержит наименьшее + возможное среди всех расконтуриваний данного орграфа число дуг. +\end{definition} + +Один из способов расконтуривания основан на теореме +\ref{thm:contour-free-matrix}. + +Если в матрице смежности, составленной при некоторой нумерации вершин, +ниже главной диагонали окажется некоторое количество единиц, то удалив +соответствующие дуги, получим орграф с правильной нумерацией вершин, и, +следовательно, удалённые дуги образуют расконтуривание. + +Очевидно, что наибольший интерес представляют минимальные и оптимальные +расконтуривания. Для поиска оптимального расконтуривания можно производить +различные нумерации вершин орграфа и среди них выбрать такие, что в матрице +смежности будет стоять минимальное количество единиц. + +Существует способ избежать полного перебора нумераций. + +\begin{theorem}[О минимальном расконтуривании] + Минимальное расконтуривание не нарушает связности орграфа. +\end{theorem} +\begin{proof} + $\vec{G} = (V, \alpha)$ --- орграф, не являющийся бесконтурным. Пусть он + связный (то есть его симметризация является связным графом). + + Пусть $\alpha^*$ --- минимальное расконтуривание. Будем удалять из $\vec{G}$ + дуги, входящие в состав $\alpha^*$ по одной. + + Пусть $(v_i, v_j) \in \alpha^*$ --- первая дуга в процессе удаления, после + изъятия которой граф окажется не связным. Это означает, что в симметризации + графа вершины $v_i$ и $v_j$ окажутся в разных компонентах связности. + + Следовательно, перед удалением дуги $(v_i, v_j)$ вершины $v_i$ и $v_j$ уже + не принадлежали никакому контуру. + + Удаление дуги $(v_i, v_j)$ не размыкает никакого контура $\implies$ исключив + эту дугу из расконтуривания, мы получим новое расконтуривание, которое + содержит на одну дугу меньше, чем $\alpha^*$. Это противоречит минимальности + $\alpha^*$. +\end{proof} + +Рассмотрим отношение $\sigma$ на множестве вершин орграфа $(V \times V)$. $(u, +v) \in \sigma \iff s(u) = s(v)$. $\sigma$ --- отношение, в котором состоят +вершины, если из них достижимы одни и те же стоки. Очевидно, что $\sigma$ +является отношением эквивалентности: рефлексивно, симметрично и транзитивно. + +Эквивалентность $\sigma$ может быть построена по матрице достижимости $D$ +следующим образом. + +Сначала в матрице достижимости определяются строки, соответствующие +стокам: в таких строках единицы стоят только на главной диагонали. Далее +из матрицы вычёркиваются столбцы, кроме столбца вершин, являющихся стоками. + +Получим прямоугольную матрицу вершин, совпадающие строки которой состоят в +отношении $\sigma$. + +\begin{theorem}[О бесконтурном фактор-графе $\vec{G}/\sigma$] + Фактор-граф $\vec{G}/\sigma$ любого бесконтурного графа $\vec{G}$ также + является бесконтурным. +\end{theorem} +\begin{proof} + От противного. Пусть $\vec{G}$ --- бесконтурный граф, а в $\vec{G}/\sigma$ + существует нетривиальный контур. + \begin{equation*} + \sigma(u_1) \to \sigma(u_2) \to \dots \to \sigma(u_k) \to \sigma(u_1),\, + k > 1 + \end{equation*} + + Так как существует дуга $(\sigma(u_1), \sigma(u_2)) \in \vec{G}/\sigma$, то + существуют представители соответствующих классов $u_1' \in \sigma(u_1), + u_2' \in \sigma(u_2), (u_1', u_2') \in \alpha$. + + Но тогда всякий сток, достижимый из вершины $u_2'$ достижим и из вершины + $u_1'$. Поэтому $s(u_1') \supseteq s(u_2')$. + + Так как $u_1'$ и $u_2'$ принадлежат разным классам отношения $\sigma$, то + $s(u_1') \neq s(u_2')$. Таким образом, $s(u_1') \supset s(u_2')$. + + Продолжая рассуждения для остальных дуг контура и учитывая, что множество $s$ + для всех вершин из одного класса равно, получаем: + \begin{equation*} + \underline{s(u_1')} \supset s(u_2') \supset \dots \supset s(u_k') \supset + \underline{s(u_1')} + \end{equation*} + + Получаем, что не существует нетривиального контура в фактор-графе. +\end{proof} + +\section{Проверяющий тест. Теорема о минимальном проверяющем тесте.} + +\begin{theorem}[О минимальных проверяющих тестах в системах с тождественным +отношением $\sigma$] + Если бесконтурный граф $\vec{G}$ имеет тождественное отношение $\sigma$, то + минимальный проверяющий тест для системы, представленной графом $\vec{G}$, + также будет и локализующим (то есть он позволяет указать отказавшую вершину). +\end{theorem} +\begin{proof} + Пусть функциональная система $\Sigma$ такова, что $\vec{G}(\Sigma)$ является + бесконтурным, а $\sigma = \Delta$. + + Это означает, что две вершины различны $u \neq v \iff s(u) \neq s(v)$. Так + как $\vec{G}(\Sigma)$ бесконтурный, то его конденсация с ним совпадает + $\vec{G} \cong \vec{G}/\varepsilon$. + + Таким образом, минимальный проверяющий тест будет состоять из проверок всех + стоков системы. Пусть в результате проверки сигнал о неисправности поступил + из стоков $u_1, \dots, u_k$. В силу тождественности отношения $\sigma$ + существует единственная вершина $v$, из которой достижимы эти стоки. По + условию сигнал о неисправности в системах такого вида наследуется, поэтому + результат тестирования может означать только одно --- вершина $v$ неисправна. +\end{proof} + +\section{Полный бесконтурный граф. Теорема о полных бесконтурных графах. +Характеризация входящих и выходящих деревьев.} + +\begin{definition} + Полный бесконтурный граф --- это такой рефлексивный бесконтурный граф, в + котором добавление любой дуги приводит к появлению нетривиального контура + (рефлексивный означает, что в каждой вершине есть петля). +\end{definition} + +\begin{theorem}[О полных бесконтурный графах] + $\forall n \in \mathbb{N}$ существует единственный с точностью до изоморфизма + полный бесконтурный $n$-вершинный граф. +\end{theorem} +\begin{proof} + Пусть $\vec{G} = (V, \alpha)$ --- полный бесконтурный граф. По теореме + \ref{thm:correct-numbering} он имеет правильную нумерацию вершин. + $V = \set{v_1, \dots, v_n}$. $(v_i, v_j) \in \alpha \implies i \leq j$. + + Пусть $\vec{H} = (U, \beta)$ --- другой полный бесконтурный граф с $n$ + вершинами. Он также имеет правильную нумерацию. + + Построим биекцию $\varphi : V \to U$ следующим образом: $\varphi(v_i) = u_i$. + Очевидно, что $\varphi$ --- биекция. При этом в силу полноты бесконтурных + графов $\vec{G}$ и $\vec{H}$ получаем: + \begin{equation*} + (v_i, v_j) \in \alpha \implies i \leq j \iff (u_i, u_j) \in \beta + \end{equation*} + + Таким образом, $\varphi$ --- изоморфизм. +\end{proof} + +Пусть $\vec{G} = (V, \alpha)$ --- полный бесконтурный граф. Тогда при правильной +нумерации его вершин матрица смежности будет верхней треугольной матрицей. Любая +Степень этой матрицы будет совпадать с ней самой $\implies D = A$. + +Так как $\vec{G}$ --- бесконтурный, то отношение достижимости $\delta$ является +порядком. $(V, \delta)$ --- упорядоченное множество. Так как $D = A \implies +\alpha = \delta \implies (V, \alpha)$ --- тоже упорядоченное множество. + +Отношение смежности транзитивно, то есть из любой цепи $u_1 \to u_2 \to \dots +\to u_k,\, k > 0 \implies \exists (u_1, u_k) \in \alpha$. + +Таким образом, диаграмма упорядоченного множества $(V, \alpha)$ представляет +собой цепь, в которой высота элемента равна количеству входящих в него дуг: +$h(v) = |\alpha^{-1}(v)|$. + +Другое название полных бесконтурных графов --- транзитивные турниры. + +Другим важным классом бесконтурных графов являются ориентированные деревья. + +\begin{definition} + Диграф $\vec{T}$ называется выходящим деревом, если он удовлетворяет следующим + двум условиям: + \begin{enumerate} + \item Симметризация $T$ --- дерево, + \item + Существует корень, то есть вершина, из которой достижимы все остальные + вершины. + \end{enumerate} +\end{definition} + +\begin{theorem}[Характеризация выходящих деревьев] + Антирефлексивный связный орграф $\vec{T}$ является выходящим деревом $\iff$ в + нём существует единственная вершина $v_0$ с нулевой степенью захода $(d^-(v_0) + = 0)$, а все остальные вершины $d^-(v) = 1, \forall v \neq v_0$. +\end{theorem} +\begin{proof} + \textbf{Необходимость.} + + Пусть антирефлексивный связный орграф $\vec{T}$ является выходящим деревом. + По определению в нём есть корень $v_0$, из которого достижимы все остальные + вершины. + + Пусть $d^-(v_0) > 0 \implies \exists v \neq v_0 : (v, v_0) \in \alpha$. Тогда + $v$ достижима из $v_0$, и $v_0$ достижима из $v$. Они взаимно достижимы + $\implies$ в $\vec{T}$ существует нетривиальный контур, а в его симметризации + --- цикл, что по определению невозможно $\implies d^-(v_0) = 0$. + + Рассмотрим произвольную $v \neq v_0$. Так как вершина $v$ достижима из корня + $v_0$, то существует цепь $v_0 \to v_1 \to \dots \to v_k \to v$. $d^-(v) \geq + 1$. Пусть $d^-(v) \geq 2$. + + Тогда найдутся две вершины $v_1$ и $v_2$ : $(v_1, v) \in \alpha, (v_2, v) \in + \alpha$. Так как $v_1$ и $v_2$ достижимы из $v_0$, то получаем, что существуют + два различных пути из $v_0$ в $v$. + + Тогда в симметризации найдутся две различных цепи между $v_0$ и $v$, что + невозможно. Таким образом, $d^-(v) = 1, v \neq v_0$. + + \textbf{Достаточность.} + + Пусть в связном антирефлексивном орграфе $\vec{T}$ существует единственная + вершина $v_0$, ($d^-(v_0) = 0$), а у всех остальных вершин $d^-(v) = 1$. + + Так как $\vec{T}$ связный, то и его симметризация $T$ --- связный граф. То + есть между вершиной $v_0$ и произвольной вершиной $v$ существует связывающая + их цепь $P$. + + Пронумеруем вершины этой цепи в порядке прохождения от $v_0$ к $v$: + $v_0 v_1 v_2 \dots v_k v$. + + Возвращаемся к орграфу $\vec{T}$. Так как $d^-(v_0) = 0$, то ребро $\set{v_0, + v_1}$ из $T$ в орграфе $\vec{T}$ может быть ориентированно только так: $(v_0, + v_1)$. + + Так как $d^-(v_1) = 1$ и есть дуга $(v_0, v_1)$, то ребро $\set{v_1, v_2}$ + может быть ориентированно только $(v_1, v_2)$. + + Продолжая рассуждения, получим, что все рёбра цепи $P$ в орграфе $\vec{T}$ + ориентированы от $v_0$ к $v$. Таким образом, в $\vec{T}$ существует + ориентация цепи из $v_0$ в $v$. То есть $v_0$ --- корень $\vec{T}$. + + Покажем, что симметризация $T$ --- дерево. Достаточно показать, что из $v_0$ + в $v$ существует единственная цепь. Предположим, что это не так и из вершины + $v_0$ в произвольную $v \neq v_0$ кроме $P$ существует ещё и цепь $P^*: v_0, + u_1, u_2, \dots, u_l, v$. Аналогично получим из $P^*$ ориентированную цепь в + орграфе $\vec{T}$. + + Пусть $v_s$ --- последняя вершина в порядке прохождения цепи $P$ от её конца, + которая также есть и в $P^*$. Тогда в $v_s$ входит две дуги, $d^-(v_s) \geq + 2$, что невозможно $\implies$ $T$ --- дерево, $\vec{T}$ --- выходящее дерево. +\end{proof} + +\begin{definition} + Если $\vec{T}$ --- выходящее дерево, то обратив его дуги получим + $\vec{T}^{-1}$ --- входящее дерево (симметризация входящего дерево будет + являться деревом, из любой вершины достижима $v_0$). +\end{definition} + +\begin{theorem}[Характеризация входящих деревьев] + Антирефлексивный связный орграф $\vec{T}$ является входящим деревом $\iff$ в + нём существует единственная вершина $v_0$ ($d^+(v_0) = 0$), а все остальные + вершины $d^+(v) = 1, v \neq v_0$. +\end{theorem} + +Во входящих деревьях вершина $v_0$ также называется корнем. + +\section{Турниры. Теорема о лидере. Теорема о гамильтоновой цепи.} + +\begin{definition} + Турнир --- полный направленный граф, то есть такой граф, в котором между + любыми двумя вершинами существует единственная дуга. +\end{definition} + +\begin{enumerate} + \item Полный бесконтурный граф является турниром (транзитивным); + \item + Пусть проводится круговой турнир в игре без ничьих (каждая команда играет с + каждой один раз). Сопоставив командам вершины, исходящую дугу, направление + которой ставится от победителя к проигравшему, получим турнир (без петель). + + Иногда определение турнира даётся следующим образом: турнир --- полный + направленный граф без петель. + \item + Пусть $K_n$ --- полный неориентированный граф. Ориентируем произвольным + образом каждое ребро $K_n$. Получим турнир без петель. Таким образом, можно + получить все турниры с заданным числом вершин. $K_n: m = \frac{n(n - 1}{2})$ + (всего $2^m$, оставить неизоморфные). +\end{enumerate} + +Заметим, что любой максимальный подграф турнира также является турниром. С +учётом этого можно предложить динамический алгоритм построения турнира с +заданным числом вершин. + +Рассмотрим $(n - 1)$-вершинный турнир $T_{n - 1}$. Добавим к нему одну вершину +и соединим её $(n - 1)$ рёбрами с вершинами $T_{n - 1}$. Для получения всех +турниров с числом вершин $n$, для которых $T_{n - 1}$ --- максимальный подграф +потребуется перебрать $2^{n - 1}$ вариантов ориентации добавленных рёбер. + +\begin{theorem}[О лидере] + Пусть $v_0$ --- одна из вершин турнира, имеющая максимальную степень исхода + (лидер). Тогда расстояние от $v_0$ до любой другой вершины равно 1 или 2. +\end{theorem} +\begin{proof} + Пусть $v_0$ --- лидер. То есть $d^+(v_0) \geq d^+(v), \forall v \in V$. + + Доказательство методом от противного. + + Пусть в турнире $T$ существует вершина $v$, расстояние от $v_0$ до неё + $d(v_0, v) > 2$. Имеем дугу $(v, v_0)$. Кроме этого не существует пути длины + 2 из $v_0$ к $v$. + + Пусть $u$ --- произвольная вершина турнира, в которую идёт дуга из $v_0$. Если + бы существовала дуга $(u, v) \in \alpha$, то получили бы путь длины 2 из $v_0$ + в $v$. $(v, u) \in \alpha$. Таким образом, если из вершины $v_0$ идёт дуга в + некоторую вершину $u$, то и из $v$ в $u$ тоже идёт дуга. Кроме того, из $v$ + идёт дуга в вершину $v_0$. + + Тогда получаем, что степень исходов вершины $d^+(v) > d^+(v_0)$, что + противоречит определению лидера. +\end{proof} + +\begin{theorem}[О гамильтоновой цепи] + В любом турнире с числом вершин $n \geq 2$ существует гамильтонова цепь. +\end{theorem} +\begin{proof} + ММИ по числу вершин. + + Предположим, что теорема справедлива для всех турниров с числом вершин $k$. + Рассмотрим $(k + 1)$-вершинный турнир $\vec{T}$. $v_1 v_2 \dots v_k + v_{k + 1}$. + + Удалим из $\vec{T}$ вершину $v_{k + 1}$ со всеми её дугами. Максимальный + подграф $\vec{T} - v_{k + 1}$ является турниром и имеет $k$ вершин $\implies$ + в нём существует гамильтонова цепь. + + Не нарушая общности, будем считать, что нумерация вершин соответствует их + порядку в прохождении цепи. $v_1 \to \dots \to v_{k - 1} \to v_k$ в + подграфе $\vec{T} - v_{k + 1}$. Вернёмся к турниру $\vec{T}$. Рассмотрим + три возможных случая: + \begin{enumerate} + \item + $(v_{k + 1}, v_1) \in \alpha)$. $v_{k + 1}, v_1, \dots, v_k$ --- + гамильтонова цепь. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-hamilton1} + \end{center} + \item + $(v_k, v_{k + 1}) \in \alpha)$. Очевидно, $v_1, \dots, v_k, v_{k + 1}$ + --- гамильтонова цепь. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-hamilton2} + \end{center} + \item + $(v_{k + 1}, v_1) \not\in \alpha$ и $(v_k, v_{k + 1}) \not\in \alpha$. В + силу полноты $(v_1, v_{k + 1}) \in \alpha, (v_{k + 1}, v_k) \in \alpha$. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-hamilton3} + \end{center} + + Последовательно просматриваем вершины от $v_1$ до $v_k$ в поиске первой + вершины $v_i : (v_{k + 1}, v_i) \in \alpha$. Тогда получаем гамильтонову + цепь $v_1, \dots, v_{i - 1}, v_{k + 1}, v_i, \dots v_k$. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-hamilton4} + \end{center} + \end{enumerate} +\end{proof} + +\section{Сильный турнир. Теорема о контурах сильно связных турниров. Следствие +(гамильтоновы турниры).} + +\begin{definition} + Турнир $T$ называется сильным, если он является сильно связным орграфом, то + есть любые две вершины в нём взаимно достижимы. +\end{definition} + +\begin{theorem}[О контурах сильно связных турниров] + В любом сильном турнире с числом вершин $n \geq 3$ каково бы ни было + натуральное число $k \leq n \quad (k \geq 3)$ через любую вершину проходит + некоторый контур длины $k$. +\end{theorem} +\begin{proof} + Пусть $\vec{T}$ --- сильный турнир, $v_1$ --- произвольная вершина. В сильных + турнирах нет источников и стоков, поэтому существует по крайней мере одна + дуга входящая и одна выходящая в/из $v_1$. + + Пусть $(v_1, v_2) \in \alpha$. Продолжим путь от $(v_1, v_2)$. $v_1 v_2 v_3 + \dots v_l v_1$, так как турнир сильный. Так как $(v_1, v_2) \in \alpha, + (v_l, v_1) \in \alpha$, то пусть $v_i$ --- первая вершина среди вершин $v_2 + \dots v_l$, в которой $(v_i, v_1) \in \alpha$. + + Таким образом мы имеем контур длины 3, проходящий через $v_1$: $v_1, v_{i - + 1}, v_i$. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-strong1} + \end{center} + + Таким образом, в любом сильном турнире с числом вершин $n \geq 3$ через + любую вершину проходит контур длины 3. + + ММИ. Пусть в сильном турнире существует контур длины $k \geq 3$, проходящий + через произвольную вершину $v_1$. Докажем, что в этом случае через неё + проходит контур длины $(k + 1)$. + + Два случая: + \begin{enumerate} + \item + В $\vec{T}$ существует вершина $v$ не принадлежащая контуру: $(v_i, v) \in + \alpha, (v, v_j) \in \alpha$. Не нарушая общности будем считать, что $i < + j$. Повторяя рассуждения, найдём между $v_i$ и $v_j$ вершину $v_s$ первую, + в которой дуга $(v, v_s) \in \alpha$. Получаем контур длины $(k + 1)$: + $v_1, \dots, v_{s - 1}, v, v_s, \dots, v_k, v_1$. + \begin{center} + \includegraphics[width=0.3\textwidth]{lec14-strong2} + \end{center} + \item + Предположим, что ни одной такой вершины $v$, как в случае 1, в $\vec{T}$ + нет. То есть для произвольной вершины $v$ дуги идут либо во все вершины + контура, либо от вершин контура к $v$. + + Будем говорить о вершинах I-го и II-го типов. Соберём эти вершины в + подмножества. + \begin{center} + \includegraphics[width=0.5\textwidth]{lec14-strong3} + \end{center} + + Легко заметить, что множества вершин I и II типов не пусты. В самом деле, + если бы $V_I = \emptyset$, то из вершин II типа мы не смогли бы попасть в + вершины контура, а это противоречит тому, что турнир сильный. Аналогично, + если $V_{II} = \emptyset$. + + Утверждается, что существуют $u_1 \in V_I$ и $u_0 \in V_{II}$ такие, что + $(u_0, u_1) \in \alpha$. Действительно, если бы таких не было, то было бы + невозможно попасть из вершин II в I. Тогда в турнире $\vec{T}$ строим + контур длины $(k + 1)$: $u_0, u_1, v_1, v_2, \dots, v_{k - 1}, u_0$. + + Таким образом, мы построили контур длины $(k + 1)$. + \begin{center} + \includegraphics[width=0.5\textwidth]{lec14-strong3} + \end{center} + \end{enumerate} +\end{proof} + +\begin{corollary} + Турнир является гамильтоновым $\iff$ он сильно связный, то есть только сильные + турниры являются гамильтоновыми. +\end{corollary} + +\section{Теорема о МРP турнира. Теорема о МВP транзитивного турнира.} + +Рассмотренные ранее понятия вершинного и рёберного расширения сохраняют свой +смысл и для орграфов. + +\begin{theorem}[МРР турнира] + Любой $n$-вершинный турнир $\vec{T_n}$ (с петлями или без) имеет единственное + с точностью до изоморфизма минимальное рёберное 1-расширение $\vec{K_n}$. + При $k > 1$ турниры не имеют минимальных рёберных расширений. +\end{theorem} +\begin{proof} + Убедимся, что $\vec{K_n}$ является рёберным 1-расширением $\vec{T_n}$. + Удалим из орграфа $\vec{K_n}$ произвольную дугу $(v_1, v_2)$. + + Тогда в получившемся орграфе между вершинами $v_1$ и $v_2$ останется + единственная дуга $(v_2, v_1)$. + + Выберем в турнире $\vec{T_n}$ две произвольные вершины $u_1$ и $u_2$: + $(u_2, u_1) \in \alpha$. + + Очевидно, что биекция $u_1, u_2, \dots u_n \to v_1, v_2, \dots v_n$ является + вложением. + + Пусть $n$-вершинный орграф $\vec{G}$, отличный от полного, является + минимальным рёберным 1-расширением $\vec{T_n}$. + + Тогда в $\vec{G}$ можно найти $(u_1, u_2) \not\in \alpha$. Тогда $(\vec{G} - + (u_2, u_1))$ $u_1$ и $u_2$ не соединены дугой ни в каком направлении. + + Очевидно, что $\vec{T_n}$ не может вкладываться в получившийся орграф. + + Рассмотрим $k > 1$. Выбрав две произвольные вершины, между которыми есть + пара встречных дуг, рассмотрим граф, получающийся после их удаления и + удаления произвольных $(k - 2)$ других дуг. + + В этом графе будет пара вершин, между которыми не будет дуг. Очевидно, что + турнир в такой граф вкладываться не может. +\end{proof} + +\begin{theorem}[О минимальном вершинном $k$-расширении транзитивного турнира] + Транзитивный турнир $\vec{T_n}$ при $n > 2$ имеет единственное минимальное + вершинное $k$-расширение при $\forall k \in \mathbb{N}$, которое является + $\vec{T_{n + k}}$. +\end{theorem} +\begin{proof} + Убедимся, что $\vec{T_{n + k}}$ является $k$-расширением для $\vec{T_n}$. + Удаление $k$ вершин из $\vec{T_{n + k}}$ приведёт к удалению соответствующих + строк и столбцов из матрицы смежности. Очевидно, что в результате мы получим + матрицу смежности турнира $\vec{T_n}$. + + \textbf{Докажем минимальность.} + + Пусть существует минимальное вершинное $k$-расширение турнира $\vec{T_n}$ c + меньшим числом дуг, чем $\vec{T_{n + k}}(\vec{G}^*)$. $\vec{G}^*$ не является + турниром, так как число дуг меньше $\implies$ в $\vec{G}^*$ существует как + минимум две вершины $v_1$ и $v_2$, между которыми нет дуг. + + Рассмотрим граф, получающийся из $\vec{G}^*$ удалением любых $k$ вершин, + кроме $v_1$ и $v_2$. Очевидно, что в получившийся граф нельзя вложить + $\vec{T_n}$. + + \textbf{Докажем единственность.} + + Предположим, что существует ещё одно МВ-kР $\vec{T_n}$, отличное от + $\vec{T_{n + k}}$. Обозначим его $\vec{G}^*$. + + По рассмотренному ранее $\vec{G}^*$ будет турниром, но нетранзитивным + $\implies$ в нём существует как минимум один нетривиальный контур. + + Рассмотрим граф, получающийся из $\vec{G}^*$ удалением $k$ вершин, не + входящих в этот контур. Любой подграф турнира тоже турнир, а в получившемся + графе есть нетривиальный контур $\implies$ этот турнир не изоморфен + транзитивному. +\end{proof} + +\begin{remark} + При $n = 2$, $\vec{T_2}$ имеет два неизоморфных МВ-1Р. При $k > 1$, любой + $\vec{T_{k + 2}}$ является МВ-kР турнира $\vec{T_2}$. +\end{remark} + +\begin{remark} + Минимальное вершинное $k$-расширение транзитивного $\vec{T_n}$ является и его + точным вершинным $k$-расширением. +\end{remark} + \section{Раскраски графов. Критерий двудольности. Теорема о 5 красках} \begin{definition} \label{def:coloring} diff --git a/graphs-exam/images/lec10-dijkstra1.png b/graphs-exam/images/lec10-dijkstra1.png Binary files differnew file mode 100644 index 0000000..0cdac8f --- /dev/null +++ b/graphs-exam/images/lec10-dijkstra1.png diff --git a/graphs-exam/images/lec11-bellman1.png b/graphs-exam/images/lec11-bellman1.png Binary files differnew file mode 100644 index 0000000..1101b4b --- /dev/null +++ b/graphs-exam/images/lec11-bellman1.png diff --git a/graphs-exam/images/lec11-floyd1.jpeg b/graphs-exam/images/lec11-floyd1.jpeg Binary files differnew file mode 100644 index 0000000..e831467 --- /dev/null +++ b/graphs-exam/images/lec11-floyd1.jpeg diff --git a/graphs-exam/images/lec14-hamilton1.jpeg b/graphs-exam/images/lec14-hamilton1.jpeg Binary files differnew file mode 100644 index 0000000..f449f35 --- /dev/null +++ b/graphs-exam/images/lec14-hamilton1.jpeg diff --git a/graphs-exam/images/lec14-hamilton2.jpeg b/graphs-exam/images/lec14-hamilton2.jpeg Binary files differnew file mode 100644 index 0000000..1adbe3b --- /dev/null +++ b/graphs-exam/images/lec14-hamilton2.jpeg diff --git a/graphs-exam/images/lec14-hamilton3.jpeg b/graphs-exam/images/lec14-hamilton3.jpeg Binary files differnew file mode 100644 index 0000000..cf85e07 --- /dev/null +++ b/graphs-exam/images/lec14-hamilton3.jpeg diff --git a/graphs-exam/images/lec14-hamilton4.jpeg b/graphs-exam/images/lec14-hamilton4.jpeg Binary files differnew file mode 100644 index 0000000..14ded8d --- /dev/null +++ b/graphs-exam/images/lec14-hamilton4.jpeg diff --git a/graphs-exam/images/lec14-strong1.jpeg b/graphs-exam/images/lec14-strong1.jpeg Binary files differnew file mode 100644 index 0000000..30126f1 --- /dev/null +++ b/graphs-exam/images/lec14-strong1.jpeg diff --git a/graphs-exam/images/lec14-strong2.jpeg b/graphs-exam/images/lec14-strong2.jpeg Binary files differnew file mode 100644 index 0000000..37324b8 --- /dev/null +++ b/graphs-exam/images/lec14-strong2.jpeg diff --git a/graphs-exam/images/lec14-strong3.png b/graphs-exam/images/lec14-strong3.png Binary files differnew file mode 100644 index 0000000..3e601b3 --- /dev/null +++ b/graphs-exam/images/lec14-strong3.png diff --git a/graphs-exam/images/lec4-mr-1r-abrosimov.png b/graphs-exam/images/lec4-mr-1r-abrosimov.png Binary files differnew file mode 100644 index 0000000..4394b02 --- /dev/null +++ b/graphs-exam/images/lec4-mr-1r-abrosimov.png diff --git a/graphs-exam/images/lec4-mr-1r-harari.png b/graphs-exam/images/lec4-mr-1r-harari.png Binary files differnew file mode 100644 index 0000000..fd94560 --- /dev/null +++ b/graphs-exam/images/lec4-mr-1r-harari.png diff --git a/graphs-exam/images/lec4-mv-1r-abrosimov.jpeg b/graphs-exam/images/lec4-mv-1r-abrosimov.jpeg Binary files differnew file mode 100644 index 0000000..55d50ba --- /dev/null +++ b/graphs-exam/images/lec4-mv-1r-abrosimov.jpeg diff --git a/graphs-exam/images/lec4-mv-1r-hayes.png b/graphs-exam/images/lec4-mv-1r-hayes.png Binary files differnew file mode 100644 index 0000000..75891fa --- /dev/null +++ b/graphs-exam/images/lec4-mv-1r-hayes.png diff --git a/graphs-exam/images/lec8-ore1.jpeg b/graphs-exam/images/lec8-ore1.jpeg Binary files differnew file mode 100644 index 0000000..5b6b930 --- /dev/null +++ b/graphs-exam/images/lec8-ore1.jpeg |
