path: root/th-graph/th-graph.org

#+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}