Калькулятор свойств графа

Основные понятия

Граф — это набор вершин и рёбер, соединяющих пары вершин. Если у рёбер есть направление, граф называют ориентированным, а рёбра — дугами. Если рёбрам приписаны числа (длины, стоимости, пропускные способности), граф взвешенный. Ребро, начинающееся и заканчивающееся в одной вершине, называют петлёй, а несколько рёбер между одной парой вершин — кратными. Граф без петель и кратных рёбер называют простым.

Степень вершины — число рёбер, которые к ней подходят (петля считается дважды). Сумма степеней всех вершин равна удвоенному числу рёбер — это лемма о рукопожатиях. Из неё следует, что вершин нечётной степени всегда чётное число. В ориентированном графе различают полустепень исхода (сколько дуг выходит) и полустепень захода (сколько входит).

Связность

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

Цикломатическое число m − n + c, где m — число рёбер, n — вершин, c — компонент, равно количеству независимых циклов. Если оно равно нулю, граф — лес, а связный лес — дерево: у дерева из n вершин ровно n − 1 ребро.

Эйлеровы графы

Эйлеров путь проходит по каждому ребру ровно один раз; если он замкнут, это эйлеров цикл. Задача восходит к Эйлеру и семи мостам Кёнигсберга. Критерий простой: все рёбра должны лежать в одной компоненте связности, а вершин нечётной степени должно быть 0 (тогда есть цикл) или 2 (тогда есть путь, который начинается в одной нечётной вершине и заканчивается в другой). В ориентированном графе у каждой вершины полустепень захода должна равняться полустепени исхода; для пути допускается одна вершина с лишней выходящей дугой (начало) и одна с лишней входящей (конец). Сам путь калькулятор строит алгоритмом Хирхольцера.

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

Гамильтонов цикл проходит через каждую вершину ровно один раз. В отличие от эйлерова, простого критерия его существования нет: задача NP-полная. Калькулятор проверяет графы до 16 вершин точно — динамическим программированием по подмножествам вершин, за время порядка 2ⁿ · n². Если цикла нет, ищется гамильтонов путь.

Двудольность и раскраска

Граф двудольный, если его вершины можно разбить на две доли так, чтобы каждое ребро соединяло вершины из разных долей. По теореме Кёнига граф двудольный тогда и только тогда, когда в нём нет циклов нечётной длины. Если граф не двудольный, калькулятор покажет такой нечётный цикл.

Правильная раскраска присваивает вершинам цвета так, чтобы соседние вершины имели разные цвета. Наименьшее число цветов — хроматическое число χ. У двудольного графа с рёбрами χ = 2, у полного графа из n вершин χ = n, а любой планарный граф по теореме о четырёх красках раскрашивается не более чем в 4 цвета. Калькулятор сначала раскрашивает граф жадным алгоритмом DSATUR, а затем перебором с отсечениями доказывает, что меньшим числом цветов обойтись нельзя. Для больших плотных графов перебор может не уложиться в отведённое время — тогда выводится верхняя оценка. Направления дуг при раскраске не учитываются.

Расстояния, диаметр и центр

Расстояние между вершинами — длина кратчайшего пути между ними: число рёбер или сумма весов во взвешенном графе. Эксцентриситет вершины — расстояние до самой удалённой от неё вершины. Наибольший эксцентриситет называют диаметром графа, наименьший — радиусом, а вершины с минимальным эксцентриситетом образуют центр. Если граф несвязный, расстояния до недостижимых вершин бесконечны.

Обходы и топологическая сортировка

Обход в ширину (BFS) посещает вершины по слоям: сначала соседей стартовой вершины, затем их соседей и так далее, и находит кратчайшие пути по числу рёбер. Обход в глубину (DFS) идёт как можно дальше по одной ветке и возвращается назад, когда идти некуда; на нём основаны поиск циклов, компонент сильной связности и топологическая сортировка. Соседей калькулятор перебирает в порядке ввода рёбер.

Топологическая сортировка упорядочивает вершины ориентированного графа так, чтобы каждая дуга шла от более ранней вершины к более поздней. Она существует только для графов без ориентированных циклов (DAG) и применяется для планирования задач с зависимостями, порядка компиляции, расписаний.

Пример

У графа из примера 6 вершин и 9 рёбер. Степени: A и F — 2, B и E — 3, C и D — 4; сумма 18 = 2 · 9. Нечётных вершин две (B и E), поэтому эйлерова цикла нет, но есть эйлеров путь из B в E. Треугольник A–B–C — нечётный цикл, значит граф не двудольный, а χ ≥ 3; раскраска в 3 цвета существует, так что χ = 3. Гамильтонов цикл: A – B – D – F – E – C – A. Эксцентриситеты A и F равны 3, остальных вершин — 2, поэтому диаметр 3, радиус 2, центр — B, C, D, E. Цикломатическое число 9 − 6 + 1 = 4.