path: root/graphs-exam/graphs-exam.tex

\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}
\newcommand{\ds}{\displaystyle}

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

\begin{definition}[Операции над отношениями]
  Пусть $\rho, \sigma \subseteq A \times B$.
  \begin{enumerate}
    \item
      Пересечение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
      \rho \land (a, b) \in \sigma}$
    \item
      Объединение: $\rho \cap \sigma = \set{(a, b) \in A \times B : (a, b) \in
      \rho \lor (a, b) \in \sigma}$
    \item
      Дополнение: $\overline{\rho} = \set{(a, b) \in A \times B : (a, b) \not\in
      \rho}$
    \item
      Обращение: $\rho^{-1} \subseteq B \times A,\, \rho^{-1} = \set{(b, a) \in
      B \times A : (a, b) \in \rho}$
    \item
      Умножение. Пусть $\rho \subseteq A \times B,\, \sigma \subseteq B \times
      C$. Тогда $\rho \circ \sigma \subseteq A \times C,\, \rho \circ \sigma =
      \set{(a, c) \in A \times C : (\exists b \in B) (a, b) \in \rho \land (b,
      c) \in \sigma}$.
  \end{enumerate}
  \label{def:rel-op}
\end{definition}


\section{Операции над матрицами: пересечение, сложение, дополнение,
транспонирование, умножение. Связь между операциями над матрицами и
отношениями.}

\begin{definition}[Операции над матрицами]
  $M(m, n)$ --- множество всех двоичных булевых матриц размерности $m \times n$.
  Пусть $M, N \in M(m, n)$.

  \begin{enumerate}
    \item Пересечение: $M \land N : (M \land N)_{ij} = M_{ij} \cdot N_{ij}$
    \item Сложение: $M + N : (M + N)_{ij} = M_{ij} + N_{ij}$
    \item Дополнение: $M' : (M')_{ij} = (M_{ij})'$
    \item Транспонирование: $M^T \in M(n, m),\, (M^T)_{ij} = M_{ji}$
    \item
      Умножение $M \in M(m, n),\, N \in M(n, p)$: $MN \in M(m, p),\,
      (MN)_{ik} = \sum_{j = 1}^n M_{ij} N_{jk}$
  \end{enumerate}
  \label{def:mat-op}
\end{definition}

\begin{theorem}[Связь между операциями над отношениями и их матрицами]
  Пусть $\rho, \sigma \in A \times B (|A| = m, |B| = n)$. Тогда
  \begin{enumerate}
    \item $M(\rho \cap \sigma) = M(\rho) \land M(\sigma)$
    \item $M(\rho \cup \sigma) = M(\rho) + M(\sigma)$
    \item $M(\overline\rho) = (M(\rho))'$
    \item $M(\rho^{-1}) = (M(\rho))^T$
    \item
      $\rho \subseteq A \times B,\, \sigma \subseteq B \times C : M(\rho \circ
      \sigma) = M(\rho) M(\sigma)$
  \end{enumerate}
  \label{def:mat-rel-op}
\end{theorem}


\section{Срез отношения через элемент и через множество. Тождественное
отношение. Классификация отношений: рефлексивность, антирефлексивность,
симметричность, антисимметричность. Отношение эквивалентности, отношение
порядка.}

\begin{definition}
  Срезом отношения $\rho \subseteq A \times B$ через элемент $a \in A$
  называется множество $\rho(a) = \set{b \in B : (a, b) \in \rho} \subseteq B$.
  \label{def:slice-elem}
\end{definition}

\begin{definition}
  Срезом отношения $\rho \subseteq A \times B$ через подмножество $X \subseteq
  A$ называется множество $\rho(a) = \ds\bigcup_{a \in X} \rho(a) \subseteq B$.
  \label{def:slice-set}
\end{definition}

\begin{definition}
  Отношения между элементами одного и того же множества называются отношениями
  на множестве $A$. $\rho \subseteq A \times A$.
  \label{def:self-rel}
\end{definition}

\begin{definition}
  Тождественное отношение на множестве $A$ обозначается $\Delta \subseteq A
  \times A$.
  \begin{align*}
    (x, y) \in \Delta &\iff x = y \\
    M(\Delta) = E&,\, E = \begin{cases}
      0, &i \neq j \\
      1, &i = j
    \end{cases}
  \end{align*}
  \label{def:identity-rel}
\end{definition}

\begin{definition}[Классификация отношений]
  \begin{enumerate}
    \item
      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall x
      \in A) ((x, x) \in \rho)$. В матрице отношения элементы главной диагонали
      равны 1.
    \item
      Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall
      x \in A) ((x, x) \not\in \rho)$. В матрице отношения элементы главной
      диагонали равны 0.
    \item
      Отношение $\rho \subseteq A \times A$ симметрично $\iff (\forall x, y
      \in A) ((x, y) \in \rho \implies (y, x) \in \rho)$. Матрица отношения
      симметрична относительно главной диагонали.
    \item
      Отношение $\rho \subseteq A \times A$ антисимметрично $\iff (\forall x,
      y \in A) ((x, y) \in \rho \land (y, x) \in \rho) \implies (x = y)$. В
      матрице отношения элементы, симметричные единицам относительно главной
      диагонали, равны нулю (исключение --- сама главная диагональ).
    \item
      Отношение $\rho \subseteq A \times A$ транзитивно $\iff (\forall x, y, z
      \in A) ((x, y) \in \rho \land (y, z) \in \rho \implies (x, z) \in \rho)$.
  \end{enumerate}
  \label{def:rel-classification}
\end{definition}

\begin{definition}
  Отношением эквивалентности на $A$ называется отношение $\varepsilon \subseteq
  A \times A$, которое одновременно рефлексивно, симметрично и транзитивно.
  \label{def:equivalence}
\end{definition}

\begin{definition}
  Отношение $\omega \subseteq A \times A$ называется отношением порядка, если
  оно рефлексивно, антисимметрично и транзитивно.
  \label{def:order}
\end{definition}


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


\section{Типы графов: ориентированные графы, неориентированные графы, диграфы,
полные графы, вполне несвязные графы. Симметризация.}

\dots

\section{Степени вершин. Спецификация.}

\dots

\section{Двудольные графы. Звезды.}

\dots

\section{Операции над графами: дополнение, объединение, соединение, декартово
произведение, тензорное произведение, сильное произведение. n-мерная решетка,
n-мерный тор.}

\dots

\section{Теорема Эйлера о степенях вершин. Однородные графы.}

\dots

\section{Степенное множество. Теорема о степенном множестве.}

\dots

\section{Вектор степеней. Критерии графичности вектора Гавела-Хакими. Процедура
layoff. Критерий графичности Эрдеша-Галлаи.}

\dots

\section{Переключения ребер. Функциональные и контрфункциональные графы.}

\dots

\section{Изоморфизм и вложение. Немое изображение, абстрактные графы. Униграфы.}

\dots

\section{Автоморфизм. Подобные вершины, подобные ребра. Тождественные
(ассиметричные графы). Симметричные графы.}

\dots

\section{Часть графа и подграф. Максимальный подграф. Колода.}

\dots

\section{Реконструируемость графов. Гипотезы Келли-Улама и Харари.}

\dots

\section{Инварианты. Примеры полных инвариантов.}

\dots

\section{Отказоустойчивые реализации. Вершинные и реберные расширения.
Минимальные, неприводимые, тривиальные, точные расширения.}

\dots

\section{Минимальные вершинные расширения, основные свойства. Леммы. Минимальные
вершинные 1-расширения цепей. Точные расширения. Минимальные вершинные
1-расширения циклов.}

\dots

\section{Минимальные реберные расширения, основные свойства. Минимальные
реберные 1-расширения цепей и циклов.}

\dots

\section{Связь точных расширений и симметричности.}

\dots



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