Добавлены несколько вопросов из третьей главы

2 files changed, 138 insertions, 1 deletions

diff --git a/graphs-exam/graphs-exam.pdf b/graphs-exam/graphs-exam.pdf
index 426953a..88ac41e 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 af93dca..b5e8217 100644
--- a/graphs-exam/graphs-exam.tex
+++ b/graphs-exam/graphs-exam.tex
@@ -11,10 +11,26 @@
 \usepackage{amsthm}
 \usepackage{amssymb}
 \usepackage{braket} % \set
+\usepackage{hyperref}
+
+\hypersetup{
+  colorlinks=true,
+  linkcolor=blue,
+}
 
 \renewcommand{\emptyset}{\varnothing}
+\renewcommand{\qedsymbol}{$\blacksquare$}
+\newcommand{\link}{\hyperref}
+
+\theoremstyle{definition}
 \newtheorem{definition}{Определение}
 
+\theoremstyle{plain}
+\newtheorem{theorem}{Теорема}
+
+\theoremstyle{definition}
+\newtheorem{remark}{Замечание}[theorem]
+
 \begin{document}
 
 \chapter*{Введение}
@@ -56,6 +72,127 @@
 
 \chapter{Пути в орграфах}
 
-\dots
+\section{Источники и стоки. Фактор-граф. Конденсация и ее свойства.
+Бесконтурность конденсации.}
+% Лекция 12
+
+\begin{definition}
+  Источником в орграфе называется такая его вершина, которая не достижима ни из
+  какой другой его вершины.
+  \label{def:source}
+\end{definition}
+
+\begin{definition}
+  Стоком в орграфе называется вершина, из которой не достижима никакая другая
+  вершина орграфа.
+  \label{def:sink}
+\end{definition}
+
+\begin{definition}
+  Пусть $\vec{G} = (V, \alpha)$ --- некоторый орграф, а $\theta \subseteq V
+  \times V$ --- отношение эквивалентности на множестве его вершин.
+
+  Фактор-графом орграфа $\vec{G}$ по эквивалентности $\theta$ называется орграф
+  $\vec{G}/\theta$, вершинами которого являются классы эквивалентности отношения
+  $\theta$, при этом из вершины $\theta(u)$ проведена дуга в $\theta(v)$, если
+  существуют вершины $u' \in \theta(u), v' \in \theta(v) : (u', v') \in \alpha$.
+  \label{def:factor}
+\end{definition}
+
+\begin{definition}
+  Конденсация орграфа $\vec{G} = (V, \alpha)$ --- это фактор-граф
+  $\vec{G}/\varepsilon$ (по отношению взаимной достижимости).
+
+  Так как классами отношения $\varepsilon$ являются сильные компоненты орграфа,
+  то они и будут вершинами конденсации.
+  \label{def:condensation}
+\end{definition}
+
+% TODO: свойства конденсации
+
+\begin{theorem}[Бесконтурность конденсации]
+  Конденсация всякого орграфа является бесконтурным графом.
+  \label{thm:acyclic-condensation}
+\end{theorem}
+\begin{proof}
+  Предположим, что это не так. Пусть $\vec{G} = (V, \alpha)$ и в
+  $\vec{G}/\varepsilon$ существует нетривиальный контур. $\varepsilon(u_1) \to
+  \varepsilon(u_2) \to \dots \to \varepsilon(u_k),\, k > 1$.
+
+  В любом классе отношения $\varepsilon$ орграфа $\vec{G}$ все вершины
+  взаимно достижимы. $\varepsilon(u_1) \to \varepsilon(u_2) \to \dots \to
+  \varepsilon(u_k) \to \varepsilon(u_1)$.
+
+  По определению конденсации в $\vec{G}$ существуют вершины $u_1' \in
+  \varepsilon(u_1),\, u_2' \in \varepsilon(u_2) : (u_1', u_2') \in \alpha$ в
+  орграфе $\vec{G}$. Вершина $u_2$ достижима из $u_1$.
+
+  Аналогично, $u_3$ достижима из $u_2$ и так далее. $u_k$ достижима из $u_{k -
+  1}$, $u_1$ достижима из $u_k$.
+
+  В силу транзитивности получаем, что вершина $u_1$ достижима из $u_2$ и
+  наоборот. То есть $u_1$ и $u_2$ взаимно достижимы. По определению
+  конденсации $u_1$ и $u_2$ должны принадлежать одному классу $\varepsilon$.
+  \emph{Это противоречие}.
+\end{proof}
+
+\section{Раскраски графов. Критерий двудольности. Теорема о 5 красках}
+
+\begin{definition} \label{def:coloring}
+  Рассмотрим граф $G = (V, \alpha)$. Каждой его вершине припишем некоторый цвет
+  так, чтобы смежные вершины имели разные цвета. Обозначим цвета числами $1,
+  \dots, p$. Тогда раскраску графа можно рассматривать как функцию $f : V \to
+  \set{1, p}$ если $\set{v_i, v_j} \in \alpha \implies f(v_i) \neq f(v_j)$.
+  При этом говорят, что граф $G$ допускает раскраску в $p$ цветов или является
+  $p$-раскрашиваемым.
+\end{definition}
+
+\begin{definition} \label{def:chroma-num}
+  Минимальное значение $p$, при котором граф является $p$-раскрашиваемым,
+  называется его хроматическим числом и обозначается $\chi(G)$. Аналогичным
+  образом можно рассматривать раскраску ребер. Соответствующий хроматическому
+  числу параметр в этом случае называется хроматическим индексом.
+\end{definition}
+
+Интерес представляет описание графов с заданным хроматическим числом. Например,
+$\chi(G) = 1$ --- вполне несвязные $O_n$. Графы с $\chi(G) = 2$ --- это
+двудольные графы, отличные от вполне несвязных.
+
+\begin{theorem}[Кёнига, Критерий двудольности]
+  Граф является двудольным $\iff$ он не содержит циклов нечётной длины.
+  \label{thm:konig} \label{thm:crit-bipart}
+\end{theorem}
+
+\begin{theorem}[О 5 красках, Хивуд]
+  Всякий планарный граф допускает раскраску в 5 цветов, то есть $\chi(G) \leq
+  5$.
+  \label{thm:5-colors}
+\end{theorem}
+\begin{proof}
+  Очевидно, что $\forall G = (V, \alpha),\, n \leq 5$, допускает раскраску
+  в 5 цветов.
+
+  Доказательство по ММИ. Пусть $n$-вершинный планарный граф с $n > 5$
+  допускает раскраску в 5 цветов. Покажем, что граф $H$ с $(n + 1)$ вершинами
+  тоже допускает раскраску в 5 цветов.
+
+  В силу планарности $H$ в нём существует вершина $v$ со степенью меньше или
+  равной 5. Рассмотрим два случая:
+  \begin{enumerate}
+    \item
+      $d(v) < 5$. Тогда $H - \set{v}$ --- по предположению 5-раскрашиваемый.
+      Возвращаясь к графу $H$, остальные раскрашиваем как $H - \set{v}$, а
+      вершину $v$ в цвет, отличный от цвета смежных вершин.
+    \item
+      $d(v) = 5$. $v_1, \dots, v_5$ не могут быть все попарно смежными (иначе
+      будет $K_5$). То есть как минимум одна пара этих вершин, несмежных между
+      собой. Пусть это $v_1$ и $v_2$. Рассмотрим граф, получающийся из $H$
+      объединением $v_1$ и $v_2$ (\link[def:factor]{фактор-граф} по отношению
+      $\theta$, где $\set{v_1, v_2}$). По предположению этот граф допускает
+      раскраску пятью цветами. Возвращаясь к $H$, оставляем раскраску, а $v_1$ и
+      $v_2$ раскрашиваем в цвет $\set{v_1, v_2}$.
+  \end{enumerate}
+\end{proof}
+
 
 \end{document}