Добавлены org файлы по Теории чисел, Теории графов и Построению защищённых сетей

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}