Краткая теория перед тестом

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

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

2. Свойства графов

1. В любом графе есть как минимум две вершины с одинаковой степенью.
2. Число вершин нечётной степени всегда чётное.
3. Сумма степеней всех вершин = удвоенному числу рёбер.

3. Подсчёт количества путей

В ориентированном графе число путей из A в K можно найти, последовательно суммируя пути к каждой вершине:
N(K) = N(Б) + N(В) + …, где суммируются только те вершины, из которых есть дуга в K.

4. Кратчайший путь

Перебираем все возможные маршруты и складываем длины рёбер. Выбираем минимальную сумму.

5. Соответствие таблицы и графа (алгоритм)

1. У каждой вершины графа записать её степень.
2. Разбить вершины на группы по степеням.
3. Сопоставить группы с номерами строк/столбцов таблицы.
4. Внутри группы — разбить на подгруппы по степеням смежных вершин.
5. Проанализировать и найти нужное соответствие.