Что такое граф
Граф состоит из вершин (пунктов) и рёбер (дорог), которые их соединяют. Если у рёбер есть числа — это взвешенный граф (длины дорог, стоимость). Если у рёбер есть направление — граф ориентированный (односторонние дороги).
Проверь себя. В графе 9 рёбер. Чему равна сумма степеней всех его вершин?
Ответ: 18
Таблица смежности и соответствие граф ↔ таблица
Граф записывают таблицей: на пересечении строки $i$ и столбца $j$ стоит длина дороги между пунктами $i$ и $j$ (пусто — дороги нет). Таблица симметрична относительно главной диагонали, если дороги двусторонние.
В задании ЕГЭ-1 дан граф с буквами и таблица с номерами; нужно понять, какая цифра — какая буква. Порядок действий:
- посчитайте степени вершин в графе и число заполненных клеток в каждой строке таблицы;
- вершина с уникальной степенью определяется сразу;
- остальные — по соседям уже найденных вершин и по весам.
Кратчайший путь
Идея алгоритма Дейкстры: у каждой вершины держим лучшую известную длину пути от старта. Берём ближайшую ещё не закрытую вершину, закрываем её и «подтягиваем» соседей: $d(v) = \min(d(v),\ d(u) + w(u,v))$.
Пример. Дороги: AB = 3, AC = 5, BC = 1, BD = 7, CD = 4, CE = 8, DE = 2. Кратчайший путь из A в E.
Старт: $d(A)=0$. Закрываем A: $d(B)=3$, $d(C)=5$. Ближайшая B: $d(C)=\min(5, 3+1)=4$, $d(D)=10$. Ближайшая C: $d(D)=\min(10, 4+4)=8$, $d(E)=12$. Ближайшая D: $d(E)=\min(12, 8+2)=10$. Ответ: 10 (A–B–C–D–E).
Число путей на схеме без циклов
Пусть дороги односторонние и циклов нет. Число путей из A в вершину $v$ равно сумме чисел путей во все вершины, из которых в $v$ ведёт дорога. Считаем по порядку от A.
Пример. Дороги: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Е, Д→Е, Е→Ж. Число путей из А в Ж.
$N(А)=1$; $N(Б)=1$; $N(В)=1$; $N(Г)=N(Б)+N(В)=2$; $N(Д)=N(В)=1$; $N(Е)=N(Г)+N(Д)=3$; $N(Ж)=3$.
Проверь себя. В схеме A→B, A→C, B→D, C→D, D→E, D→F, E→G, F→G сколько путей из A в G?
Ответ: 6