graph theory

Граф (G)

Множество вершин (V) и ребер (E), соединяющих эти вершины.

Орграф (Ориентированный граф)

Граф, все ребра которого имеют направление (называются дугами).

Простой граф

Граф без петель и кратных (параллельных) ребер.

Мультиграф

Граф, в котором разрешены кратные ребра (несколько ребер между двумя вершинами).

Петля

Ребро, концы которого совпадают (соединяет вершину саму с собой).

Степень вершины (deg v)

Количество ребер, инцидентных данной вершине.

Лемма о рукопожатиях

Сумма степеней всех вершин графа равна удвоенному количеству ребер (2|E|).

Изоморфизм графов

Взаимно однозначное соответствие между вершинами двух графов, при котором сохраняется смежность.

Индуцированный подграф

Подграф, образованный выбранным множеством вершин и ВСЕМИ ребрами исходного графа, соединяющими эти вершины.

Остовный подграф

Подграф, который содержит абсолютно все вершины исходного графа.

Простой путь

Путь, в котором ни одна вершина не повторяется (кроме, возможно, начала и конца в цикле).

Компонента связности

Максимальный по включению связный подграф (кусок графа, отделенный от остальных).

Слабо связный орграф

Орграф, который станет связным, если стереть стрелки (направления) со всех его ребер.

Сильно связный орграф

Орграф, в котором из любой вершины можно добраться по стрелкам в любую другую.

Лес

Граф без простых циклов (состоит из непересекающихся деревьев).

Дерево (классическое определение)

Связный граф, не содержащий циклов.

Дерево (эквивалентное определение через ребра)

Граф, который связен и имеет ровно V - 1 ребро.

Дерево (эквивалентное определение через отсутствие циклов)

Граф, который не имеет циклов и имеет ровно V - 1 ребро.

Дерево (определение через пути)

Граф, в котором любые две вершины соединены ровно одним простым путем.

Дерево (минимально связный)

Связный граф, в котором удаление любого ребра делает его несвязным.

Дерево (максимально ациклический)

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

Клика (Полный подграф K_r)

Множество вершин, в котором каждые две вершины соединены ребром.

Теорема Турана

Максимальное число ребер в графе без полного подграфа K_{r+1} не превышает числа ребер в графе Турана.

Граф Турана T(n,r)

Полный r-дольный граф с максимально равномерным распределением вершин по долям.

Теорема Мантеля (частный случай Турана)

Максимальное число ребер в простом графе без треугольников не превышает V^2 / 4.

Число Рамсея r(n,m)

Минимальное число вершин, гарантирующее наличие в любом графе либо клики размера n, либо независимого множества размера m.

Верхняя оценка числа Рамсея

r(n,m) <= C_{n+m-2}^{n-1} (биномиальный коэффициент).

Теорема Эрдёша (нижняя оценка числа Рамсея)

r(k,k) >= 2^{k/2} (доказывается вероятностным методом).

Независимое множество вершин

Набор вершин графа, в котором никакие две вершины не соединены ребром.

Число независимости графа (α)

Размер самого большого (максимального) независимого множества вершин в графе.

Алгоритм Брона-Кербоша

Рекурсивный алгоритм (с возвратом) для поиска всех максимальных независимых множеств (или клик) в графе.

Поиск в ширину (BFS)

Алгоритм обхода графа "по слоям", используется для поиска кратчайшего пути в невзвешенном графе.

Поиск в глубину (DFS)

Алгоритм обхода графа, идущий "вглубь" по ветви до упора, а затем возвращающийся назад.

Нормальность остовного дерева DFS

Для любого ребра исходного графа одна из его вершин обязательно является предком другой в построенном дереве DFS.

Формула Кэли

Количество различных помеченных деревьев на n вершинах равно n^(n-2).

Код Прюфера

Способ однозначно закодировать любое помеченное дерево на n вершинах последовательностью из n-2 чисел.

Алгоритм кодирования Прюфера

На каждом шаге удаляем лист с минимальной меткой и записываем в код номер его единственного соседа.

Рекурсивный подсчет остовных деревьев t(G)

t(G) = t(G - e) + t(G / e), где (G-e) — удаление ребра, а (G/e) — его стягивание.

Матрица смежности

Квадратная матрица, где элемент a_ij = 1, если вершины i и j соединены ребром, и 0 иначе.

Матрица инцидентности

Матрица (Вершины × Ребра). В неориентированном простом графе в каждом столбце стоят ровно две единицы.

Матрица Кирхгофа (Лапласиан, L)

L = D - A, где D — диагональная матрица степеней вершин, A — матрица смежности графа.

Матричная теорема о деревьях

Количество остовных деревьев равно определителю матрицы Кирхгофа, из которой вычеркнули любую одну строку и столбец.

Подсчет деревьев через собственные числа

t(G) = (λ_2 * λ_3 * … * λ_n) / n, где λ_i — ненулевые собственные числа матрицы Кирхгофа.

Теорема Татта для орграфов

Количество ориентированных остовных деревьев, направленных к корню v, равно определителю минора матрицы Кирхгофа L_{-}^{(v)}.

Разделяющее множество вершин

Набор вершин, удаление которого делает граф несвязным (или оставляет только 1 вершину).

Вершинная связность (κ)

Минимальный размер вершинного разделяющего множества.

Рёберная связность (λ)

Минимальное количество ребер, удаление которых делает граф несвязным.

Соотношение связностей (Теорема Уитни)

κ(G) <= λ(G) <= δ(G), где δ(G) — минимальная степень вершины в графе.

Теорема Хартранда-Харари

Для любых натуральных чисел k <= l <= d существует граф, у которого κ=k, λ=l и δ=d.

Двусвязный граф

Связный граф с вершинной связностью κ >= 2 (нет точек сочленения).

Эквивалентное определение двусвязности (через ребра)

Граф двусвязен, если любые два его ребра лежат на одном простом цикле.

Похожесть ребер

Два ребра похожи, если они совпадают или лежат на одном простом цикле (это отношение эквивалентности).

Разложение на ручки (Ear decomposition)

Граф двусвязен тогда и только тогда, когда его можно собрать, начав с цикла и приклеивая "ручки" (пути).

Реберно двусвязный граф

Граф без мостов (λ >= 2). В разложении на ручки допускаются замкнутые ручки (циклы).

Точка сочленения

Вершина, удаление которой увеличивает количество компонент связности графа.

Мост

Ребро, удаление которого увеличивает количество компонент связности графа.

Алгоритм Хопкрофта-Тарьяна

Эффективный алгоритм на основе DFS для поиска всех точек сочленения за время O(V+E).

Теорема Менгера (вершинная)

Минимальное число удаляемых вершин для разделения u и v равно максимальному числу независимых путей между ними.

Теорема Уитни (вершинная)

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

Рёберная теорема Менгера

Минимальное число разрезаемых ребер между u и v равно максимальному числу реберно непересекающихся путей между ними.

Рёберная теорема Уитни

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

Транспортная сеть

Орграф с истоком и стоком, где каждому ребру приписана пропускная способность c(e) >= 0.

Поток в сети

Функция на ребрах, удовлетворяющая ограничениям труб (0 <= f <= c) и закону сохранения потока в узлах.

Разрез сети (S, T)

Разбиение вершин на два множества, где S содержит исток, а T содержит сток.

Пропускная способность разреза cap(S,T)

Сумма пропускных способностей всех дуг, идущих строго из множества S в множество T.

Лемма о слабой двойственности потоков

Величина любого потока никогда не превышает пропускную способность любого разреза.

Теорема Форда-Фалкерсона

Величина максимального потока в сети в точности равна пропускной способности минимального разреза.

Алгоритм Эдмондса-Карпа

Модификация алгоритма Форда-Фалкерсона, ищущая на каждом шаге кратчайший увеличивающий путь (предотвращает зацикливание).

Эйлеров цикл

Простой цикл, проходящий через каждое ребро графа ровно один раз.

Критерий Эйлерова графа (неорграф)

Граф является эйлеровым, если он связен и степени всех его вершин четные.

Критерий Эйлерова графа (орграф)

Орграф является эйлеровым, если он сильно связен и для каждой вершины число входящих дуг равно числу исходящих.

Теорема BEST

Формула для точного подсчета количества эйлеровых циклов в ориентированном графе через остовные деревья.

Гамильтонов цикл

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

Граф де Брёйна

Орграф слов, эйлеров цикл в котором генерирует универсальную циклическую последовательность (код, где есть все подстроки длины k).

Необходимое условие Гамильтонова цикла

Если удалить из графа множество S вершин, он распадется не более чем на |S| компонент связности.

Теорема Оре (достаточное условие)

Если для любых ДВУХ НЕСМЕЖНЫХ вершин сумма их степеней >= n, то в графе есть Гамильтонов цикл.

Теорема Дирака (достаточное условие)

Если степень КАЖДОЙ вершины >= n/2, то в графе есть Гамильтонов цикл.

Замыкание графа по Хваталу cl(G)

Граф, полученный добавлением ребер между несмежными вершинами с суммой степеней >= n, пока такие пары не исчезнут.

Теорема Хватала о замыкании

Граф является гамильтоновым тогда и только тогда, когда его замыкание cl(G) является гамильтоновым.

Паросочетание (M)

Набор ребер графа, не имеющих общих концов (вершин).

Совершенное паросочетание

Паросочетание, покрывающее абсолютно все вершины графа.

M-чередующийся путь

Путь, в котором ребра строго чередуются: принадлежит паросочетанию - не принадлежит.

M-дополняющий путь

Чередующийся путь, который начинается и заканчивается в свободных (не покрытых паросочетанием) вершинах.

Теорема Бержа (о паросочетаниях)

Паросочетание максимально тогда и только тогда, когда в графе отсутствуют M-дополняющие пути.

Алгоритм Куна

Алгоритм поиска максимального паросочетания в двудольном графе путем поиска и переключения дополняющих путей.

Условие Холла

Для любого подмножества левой доли S количество их соседей в правой доле |N(S)| должно быть >= |S|.

Теорема Холла (о свадьбах)

В двудольном графе существует паросочетание, покрывающее левую долю, тогда и только тогда, когда выполняется Условие Холла.

Теорема Татта (о совершенном паросочетании)

В графе есть совершенное паросочетание

Теорема Петерсена

Любой регулярный кубический (степень всех вершин = 3) граф без мостов гарантированно имеет совершенное паросочетание.

Вершинное покрытие (K)

Множество вершин, такое что каждое ребро графа инцидентно хотя бы одной вершине из K.

Реберное покрытие (L)

Множество ребер, такое что каждая вершина графа инцидентна хотя бы одному ребру из L.

Слабая двойственность паросочетаний

Размер максимального паросочетания <= размера минимального вершинного покрытия.

Теорема Галлаи (Тождество для графа без изолированных вершин)

Размер максимального паросочетания + Размер минимального реберного покрытия = Количество вершин (n).

Теорема Кёнига-Эгервари (сильная двойственность)

В двудольном графе размер максимального паросочетания в точности равен размеру минимального вершинного покрытия.

Правильная раскраска вершин

Присвоение цветов вершинам так, чтобы любые две смежные вершины имели разные цвета.

Хроматическое число графа (χ)

Минимальное количество цветов, необходимое для правильной раскраски вершин графа.

Жадная оценка хроматического числа

Хроматическое число никогда не превышает максимальную степень вершины плюс один (Δ + 1).

Теорема Брукса

Хроматическое число <= Δ (максимальной степени), КРОМЕ двух исключений: полных графов и простых нечетных циклов.

Теорема Мицельского

Существуют графы без треугольников с любым наперед заданным (сколь угодно большим) хроматическим числом.

Теорема Эрдёша (о хроматическом числе и обхвате)

Существуют графы с одновременно сколь угодно большим хроматическим числом и сколь угодно большим обхватом (длиной кратчайшего цикла).