#set text(lang: "ru")

= Теория графов
== Определения
$E_(G)(X, Y)$ множество, состоящее из таких ребер $e in E(G)$, 
что $e = x y, x in X, y in Y$

$N_(G)(v)$ – окрестность вершины $v$ (множество всех вершин смежных с $v$)

$N'_(G)(U)$ – множество всех вершин графа смежных со всеми вершинами множества U

$N_(G)(U) = N'_(G)(U) \\ U $

$d_(G)(x)$ – количество ребер графа инцидентных вершине x

$delta(G)$ – минимальная степень вершины в графе G

$Delta(G)$ – максимальная степень вершины в графе G

Граф G называют регулярным, если степени всех его вершин одинаковы

=== Подграф
Подграф H графа G называется остовным, если $V(H) = V(G)$
$U subset V(G)$ через $G(U)$ мы обозначим индуцированные подграф на множестве вершин $U$. Это означает, что $V(G(U)) = U$, а $E(G(U))$ состоит из всех ребер множества E(G), обо конца которых лежат в $U$.

Индуцированные подграф - это другой граф, который образуется из подмножества вершин исходного графа и всех ребер, соединяющих пары вершин в этом множестве.

=== Маршрут и путь
Маршрут – последовательность вершин и ребер графа G, где $e_i = a_i a_(i + 1)$

Путь - это маршрут, не проходящий ни по какому ребру дважды. Более того, путь - подграф графа G, состоящий из вершин и ребер, по которым этот путь проходит

Путь называется простым, если все его вершины различны.

Внутренность $"Int"(P)$ - это множество всех его вершин, отличных от начала и конца этого пути.

Расстояние между вершинами x и y графа G называется наименьшая длина xy-пути. Обозначение $"dist"_(G)(x, y)$.

=== Цикл
Цикл - это последовательность вершин и различных ребер графа G, где $e_i = a_i a_(i + 1)$ для всех $i in [1..n]$ (мы считаем, что $a_(n + i) = a_i$).

Цикл называется простым, если все его вершины различны.

Длина цикл - количество его ребер.

Пусть C - простой цикл, а x, y - две его несоседние вершины.
- Вершины x и y делят цикл C на два пути с концами x и y, которые мы будем называть дугами.
- Если $"xy" in E(G)$, назовем ребро xy хордой или (что, то же самое) диагональю цикла C.

Индуцированный цикл графа G - это простой цикл, не имеющий диагоналей.

=== Компоненты связанности
Вершины a и b графа G называют связанными, если в графе существует путь между ними.

Граф называется связным, если любые две его вершины связанны.

Компоненты связанности графа G - максимальные (по включению) связанные множества вершин. Через $c(G)$ обозначим их количество.

Будем называть компонентами графа G подграфы, индуцированные на его компонентах связанности.
#align(center)[
  #figure(
    image("images/Пример графа с компонентами связнности.png", width: 20%),
    caption: [Граф G, $c(G) = 3$]
  )
]

=== Дерево и лес
Дерево - это связанный граф без циклов.

Лес - это граф без циклов. Все компоненты леса - деревья.

Вершина x графа G, имеющая степень 1, называется висячей вершиной или листом.

#pagebreak()

== Теоремы и леммы
=== Общие
$ sum_(v in V(G))d_(G)(v) = 2e(G) $

=== Циклы
Для любого циклы $Z$ существует такой простой цикл $Z'$, что $V(Z') subset V(Z)$ и $E(Z') subset E(Z)$

Если в графе есть нечетный цикл, то есть и простой нечетный цикл.

Из xy-пути можно выделить простой xy-путь.

=== Дерево
В дереве с n вершинами n - 1 ребро.

У любого связанного графа существует основное дерево.

Граф G является деревом, если и только если для любых двух вершин существует единственный простой путь, соединяющий их.