diff options
Diffstat (limited to 'th-graph/th-graph.org')
| -rw-r--r-- | th-graph/th-graph.org | 327 |
1 files changed, 327 insertions, 0 deletions
diff --git a/th-graph/th-graph.org b/th-graph/th-graph.org new file mode 100644 index 0000000..f33e602 --- /dev/null +++ b/th-graph/th-graph.org @@ -0,0 +1,327 @@ +#+TITLE: Теория графов +#+AUTHOR: Андрей Гущин +#+LATEX_CLASS: Lecture +#+LATEX_HEADER: \usepackage{../preamble} + +# Лекция 1 (08.09.22) +* Лекция + +Опр. Пусть $A, B$ - два непустых множества. Декартовым произведением $A$ и $B$ +называется множество $A \times B = \{ (a, b) : a \in A, \, b \in B \}$ + +Пустое отношение --- это отношение, не содержащее ни одной пары. + +Универсальное отношение содержит все возможные пары + +Опр. Двоичной булевой алгеброй называется множество $B = \{ 0, 1 \} $, на котором +определены следующие операции: +- Булево умножение +- Булево сложение +- Булево отрицание + +Пусть множества $A = \{ a_1, \dots, a_m \}, B = \{ b_1, \dots, b_n \}$. +... + +\( a = b + c \) + + +** Бинарные отношения +1. Отношение $\rho \subseteq A \times A$ называется рефлексивным $(\forall x \in A) ((x, x) \in \rho)$. + В матрице отношения элементы шлавной диагонали = 1; +2. +3. +4. Отношение $\rho \subseteq A \times A$ антисимметрично тогда и только тогда, когда + $(\forall x, y \in A) ((x, y) \in \rho \land (y, x) \in \rho) \implies (x = y)$. В + Матрице отношения элементы, симметричные единицам относительной главной диагонали, равны 0. + (Исключение - сама главная диагональ). +5. Отношение $\rho \subseteq A \times A$ транзитивно тогда и только тогда, когда $(\forall x, y, z \in A) + ((x, y) \in \rho \land (y, z) \in \rho \implies (x, z) \in \rho). + + +Опр. Отношением эквивалентности на на $A$ называется отношение $\varepsilon \subseteq A \times A$, +которое одновременно рефлексивно, симметрично и транзитивно. + +\begin{definition} +Отношение $\omega \subseteq A \times A$ ... порядка ... если ... +\end{definition} + +** Типы графов. Операции над графами. + +\begin{definition} +Опр. Орграфом $\vec{G} = (V, \alpha)$, где $V$ --- конечное непустое множество, +а $\alpha \subseteq V \times V$. Элементы множества $V$ называются вершинами, а +элементы множества $\alpha$ --- дугами (!!!). $V$ --- множество вершин, $\alpha$ --- +отношение смежности. + +- $(u, v) \in \alpha$ --- значит, из $u$ в $v$ есть дуга. +- Если $u = v$, то есть $(u, u) \in \alpha$, то дуга называется петлёй. +- Говорят, что дуга $(u, v)$ инцидентна вершинам $u$ и $v$, то есть + своим концам. +\end{definition} + +$A = M(\alpha)$ --- матрица смежности. Если $\alpha_{ij} = 1$, то есть дуга из +$i$-ой вершины в $j$-ую. + +\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)$. +\end{definition} + +** Неориентированные графы + +Граф $G = (V, \alpha)$ называется неориентированным (или просто графом), если отношение +смежности $\alpha$ антирефлексивно и симметрично. +- Нет петель, дуги встречаются парами +- $(u, v)$, $(v, y)$ --- ребро обозначается $\{ u, v \}$. + +** Симметризация + +Опр. Каждому орграфу $\vec{G} = (V, \alpha)$ естественным образом можно + сопоставить неориентированный граф, который называется его + симметризацией. Это граф $(V, (\alpha \cup \alpha^{-1}) \backslash + \Delta)$, то есть дуги заменяются рёбрами и исключаются петли. + +** Диграфы + +Опр. Ограф $\vec{G} = (V, \alpha)$ называется направленным графом или + /диграфом/, если его отношение смежности антисимметрично (то есть в диграфу + нет встречных дуг, за исключением быть может петель). + +Опр. Орграф $\vec{G} = (V, \alpha)$ называется полным, если его отношение + смежности универсально, то есть $\alpha = V \times V$. Обозначается + $\vec{K_n}$. + +Опр. Неориентированный граф называется полным, если его отношение смежности + $\alpha$ имеет вид $(V \times V) \backslash \Delta$. Обозначается $K_n$ + +** Вполне несвязные графы + +Опр. Орграф называется вполне несвязным (нуль-графом), если его отношение + смежности пусто. Обозначается $O_n$. Очевидно, что для каждого $n$ + существует единственный граф $K_n$, $\vec{K_n}$, $O_n$ + +Опр. Диграф называется полным, если в каждой вершине имеется петля и между двумя + различными вершинами существует, и при том единственная, дуга. Полный + диграф называется турниром. + +** Степени вершин + +Пусть $\vec{G} = (V, \alpha)$ --- орграф, $v$ --- некоторая его вершина. + +Опр. Степенью исхода вершины $v$ называется число $d^+$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим началом. $d^+(v) := |\alpha(v)|$. + +Опр. Степенью захода вершины $v$ называется число $d^-$, равное количеству дуг в + $\vec{G}$, имеющих $v$ своим концом. $d^+(v) := |\alpha^{-1}(v)|$. + +** Спецификация орграфа + +Опр. Спецификацией орграфа называется вектор вида $(v_1^{(d_1^+, d_1^-)}, \dots, + v_n^{(d_n^+, d_n^-)}$, где $d_i^+ = d^+(v_i), d_i^- = d^-(v_i)$. + +Опр. Для неориентированного графа степени исхода и захода равны: $d^+(v) = + d^-(v) = d(v)$. Называется $d(v)$ просто степенью вершины. + + +** Двудольные графы + +Опр. Граф называется /двудольным/, если его множество вершин может быть разбито + на два подмножества $V_1$ и $V_2$. + - $V = V_1 \cup V_2$ + - $V_1 \cap V_2 = \empty$ + - для любого ребра $\{ u, v \}$, $u$ и $v$ принадлежат различным множествам. + +Опр. Двудольный граф, который содержит все возможные рёбра, отвечающие этому условию, + называется полным двудольным графом. И обозначается $K_{m, n}$, где $n$ и $m$ --- + количество вершин $n = |V_1|, m = |V_2|$. + +Опр. Двудольный граф $K_{1, n}$ называется звёздным графом. + +Опр. $K_{3, 3}$ граф Куратовского. + +# Лекция 3 (22.09.22) +* Изоморфизм + +\begin{definition} +$\ved{G} = (U, \alpha), \vec{H} = (V, \beta)$. Орграф G изоморфен орграфу 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)$. +\end{definition} + +\begin{definition} + Граф G вкладывается в H если существует инъекция $\varphi : + (\forall u_1, u_2 \in U) ((u_1, u_2) \in \alpha \implies (\varphi(u_1), \varphi(u_2)) \in \beta)$. +\end{definition} + +\begin{definition} + Немым изображением графа называют его изображение, в котором пропущены имена меток. +\end{definition} + +Два графа изоморфны тогда и только тогда, когда они допускают +одинаковое немое изображение. + +Отношение измоморфизма это отношение эквивалентности и классы этого +отношения называются абстрактными графами. + +\begin{definition} + Изоморфизм графа на себя называется автоморфизмом. +\end{definition} + +\begin{definition} + Графы которые имеют только тождественный автоморфизм называются + ассиметричными или тождественными. +\end{definition} + +\begin{definition} + Две вершины $u$ и $v$ называются подобными, если существует + автоморфизм, в котором вершина $u$ переходит в вершину $v$. Граф, в + котором все вершины подобны называется вершинно-симметрическим или + вершинно-транзитивным. +\end{definition} + +Если в графе все вершины подобны, то этот граф регулярен. + +\begin{definition} + Два ребра называются подобными, если существует автоморфизм + $\varphi$, такой, что образом одного ребра является второе ребро. +\end{definition} + +\begin{definition} + Граф у которого все рёбра подобны называется рёберно-симметрическим + или рёберно-транзитивным. +\end{definition} + +\begin{definition} + Граф, который является вершинно-симметрическим и + рёберно-симметрическим называется симметричным. +\end{definition} + +** Части графа. Отказоустойчивость и расширение. + +\begin{definition} + $\vec{G} = (V, \alpha)$. Его частью называется граф $\vec{G^*} = + (V^*, \alpha^*)$, где $V^* \subseteq V, \alpha^* \subseteq \alpha + \cap (V^* \times V^*)$. Часть графа состоит из некоторых вершин и + некоторых соединяющих их дуг или рёбер. +\end{definition} + +\begin{definition} + Подграфом ографа $\vec{G}$ называется орграф $\vec{G^*} = (V^*, + \alpha^*)$, где $V^* \subseteq V, \alpha^* = \alpha \cap (V^* \times + V^*)$ +\end{definition} + +\begin{definition} + Максимальным подграфом орграфа $\vec{G}$ называется орграф, + получающийся удалением одной вершины и всех связанных с ней дуг. +\end{definition} + +\begin{definition} + Список максимальных подграфов называют колодой $P(\vec{G})$. +\end{definition} + +\begin{definition} + Граф $G$ называется реконструкцией графа $H$ если колода $P(G) = P(H)$. +\end{definition} + +\begin{definition} + Граф $G$ является реконструируемым, если он изоморфен всякой своей реконструкции. +\end{definition} + +\begin{definition} + Гипотеза Келли-Улама (Гипотеза о вершинной реконструирумости). Все + неориентированные графы с числом вершин больше двух являются + вершинно-реконструируемыми. Гипотеза справедлива для несвязных + графов, деревьев, двудольных графов. +\end{definition} + +\begin{definition} + Всякий неориентриваонный граф с числом рёбер больше трёх является + рёберно-реконструируемым. +\end{definition} + +\begin{definition} + Инвариант графа --- это один или более параметров, которые являются + одинаковыми для всех изоморфных графов. Инвариант называется полным, если + он различен для любых неизоморфных графов. +\end{definition} + +# Лекция (06.10.22) + +** Расширения циклов +..... + +\begin{theorem}[МВ-1Р, Абросимов, 2000] + Графы, построенные по предлагаемым схемам являются МВ-1Р цикла с + соответствующим числом вершин и при $n > 5$ строят графы, не + изоморфные соответствующим реализациям из теоремы 2. + + /Рисунки схем/ +\end{theorem} + +* Основные типы неориентированных графов + +** Пути в графе. Связные графы. + +\begin{definition} + Путём называется последовательность рёбер, в которой каждые два + соседних ребра имеют общую вершину, и никакое ребро не встерчаеся + более одного раза. При этом считается, что оба конца каждого ребра, + кроме первого и последнего, являются концами соседних рёбер. +\end{definition} + +\begin{definition} + Путь называется циклическим, если его первая и последняя вершины совпадают. +\end{definition} + +\begin{definition} + Путь, любая вершина которого принадлежит не более чем двум рёбрам, называется простым. +\end{definition} + +\begin{definition} + Простой циклический путь называется циклом. Простой путь, не + являющийся циклом, называется цепью. +\end{definition} + +\begin{definition} + Длиной пути называется количество входящих в его состав рёбер. +\end{definition} + +Очевидно, что в $n$-вершинном графе цепь не может иметь длину больше, чем $n - 1$, а +цикл не может иметь длину больше, чем $n$. + +\begin{definition} + Наибольшее из расстояний от вершины до всех оставшихся вершин называется + эксцентриситетом вершины. + + $E(u)$ --- эксцентреситет, $E(u) = \max d(u, v), \, v \in V$ +\end{definition} + +** Связные графы + +\begin{definition} + Классы отношения связности графа называются его связными + компонентами или просто компонентами. +\end{definition} + +\begin{definition} + Граф с универсальным отношением связности называется связным графом. + Граф с тождественным отношением связности называется вполне + несвязным. +\end{definition} + +\begin{theorem} + Если вершины $u$ и $v$ являются единственными нечётными вершинами графа + $G$, то они связаны в этом графе. +\end{theorem} +\begin{proof} + Предположим противное, то есть $u$ и $v$ не связаны в + графе $G = (V, \alpha)$. Обозначим через $G_1$ и $G_2$ + компоненты связности графа $G$, содержащие соответственно + вершины $u$ и $v$. + + В графе $G_1$ вершина $u$ является единственной нечётной вершиной, + что противоречит теореме Эйлера (количество нечётных вершин должно + быт чётно). +\end{proof} |