\documentclass[a4paper,oneside,12pt]{extbook}

\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage[
  left=2cm,right=2cm,
  top=2.5cm,bottom=2.5cm
]{geometry}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{braket} % \set
\usepackage{hyperref}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\qedsymbol}{$\blacksquare$}
\newcommand{\link}{\hyperref}

\input{style.tex}

\begin{document}

\chapter*{Введение}

\section{Декартово произведение. Бинарные отношения. Пустое и универсальное
отношения. Операции над отношениями: пересечение, объединение, дополнение,
обращение, умножение.}

\begin{definition}
  Пусть $A$, $B$ --- два непустых множества. Декартовым произведением $A$ и $B$
  называется множество $A \times B = \set{(a, b) : a \in A,\, b \in B}$
  \label{def:decart-cross}
\end{definition}

\begin{definition}
  Бинарным отношением между множествами A и B называется всякое подмножество
  $A \times B$. $\rho \subseteq A \times B$.
  \label{def:bin-rel}
\end{definition}

\begin{definition}
  Пустое отношение --- это отношение, не содержащее ни одной пары. Обозначение:
  $\emptyset$.
  \label{def:empty-set}
\end{definition}

\begin{definition}
  Универсальное отношение содержит все возможные упорядоченные пары.
  $\forall \rho: \emptyset \subseteq \rho \subseteq A \times B$.
  \label{def:universal-set}
\end{definition}


\chapter{Основные алгебраические конструкции для графов}


\chapter{Основные типы неориентированных графов}


\chapter{Пути в орграфах}

\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}