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