From 5ab3b3d85d3d30323f19a155988fcc0bd5de446c Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 25 Dec 2022 00:28:46 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?= =?UTF-8?q?=20=D0=BD=D0=B5=D1=81=D0=BA=D0=BE=D0=BB=D1=8C=D0=BA=D0=BE=20?= =?UTF-8?q?=D0=B2=D0=BE=D0=BF=D1=80=D0=BE=D1=81=D0=BE=D0=B2=20=D0=B8=D0=B7?= =?UTF-8?q?=20=D1=82=D1=80=D0=B5=D1=82=D1=8C=D0=B5=D0=B9=20=D0=B3=D0=BB?= =?UTF-8?q?=D0=B0=D0=B2=D1=8B?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- graphs-exam/graphs-exam.pdf | Bin 117360 -> 201712 bytes graphs-exam/graphs-exam.tex | 139 +++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 138 insertions(+), 1 deletion(-) (limited to 'graphs-exam') diff --git a/graphs-exam/graphs-exam.pdf b/graphs-exam/graphs-exam.pdf index 426953a..88ac41e 100644 Binary files a/graphs-exam/graphs-exam.pdf and b/graphs-exam/graphs-exam.pdf differ 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} -- cgit v1.2.3