Часть II. Алгоритмы на графах¶

Глава 11. Основы графов¶

11.1 Терминология графов¶

Введение¶

Многие задачи в программировании можно свести к задачам на графах и решить с помощью соответствующих алгоритмов.

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

В этой главе мы разберём:

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

Что такое граф¶

Граф состоит из:

• вершин (узлов)
• рёбер (соединений между вершинами)

Обозначения:

• n — число вершин
• m — число рёбер

Вершины обычно нумеруются: 1, 2, ..., n

Пример графа¶

graph TD
    1 --- 2
    1 --- 3
    3 --- 4
    4 --- 5
    2 --- 5

В этом графе:

• 5 вершин
• несколько рёбер между ними

Пути в графе¶

Путь — это последовательность вершин, соединённых рёбрами.

Пример пути:

1 → 3 → 4 → 5

Длина пути — количество рёбер:

длина = 3

Виды путей¶

1. Цикл Путь, который начинается и заканчивается в одной вершине:

1 → 3 → 4 → 1

2. Простой путь Путь без повторяющихся вершин.

Связность графа¶

Граф называется связным, если:

между любой парой вершин существует путь

Пример связного графа¶

graph TD
    1 --- 2
    2 --- 3
    3 --- 4

Пример несвязного графа¶

graph TD
    1 --- 2
    3 --- 4

Здесь:

• вершины {1,2} отдельно
• вершины {3,4} отдельно

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

Компоненты связности — это отдельные «кусочки» графа.

Пример:

{1,2,3}, {4,5,6}, {7}

Дерево¶

Дерево — это граф, который:

• связный
• содержит ровно n - 1 рёбер

Свойство:

между любыми двумя вершинами существует ровно один путь

graph TD
    1 --- 2
    1 --- 3
    3 --- 4
    3 --- 5

Ориентированные графы¶

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

graph LR
    1 --> 2
    3 --> 1
    2 --> 5

Важно:

• путь может существовать в одну сторону
• но отсутствовать в обратную

Взвешенные графы¶

В взвешенном графе каждому ребру присвоен вес.

graph TD
    1 -- 5 --> 2
    1 -- 3 --> 3
    3 -- 2 --> 4
    4 -- 4 --> 5
    2 -- 7 --> 5

Длина пути¶

Считается как сумма весов рёбер.

Пример:

1 → 2 → 5 = 5 + 7 = 12  
1 → 3 → 4 → 5 = 3 + 2 + 4 = 9

Кратчайший путь — второй.

Соседи и степени вершин¶

Соседи — вершины, соединённые ребром.

Пример:

• у вершины 2 соседи: 1, 4, 5
• степень вершины = 3

Важное свойство¶

Сумма степеней всех вершин:

= 2 * m

Почему:

• каждое ребро учитывается дважды

⇒ сумма всегда чётная

Особые типы графов¶

Регулярный граф¶

У всех вершин одинаковая степень:

deg(v) = d

Полный граф¶

Каждая вершина соединена со всеми остальными:

deg(v) = n - 1

Итог¶

В этом разделе мы разобрали базовые понятия:

• вершины и рёбра
• пути и циклы
• связность
• компоненты
• деревья
• ориентированные и взвешенные графы
• степени вершин

Это фундамент, без которого невозможно изучать:

• обходы (DFS, BFS)
• кратчайшие пути
• алгоритмы на деревьях