From e3c06ad0a6ae036e16eaa6458720c637dc601733 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Thu, 5 Jan 2023 16:56:44 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?= =?UTF-8?q?=20=D0=B2=D1=82=D0=BE=D1=80=D0=B0=D1=8F=20=D0=B3=D0=BB=D0=B0?= =?UTF-8?q?=D0=B2=D0=B0?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- graphs-exam/graphs-exam.pdf | Bin 274101 -> 334742 bytes graphs-exam/graphs-exam.tex | 798 +++++++++++++++++++++++++++++++++++++++++++- graphs-exam/style.tex | 33 +- 3 files changed, 810 insertions(+), 21 deletions(-) diff --git a/graphs-exam/graphs-exam.pdf b/graphs-exam/graphs-exam.pdf index 876cc67..b6eea17 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 ab75c2a..338b357 100644 --- a/graphs-exam/graphs-exam.tex +++ b/graphs-exam/graphs-exam.tex @@ -193,70 +193,745 @@ \section{Типы графов: ориентированные графы, неориентированные графы, диграфы, полные графы, вполне несвязные графы. Симметризация.} -\dots +\begin{definition} + Орграфом $\vec{G} = (V, \alpha)$, где $V$ --- конечное непустое множество, а + $\alpha \subseteq V \times V$. Элементы множества $V$ называются вершинами, а + элементы множества $\alpha$ --- дугами. $V$ --- множество вершин, $\alpha$ + --- отношение смежности. + \label{def:orgraph} +\end{definition} + +$(u, v) \in \alpha$ --- значит из $u$ в $v$ есть дуга. Если $u = v$, то есть +$(u, u) \in \alpha$, то дуга называется петлёй. Говорят, что дуга $(u, v)$ +инцидентна вершинам $u$ и $v$, то есть своим концам. + +\begin{definition} + Говорят, что $\vec{G} = (U, \alpha)$ изоморфен $\vec{H} = (V, \beta)$, если + существует биекция $\varphi : U \to V$, которая сохраняет отношение смежности: + $(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \iff (\varphi(u_1), + \varphi(u_2)) \in \beta$. + \label{def:isomorphism} +\end{definition} + +\begin{definition} + Граф $G = (V, \alpha)$ называется неориентированным (или просто графом), если + отношение смежности $\alpha$ антирефлексивно и симметрично. Нет петель, дуги + встречаются парами. $(u, v), (v, u)$ --- ребро, обозначается $\set{u, v}$. + \label{def:graph} +\end{definition} + +\begin{definition} + Каждому орграфу $\vec{G} = (V, \alpha)$ естественным образом можно сопоставить + неориентированный граф, который называется его симметризацией. Это граф $(V, + (\alpha \cup \alpha^{-1}) \backslash \Delta)$, то есть дуги заменяются рёбрами + и исключаются петли. + \label{def:symmetrization} +\end{definition} + +\begin{definition} + Орграф $\vec{G} = (V, \alpha)$ называется направленным графом или диграфом, + если его отношение смежности антисимметрично (то есть в диграфе нет встречных + дуг, за исключением быть может петель). + \label{def:digraph} +\end{definition} + +\begin{definition} + Орграф $\vec{G} = (V, \alpha)$ называется полным, если его отношение смежности + универсально, то есть $\alpha = V \times V$. Если число вершин орграфа равно + $n$, то полный орграф обозначают $\vec{K_n}$. + \label{def:full-orgraph} +\end{definition} + +\begin{definition} + Неориентированный граф называется полным, если его отношение смежности $\alpha$ + имеет вид $(V \times V) \backslash \Delta$. Обозначается $K_n$. + \label{def:full-graph} +\end{definition} + +\begin{definition} + Орграф $\vec{G} = (V, \alpha)$ называется вполне несвязным (нуль-графом), если + его отношение смежности пусто. Обозначается $0_n$. + \label{def:null-graph} + \label{def:fully-disconnected} +\end{definition} + +Очевидно, что для каждого $n$ существует единственный граф $K_n$, $\vec{K_n}$, +$0_n$. + +\begin{definition} + Диграф $\vec{G}$ называется полным, если в каждой вершине имеется петля и + между двумя различными вершинами существует единственная дуга. Полный диграф + называется турниром. + \label{def:full-digraph} + \label{def:tournament} +\end{definition} \section{Степени вершин. Спецификация.} -\dots +\begin{definition} + Степенью исхода вершины $v$ называется число $d^+$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим началом. $d^+(v) = |\alpha(v)|$. + \label{def:out-degree} +\end{definition} -\section{Двудольные графы. Звезды.} +\begin{definition} + Степенью захода вершины $v$ называется число $d^-$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим концом. $d^-(v) = |\alpha^{-1}(v)|$. + \label{def:in-degree} +\end{definition} -\dots +\begin{definition} + Спецификацией орграфа называется вектор вида $\left(v_1^{(d_1^+, d_1^-)}, + \dots, v_n^{(d_n^+, d_n^-)}\right)$, где $d_i^+ = d^+(v_i)$, $d_i^- = + d^-(v_i)$. + \label{def:specification} +\end{definition} + +Для неориентированного графа степени исхода и захода равны. $d(v)$ называется +просто степенью вершины. $d(v)$ --- количество рёбер, которым принадлежит +вершина $v$. + +\section{Двудольные графы. Звёзды.} + +\begin{definition} + Граф называется двудольным, если его множество вершин может быть разбито на + два подмножества $V_1$ и $V_2$. $V = V_1 \cup V_2$, $V_1 \cap V_2 = \emptyset$ + и для любого ребра $\set{u, v}$ (или дуги $(u, v)$) $u$ и $v$ принадлежат + различным множествам. + \label{def:bipartite} +\end{definition} + +\begin{definition} + Двудольный граф, который содержит все возможные рёбра, отвечающие этому + условию, называется полным двудольным графом. И обозначается $K_{m,n}$, где + $n$ и $m$ --- количество вершин $n = |V_1|$, $m = |V_2|$. + \label{def:full-bipartite} +\end{definition} + +\begin{definition} + Полный двудольный граф вида называется звездным графом или звездой. + \label{def:star} +\end{definition} \section{Операции над графами: дополнение, объединение, соединение, декартово произведение, тензорное произведение, сильное произведение. n-мерная решетка, n-мерный тор.} -\dots +\begin{definition}[Операции над графами] + Пусть $G = (V, \alpha)$ --- некоторый неориентированный граф. + \begin{enumerate} + \item + Дополнение: $G = (V, \alpha) \to G' = (V, \overline\alpha \backslash + \Delta)$ + \item + Объединение: $G_1 = (V_1, \alpha_1)$, $G_2 = (V_2, \alpha_2)$, $G_1 \cup + G_2 = G = (V_1 \cup V_2, \alpha_1 \cup \alpha_2)$. + \item + Соединение: $G_1 = (V_1, \alpha_1)$ и $G_2 = (V_2, \alpha_2)$, $V_1 \cap + V_2 = \emptyset$, $G_1 + G_2 = (V_1 \cup V_2, \alpha_1 \cup \alpha_2 \cup + (V_1 \times V_2) \cup (V_2 \times V_1)$. + \item + Декартовым или прямым произведением двух графов $G_1 = (U, \alpha_1)$ и + $G_2 = (V, \alpha_2)$ называется граф $G_1 \cdot G_2$ с множеством вершин + $U \times V$, в котором вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны тогда и + только тогда, когда либо $u_1 = u_2$, а $v_1$ смежна с $v_2$, либо $v_1 = + v_2$, а $u_1$ смежна с $u_2$. + \item + Тензорным произведением двух графов $G_1 = (U, \alpha_1)$ и $G_2 = (V, + \alpha_2)$ называется граф $G_1 \times G_2$ с множеством вершин $U \times + V$, в котором различные вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны + тогда и только тогда, когда смежны $u_1$ и $u_2$ и $v_1$ с $v_2$: + $(u_1, u_2) \in \alpha_1 \land (v_1, v_2) \in \alpha_2$. + \item + Сильным произведением двух графов $G_1 = (U, \alpha_1)$ и $G_2 = (V, + \alpha_2)$ называется граф $G_1 \times G_2$ с множеством вершин $U \times + V$, в котором различные вершины $(u_1, v_1)$ и $(u_2, v_2)$ смежны тогда + и только тогда, когда выполняется одно из трёх условий: + \begin{enumerate} + \item + смежны $u_1$ с $u_2$ и $v_1$ с $v_2$ : $(u_1, u_2) \in \alpha_1 + \land (v_1, v_2) \in \alpha_2$ (как в тензорном); + \item + $u_1 = u_2$, а $v_1$ смежна с $v_2$: $(v_1, v_2) \in \alpha_2$ + (как в декартовом); + \item + $v_1 = v_2$, а $u_1$ смежна с $u_2$: $(u_1, u_2) \in \alpha_1$ + (как в декартовом); + \end{enumerate} + + Сильное произведение является объединением тензорного и декартова + произведений. + \end{enumerate} +\end{definition} + +\begin{definition} + $n$-мерной решёткой называется граф, являющийся декартовым произведением $n$ + цепей. + \label{def:mesh-graph} +\end{definition} + +\begin{definition} + $n$-мерным тором называется граф, являющийся декартовым произведением $n$ + циклов. + \label{def:torus-graph} +\end{definition} \section{Теорема Эйлера о степенях вершин. Однородные графы.} -\dots +Пусть $G = (V, \alpha)$ --- неориентированный граф. Вершина $v \in V$ называется +чётное или нечётное в зависимости от чётности её степени. + +\begin{theorem}[Эйлера, о степенях вершин] + Пусть $G = (V, \alpha)$ --- неориентированный граф с $n$ вершинами и $m$ + рёбрами. Тогда справедливы следующие три утверждения: + \begin{enumerate} + \item $\ds\sum_{i = 1}^n d(v_i) = 2m$; + \item Количество нечётных вершин чётно; + \item Сущестует по крайней мере две вершины с одинаковой степенью. + \end{enumerate} + \label{thm:euler} +\end{theorem} +\begin{proof} + \begin{enumerate} + \item + $\set{u, v}$ --- ребро в $G$. Это ребро один раз будет учитываться в + $d(u)$ и один раз в $d(v)$, таким образом, в сумме степеней вершин каждое + ребро будет учитываться дважды; + \item + $\ds 2m = \sum_{i = 1}^n d(v_i) = \sum d(v_i)_\text{чёт} + \sum + d(v_i)_\text{нечёт}$ + + Так как $2m$ --- чётное, то сумма чётных степеней и нечётных степеней + также должна быть чётной. Такое может быть только если сумма нечётных + степеней --- чётное число, то есть нечётных вершин чётное число. + \item + Вершина $v$ называется изолированной, если её степень равна 0, то есть она + не смежна ни с одной другой вершиной. Вершина $u$ называется полной, если + она смежна со всеми вершинами. + + Таким образом, степень произвольной вершины в графе $0 \leq d(v) \leq n - + 1$. Заметим, что одновременно в графе не может быть полной и изолированной + вершин. + \end{enumerate} +\end{proof} + +\begin{definition} + Однородные (регулярные) графы --- это графы, у которых степени всех вершин + одинаковые. Обозначаются через $R_{n,p}$, где $p$ --- порядок, $n$ --- число + вершин. + \label{def:regular-graph} +\end{definition} \section{Степенное множество. Теорема о степенном множестве.} -\dots +\begin{definition} + Степенным множеством графа называется множество чисел, являющихся степенями + его вершин. + \label{def:degree-set} +\end{definition} + +\begin{theorem}[О стененном множестве, Капур, Полимени, Уолл] + Для любого множества натуральных чисел $A = \set{d_1, \dots, d_k}$ ($d_1 < d_2 + < \dots < d_k$ для удобства) существует граф с $(d_k + 1)$ вершинами, для + которых $A$ является степенным множеством. + \label{thm:degree-set} +\end{theorem} +\begin{proof} + Доказательство по ММИ. + \begin{enumerate} + \item + $k = 1, A = \set{d}$. Граф $K_{d + 1}$. В полном $(d + 1)$ вершинном графе + каждая вершина соединена с остальными, таким образом число вершин $d + 1$, + их степень --- $d$. + \item + $k = 2, A = \set{d_1, d_2}, d_1 < d_2$. Рассмотрим граф $G = K_{d_1} + + 0_{d_2 - d_1 + 1}$. $d(u) = (d_1 - 1) + (d_2 - d_1 + 1) = d_2$, $d(v) = + d_1$. Количество вершин: $d_2 - d_1 + 1 + d_1 = d_2 + 1$. + \item + Пусть верно для $k$. Докажем для $k + 1$. + \begin{align*} + A &= \set{d_1, \dots, d_k, d_{k + 1}} \quad d_1 < \dots < d_k < d_{k + 1} \\ + A^* &= \set{d_2 - d_1, \dots, d_k - d_1} \implies |A^*| = k - 1 + \end{align*} + + Существует граф $G_0$ с $d_k - d_1 + 1$ вершинами, для которого $A^*$ --- + степенное множество + \begin{equation*} + G = K_{d_1} + (0_{d_{k + 1} - d_k} \cup G_0) + \end{equation*} + + Количество вершин в $G$: $d_1 + (d_{k + 1} - d_k) + (d_k - d_1 + 1) = + d_{k + 1} + 1$. + + \begin{align*} + d(u) &= (d_1 - 1) + (d_{k + 1} - d_k) + (d_k - d_1 + 1) = d_{k + 1} \\ + d(v) &= d_1 \\ + d(w) &= d_{G_0}(w) + d_1 + \end{align*} + + Степени вершин в $G_0$ --- это $d_2 - d_1, \dots, d_k - d_1$. + \end{enumerate} +\end{proof} \section{Вектор степеней. Критерии графичности вектора Гавела-Хакими. Процедура layoff. Критерий графичности Эрдеша-Галлаи.} -\dots +\begin{definition} + Вектор степеней графа --- вектор, составленный из степеней вершин графа $G$ в + порядке невозрастания + \label{def:degree-vector} +\end{definition} + +\begin{definition} + Говорят, что граф является реализацией своего вектора степеней или степенного + множества. +\end{definition} + +\begin{definition} + Если вектор является вектором степеней некоторого графа, то говорят, что он + графический. +\end{definition} + +Очевидно, что для графичности вектора необходимо, чтобы выполнялась теорема +Эйлера. Если в векторе $n$ элементов, то для графичности необходимо, чтобы +значения элементов были от $0$ до $n - 1$. + +Однако это условия не являются достаточными. Существуют эффективные критерии +графичности заданного вектора. + +\begin{theorem}[Критерий графичности вектора] + Пусть вектор $d = (d_1, \dots, d_n)$, $d_1 \geq d_2 \geq \dots \geq d_n$. + Производный вектор $d^i$ получается из $d$ удалением элемента $d_i$ и + уменьшением на единицу первых $d_i$ компонент в получившемся после удаления + векторе. + + Если $d^i$ при каком-либо $i = \overline{1, n}$ является графическим, то и + $d$ является графическим. + + Если $d$ является графическим, то существует производный вектор $d^i$ также + является графическим. + \label{thm:graphic-crit-vec} +\end{theorem} + +\begin{corollary} + Процедура layoff (layout): + \begin{enumerate} + \item + Берутся $n$ точек, которым присваиваются метки $d_1, \dots, d_n$. В + качестве ведущей выбирается вершина с наибольшим значением метки $d = + d_1$. + \item + Ведущая вершина соединяется ребром с $d$ вершинами, имеющими максимальное + значение меток (исключая саму ведущую). + \item + Ведущая вершина получает значение метки 0, а вершина, с которой она была + соединена, получает предудыщее значение минус 1. Если все вершины имеют + метку 0, то алгоритм завершён. + \item + Выбирается новая ведущая вершина с максимальным значением метки и + переходим на шаг 2. + \end{enumerate} + \label{cor:layoff} +\end{corollary} + +\begin{theorem}[Критерий графичности, Эрдёш, Галлаи] + Пусть дан вектор $d = (d_1, \dots, d_n)$, $d_1 \geq \dots \geq d_n$. Он + графичен $\iff \for k = \overline{1, n}$ выполняется $\ds\sum_{i = 1}^k + d_i \leq k(k - 1) + \sum_{i = k + 1}^n \min\set{k, d_i}$. + \label{thm:graphic-crit} + \label{thm:erdes-gallai} +\end{theorem} \section{Переключения ребер. Функциональные и контрфункциональные графы.} -\dots +\begin{definition} + Пусть $\set{a, b}$ и $\set{c, d}$ --- два ребра графа $G$. Переключением + этих рёбер в графе $G$ называется $G^* = G - \set{a, b} - \set{c, d} + + \set{a, d} + \set{b, c}$. + \label{def:switch} +\end{definition} + +\begin{theorem} + С помощью соответствующей цепочки переключений рёбер можно осуществить переход + от любой реализации вектора степеней к любой другой его реализации. +\end{theorem} + +\begin{definition} + Орграф $\vec{G} = (V, \alpha)$ называется функциональным, если степень исхода + любой его вершины равна 1, и контрфункциональным, если степень захода каждой + вершины равна 1. + \label{def:functional} + \label{def:contrafunctional} +\end{definition} + +Пусть на конечном множестве $V$ задана некоторая функция $f : V \to V$ со +значениями в этом множестве. Сопоставим этой функции орграф, рассматривая +функцию как отношение: если $f(u) = v$ --- это значит $(u, v) \in \alpha$. + +Очевидно, что полученный орграф будет функциональным. Верно и обратное: любому +функциональному орграфу можно сопоставить функцию в указанном смысле. \section{Изоморфизм и вложение. Немое изображение, абстрактные графы. Униграфы.} -\dots +\begin{definition} + Если вектор степеней имеет единственную реализацию, то говорят, что вектор + степеней определяет униграф. Заметим, что все графы с числом вершин меньше + пяти являются униграфами. + \label{def:unigraph} +\end{definition} + +\begin{definition} + Минимальным по числу вершин и рёбер неуниграфом является граф реализации + вектора степеней $(2, 2, 2, 1, 1)$. +\end{definition} + +\begin{definition} + $\vec{G} = (U, \alpha),\, \vec{H} = (V, \beta)$. Говорят, что $\vec{G}$ + изоморфен $\vec{H}$, если существует биекция $\varphi : U \to V$, которая + сохраняет отношение смежности: $(\forall u_1, u_2 \in U) ((u_1, u_2) \in + \alpha \iff (\varphi(u_1), \varphi(u_2)) \in \beta)$. + \label{def:isomorph} +\end{definition} + +\begin{definition} + $\vec{G} = (U, \alpha),\, \vec{H} = (V, \beta)$. Говорят, что $\vec{G}$ + вкладывается в $\vec{H}$, если существует инъекция $\varphi : U \to V$, для + которой выполняется: $(\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \implies + (\varphi(u_1), \varphi(u_2)) \in \beta)$. + \label{def:enclosure} +\end{definition} + +\begin{definition} + Метод канонических представителей: + \begin{enumerate} + \item Определить способ кодирования объектов; + \item Среди всех кодов изоморфных объектов выбирается канонический код; + \item + Порождаются все возможные уникальные структуры вместе с их кодами, + содержащие всех канонических представителей; + \item + Порождённая структура принимается, если её код канонический, в противном + случае --- исключается. + \end{enumerate} +\end{definition} \section{Автоморфизм. Подобные вершины, подобные ребра. Тождественные (ассиметричные графы). Симметричные графы.} -\dots +\begin{definition} + Изоморфизм графа на себя называется автоморфизмом. Очевидно, что любой граф + имеет как минимум один автоморфизм --- тождественное отображение. + \label{def:automorphism} +\end{definition} + +\begin{definition} + Графы, которые имеют только этот автоморфизм, называются асимметричными или + тождественными. Минимальный по числу вершин --- $0_1$, затем от 6 вершин. + \label{def:asymm-graph} + \label{def:identity-graph} +\end{definition} + +\begin{definition} + Вершины $u$ и $v$ называются подобными, если существует автоморфизм $\varphi : + \varphi(u) = v$. +\end{definition} + +\begin{definition} + Граф, все вершины которого подобны, называется вершинно-симметричным + (вершинно-транзитивным). +\end{definition} + +\begin{definition} + Два ребра $\set{u_1, v_1}$ и $\set{u_2, v_2}$ называются подобными, если + существует автоморфизм $\varphi$, такой, что образом первого ребра будет + второе ребро ($\varphi(\set{u_1, v_1}) = \set{u_2, v_2}$). Если $\varphi(u) = + u_2, \varphi(v_1) = v_2$, или $\varphi(u_1) = v_2, \varphi(v_2) = v_1$. +\end{definition} + +\begin{definition} + Граф, у которого все рёбра подобны, называется рёберно-симметрическим (или + рёберно-транзитивным). +\end{definition} + +\begin{definition} + Граф, являющийся вершинно-симметрическим и рёберно-симметрическим, называется + симметричным. А граф, обладающий только одним видом симметричности --- + полусимметричным. + \label{def:symm-graph} +\end{definition} + +$K_{m, n}$ --- всегда рёберно-симметрический, если $m \neq n$. $K_{m, m}$ --- +симметричный. \section{Часть графа и подграф. Максимальный подграф. Колода.} -\dots +\begin{definition} + Пусть $\vec{G} = (V, \alpha)$. $\vec{G}^* = V^*, \alpha^*) : V^* \subseteq V, + \alpha^* \subseteq \alpha \cap (V^* \times V^*)$ --- часть графа. То есть + часть графа состоит из некоторых его вершин и некоторых соединяющих их дуг + (рёбер). + \label{def:graph-part} +\end{definition} + +\begin{definition} + Пусть $\vec{G} = (V, \alpha)$. $\vec{G}^* = V^*, \alpha^*) : V^* \subseteq V, + \alpha^* = \alpha \cap (V^* \times V^*)$ --- подграф. То есть подграф состоит + из некоторых вершин графа и всех дуг (рёбер), соединяющих эти вершины в графе. + \label{def:subgraph} +\end{definition} + +\begin{definition} + Максимальным подграфом орграфа $\vec{G} = (V, \alpha)$ называется орграф, + получающийся удалением одной вершины и всех связанных с ней дуг. + \label{def:max-subgraph} +\end{definition} + +\begin{definition} + $P(\vec{G})$ (колода графа) --- список максимальных подграфов. + \label{def:pack} +\end{definition} \section{Реконструируемость графов. Гипотезы Келли-Улама и Харари.} -\dots +\begin{definition} + Граф $G$ называется реконструкцией графа $H$, если его колода совпадает с + колодой графа $H : P(G) = P(H)$. +\end{definition} + +\begin{definition} + Говорят, что граф $G = (V, \alpha)$ называется реконструируемым, если он + изоморфен всякой своей реконструкции. +\end{definition} + +\begin{definition}[Гипотеза Келли-Улама] + Гипотеза вершинной реконструируемости --- все неориентированные графы с числом + вершин больше двух являются вершинно-реконструируемыми. + + Известно, что гипотеза справедлива для многих классов графов: несвязные + графы, деревья, двудольные графы и некоторые другие. + + Для ориентированных графов существует бесконечные семейства пар + нереконструируемых орграфов. + \label{def:kelly-ulam-conjecture} +\end{definition} + +\begin{definition}[Гипотеза Харари] + Гипотеза рёберное реконструируемости --- всякий неориентированный граф с + числом рёбер больше трёх является рёберно-реконструируемым. + \label{def:harari-conjecture} +\end{definition} \section{Инварианты. Примеры полных инвариантов.} -\dots +\begin{definition} + Инвариантом графа называется один или более параметров графа, которые являются + одинаковыми для всех изоморфных графов. + \label{def:invariant} +\end{definition} + +\begin{definition} + Инвариант называется полным, если он различен для всех неизоморфных графов. +\end{definition} + +\textbf{TODO:} Добавить примеры полных инвариантов. \section{Отказоустойчивые реализации. Вершинные и реберные расширения. Минимальные, неприводимые, тривиальные, точные расширения.} -\dots +\begin{definition} + Под отказом элемента системы будем понимать удаление из графа системы + соответствующей вершины и всех её рёбер или дуг. + \label{def:fault-vert} +\end{definition} + +\begin{definition} + Под отказом связи между элементами будем понимать удаление из графа системы + соответствующего связи ребра или дуги. + \label{def:fault-edge} +\end{definition} + +\begin{definition} + Говорят, что система $\Sigma^*$ $k$-отказоустойчиво моделирует систему + $\Sigma$, если граф $G(\Sigma)$ вкладывается в любой граф, получающийся из + графа $G(\Sigma^*)$ удалением любых $k$ вершин и всех связанных с ними + рёбер (вершинная отказоустойчивость). + + Система $\Sigma^*$ --- $k$-отказоустойчивая реализация системы $\Sigma$. +\end{definition} + +\begin{definition} + Система $\Sigma^*$ называется оптимальной $k$-отказоустойчивой реализацией + (вершинной) системы $\Sigma$, если выполняются следующие условия: + \begin{enumerate} + \item Система $\Sigma^*$ является $k$-ОУР (вершинной) системы $\Sigma$; + \item Система $\Sigma^*$ имеет минимально возможное число вершин; + \item + Из всех систем, удовлетворяющих условиям 1 и 2 система $\Sigma^*$ имеет + минимально возможное число рёбер. + \end{enumerate} + \label{def:optimal-impl} +\end{definition} + +\begin{definition} + Граф $G^*$ является вершинным (рёберным) $k$-расширением графа $G$, если граф + $G$ вкладывается в любой граф, получающийся из $G^*$ удалением любых $k$ + вершин и связанных с ними рёбер (просто рёбер). +\end{definition} + +\begin{definition} + Граф $G^*$ называется $k$-неприводимым расширением (вершинным или рёберным) + графа $G$, есть $G^*$ является $k$-расширением, а никакая его часть + (собственная) не является $k$-расширением графа $G$. +\end{definition} + +\begin{definition} + Граф $G^*$ называется тривиальным расширением графа $G$, если $G^* = G + K_k$, + то есть тривиальное $k$-расширение получается из графа добавлением $k$ + вершин и связи их между собой и всеми вершинами графа $G$. + + Очевидно, что тривиальное расширение является и вершинным, и рёберным + $k$-расширением графа. +\end{definition} + +\begin{definition} + Граф $G^* = (V^*, \alpha^*)$ называется минимальным вершинным $k$-расширением + графа $G = (V, \alpha)$, если выполняются три условия: + \begin{enumerate} + \item $G^*$ является вершинным $k$-расширением графа $G$; + \item $G^*$ имеет на $k$ вершин больше, чем $G$: $|V^*| = |V| + k$; + \item + Среди всех графов, удовлетворяющих условиям 1 и 2, $G^*$ имеет минимально + возможное число рёбер. + \end{enumerate} + + Очевидно, что любой граф имеет минимальное вершинное $k$-расширение. +\end{definition} + +\begin{definition} + Граф $G^* = (V^*, \alpha^*)$ называется минимальным рёберным $k$-расширением + графа $G = (V, \alpha)$, если выполняются три условия: + \begin{enumerate} + \item $G^*$ является рёберным $k$-расширением графа $G$; + \item $G^*$ имеет столько же вершин, сколько и $G$: $|V^*| = |V|$; + \item + Среди всех графов, удовлетворяющих условиям 1 и 2, $G^*$ имеет минимально + возможное число рёбер. + \end{enumerate} + + Не всякий граф имеет минимальное рёберное $k$-расширение. +\end{definition} \section{Минимальные вершинные расширения, основные свойства. Леммы. Минимальные -вершинные 1-расширения цепей. Точные расширения. Минимальные вершинные +вершинные 1"=расширения цепей. Точные расширения. Минимальные вершинные 1-расширения циклов.} -\dots +\begin{lemma} + Если в графе $G$ минимальная из степеней вершин $d > 0$, то МВ-kР не содержит + вершин степени меньше $d + k$. +\end{lemma} + +\begin{lemma} + Если в графе $G$ максимальная из степеней вершин есть $d$, и таких вершин + $m$, то МВ-kР содержит не менее, чем $(m + k)$ вершин степени не ниже $d$. +\end{lemma} + +\begin{lemma} + Если в графе $G$ максимальная из степеней вершин есть $d$, то МВ-kР содержит + не менее, чем $kd$ дополнительных рёбер. +\end{lemma} + +\begin{lemma} + \textbf{TODO:} ЧТО?? + + $G = (V, \alpha)$, $d > 0$ --- минимальная из степеней вершин. + + $G^* = (V^*, \alpha^*)$ и в $G^*$ $d(v) < d + k$. +\end{lemma} + +\begin{lemma} + Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин, смежных с $v$. + (Если $d(v) < k$, то удаление всех вершин, смежных с $v$, и $k - d(v)$ + произвольных вершин, отличных от $v$). + + В получившемся графе степень вершины $v < d$. Очевидно, что $G$ нельзя будет + вложить в получившийся граф, это противоречит предположению $\implies + d(v) < d + k$. +\end{lemma} + +\begin{lemma} + \textbf{TODO:} ЧТО?? №2 + + $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин. + + $G^* = (V^*, \alpha^*)$ и в $G^*$ менее чем $m + k$ вершин имеют степень $\geq + d$. +\end{lemma} + +\begin{lemma} + Рассмотрим граф, получающийся из $G^*$ удалением $k$ вершин наибольшей степени. + В получившемся графе меньше, чем $m$ вершин будут иметь степень не меньшую + $d$. И, очевидно, что граф $G$ нельзя будет вложить в получившийся граф. +\end{lemma} + +\begin{lemma} + $G = (V, \alpha)$, $d > 0$ --- максимальная из степеней вершин. + + В $G^*$ по крайней мере на $k$ вершин степени $\geq d$ больше, чем в графе + $G$. + + Рассмотрим граф, получающийся удалением $k$ вершин максимальной степени. + Исходный граф по условию вкладывается в получившийся граф, а сам граф + отличается от МВ-kР не менее, чем на $dk$ рёбер. +\end{lemma} + +\begin{definition} + Граф $G = (V, \alpha)$ называется $n$-вершинной цепью и обозначается $P_n$, + или его вершины $V = \set{v_1, \dots, v_n}$ могут быть занумерованы таким + способом, чтобы $\alpha$ имело вид: + \begin{equation*} + \alpha = \set{\set{v_i, v_{i + 1}}, i = \overline{1, n - 1}} + \end{equation*} +\end{definition} + +\begin{definition} + Вершины $u$ и $v$ называются подобными, если существует автоморфизм $\varphi : + \varphi(u) = v$. +\end{definition} + +\begin{definition} + Граф, все вершины которого подобны, называется вершинно"=симметрическим + (вершинно"=транзитивным). +\end{definition} + +\begin{theorem}[О МВ-1В цепи, Хейз] + Единственным с точностью до изоморфизма МВ-1Р цепи $P_n$ является цикл + $C_{n + 1}$. +\end{theorem} +\begin{proof} + По лемме ??? для любого МВ-1Р цепи не может содержать вершин степени меньше + двух. Очевидно, что $C_{n + 1}$ является В-1Р цепи $P_n$. + + С другой стороны, цикл $C_{n + 1}$ имеет все вершины степени 2, то есть имеет + минимально возможное число рёбер $\implies C_{n + 1}$ --- МВ-1Р цепи $P_n$. + + Докажем, что других не существует. + + Предположим, $G^* = (V^*, \alpha^*)$ также является МВ-1Р цепи $P_n$. Тогда + $G^*$ также будет отличаться от цепи $P_n$ на два дополнительных ребра, причём + степени всех вершин должны быть равны двум. Очевидно, что добавить в этом + случае два ребра можно единственно возможным способом, то есть $G^* \cong + C_{n + 1}$. +\end{proof} + +\begin{definition} + Точным вершинным $k$-расширением графа $G = (V, \alpha)$ называется граф + $G^* = (V^*, \alpha^*)$: любой граф, получающийся из $G^*$ удалением + произвольных $k$ вершин вместе с рёбрами, изоморфен $G$. + + Цикл $C_{n + 1}$ является ТВ-1Р цепи $P_n$. +\end{definition} + +\textbf{TODO:} Лекция 3, страница 67 --- Лекция 5 \section{Минимальные реберные расширения, основные свойства. Минимальные реберные 1-расширения цепей и циклов.} @@ -271,6 +946,95 @@ layoff. Критерий графичности Эрдеша-Галлаи.} \chapter{Основные типы неориентированных графов} +\section{Пути в графе. Цепи и циклы в графе. Эксцентриситет, радиус и диаметр. +Центр и окраина. Связность.} + +\begin{definition} + Путём называется последовательность рёбер, в которой каждые два соседних ребра + имеют общую вершину, и никакое ребро не встречается более одного раза. При этом + считается, что оба конца каждого ребра, кроме первого и последнего, являются + концами соседних с ним рёбер. + \label{def:path} +\end{definition} + +\begin{definition} + Путь называется циклическим, если его первая и последняя вершины совпадают. + \label{def:cyclic-path} +\end{definition} + +\begin{definition} + Путь, любая вершина которого принадлежит не более, чем двум его рёбрам, + называется простым. + \label{def:simple-path} +\end{definition} + +\begin{definition} + Простой циклический путь называется циклом. Простой путь, не являющийся + циклом, называется цепью. + \label{def:chain} +\end{definition} + +\section{Теорема о связности двух нечетных вершин. Достаточное условие +связности.} + +\dots + +\section{Точки сочленения, мосты.} + +\dots + +\section{Деревья. Лист и корень. Характеристическая теорема о деревьях. Теорема +о центре дерева.} + +\dots + +\section{Изоморфизм деревьев: алгоритм Эдмондса, алгоритм WAV. Кодирование +деревьев.} + +\dots + +\section{Уровневые коды. Канонические коды. Код Прюфера.} + +\dots + +\section{Сеть. Остовное (покрывающее) дерево. Алгоритмы Прима и Краскала.} + +\dots + +\section{Укладки графов. Укладки на сфере и в пространстве. Планарные графы. +Планарность деревьев.} + +\dots + +\section{Грань. Теорема Эйлера и её обобщения. Триангуляция, максимально плоский +граф. Следствия из теоремы: если всякая грань k-элементный цикл, число ребер в +триангуляции, необходимое условие планарности, степень вершины в триангуляции.} + +\dots + +\section{Графы типа 1 и типа 2. Стягивание ребра, минор. Критерии планарности +(Понтрягин-Куратовский, Вагнер). Прямолинейное изображение. Род поверхности, род +графа, число скрещиваний.} + +\dots + +\section{Эйлеровы графы. Критерий эйлеровости графа. Критерий существования +эйлерова пути.} + +\dots + +\section{Гамильтоновы графы. Доказательство с нулевым разглашением гамильтонова +цикла. Теорема Оре. Теорема Дирака (следствие т. Оре). Достаточное условие Поша. +Достаточное условие Хватала.} + +\dots + +\section{Замыкание. Критерий и достаточное условие Бонди-Хватала.} + +\dots + + + \chapter{Пути в орграфах} diff --git a/graphs-exam/style.tex b/graphs-exam/style.tex index cb21fbf..74aaa6f 100644 --- a/graphs-exam/style.tex +++ b/graphs-exam/style.tex @@ -4,6 +4,7 @@ \colorlet{definitioncolor}{DarkGreen} \colorlet{theoremcolor}{DarkBlue} +\colorlet{lemmacolor}{DarkRed} \renewenvironment{leftbar}[1][]{% \def\FrameCommand{{\color{#1}\vrule width 2pt} \hspace{7pt}}% @@ -17,19 +18,33 @@ \renewenvironment{theorembar} {\begin{leftbar}[theoremcolor]} {\end{leftbar}} +\renewenvironment{lemmabar} + {\begin{leftbar}[lemmacolor]} + {\end{leftbar}} \declaretheoremstyle[ - headfont=\sffamily\bfseries,% - notefont=\sffamily\bfseries,% + headfont=\bfseries,% + notefont=\bfseries,% notebraces={(}{)},% headpunct=,% - bodyfont=\sffamily\itshape,% + bodyfont=,% headformat=\color{definitioncolor}\NAME~\NUMBER~\NOTE\hfill\smallskip\linebreak,% preheadhook=\begin{definitionbar},% postfoothook=\end{definitionbar},% ]{customDefinition} \declaretheorem[name={Определение}, style=customDefinition]{definition} +\declaretheoremstyle[ + headfont=\bfseries,% + notefont=\bfseries,% + notebraces={(}{)},% + headpunct=,% + headformat=\color{lemmacolor}\NAME~\NUMBER~\NOTE\hfill\smallskip\linebreak,% + preheadhook=\begin{lemmabar},% + postfoothook=\end{lemmabar},% +]{customLemma} +\declaretheorem[name={Лемма}, style=customLemma]{lemma} + \declaretheoremstyle[ headfont=\bfseries,% notefont=\bfseries,% @@ -54,7 +69,17 @@ }{\end{proofthm}} % TODO: Изменить стиль замечаний -\declaretheorem[name={Замечание}, style=definition, numberwithin=theorem]{remark} +\declaretheorem[ + name={Замечание}, + style=customDefinition, + numberwithin=theorem +]{remark} + +\declaretheorem[ + name={Следствие}, + style=customDefinition, + numberwithin=theorem +]{corollary} \setlength{\parindent}{0pt} \setlength{\parskip}{0.5\baselineskip} -- cgit v1.2.3