Графы: основные понятия

Граф - это кружки и стрелки

Представь карту маршруток: кружки - остановки, стрелки - рейсы, число у стрелки - сколько минут ехать.

Всё, это и есть граф. Кружок называют вершиной, стрелку - ребром, число у стрелки - весом ребра.

В этой теме нас интересуют ориентированные графы: если в файле записано L M W, это означает ребро из L идет в M и его вес W. Обратное ребро M → L из этой записи не следует.

Основы

Вершина и ребро

Вершины пронумерованы. Номера произвольные: рядом могут стоять вершины 1 и 917, и это ничего не значит — соседство задают только стрелки.

Стрелка работает в одну сторону

Ребро из 1 в 8 разрешает ехать из 1 в 8. Обратный рейс - отдельное ребро, и если его не нарисовали, значит его нет.

Из «есть стрелка туда» не следует «есть стрелка обратно».

Путь

Путь - цепочка вершин, где каждый следующий шаг разрешён стрелкой. Прыгать через вершины нельзя.

Длина пути

Длина пути равна сумме весов всех рёбер, входящих в этот путь.

1 → 5 (10)
5 → 8 (7)
8 → 100 (12)

Длина пути:
10 + 7 + 12 = 29

 

Кратчайший путь - тот, у которого сумма меньше всех. Он спокойно может идти через большее число остановок: три коротких перегона часто быстрее одного длинного.

Пример

Выпишем все способы добраться из вершины 1 в вершину 100. Из единицы выходят две стрелки - в 5 и в 8, с них и начнём.

• 1 → 5 → 100: 4.0 + 3.0 = 7.0
• 1 → 8 → 5 → 100: 2.0 + 1.5 + 3.0 = 6.5
• 1 → 8 → 100: 2.0 + 9.0 = 11.0

Короче всех второй путь - 6.5, хотя в нём три шага, а в первом два.

Вершина 3 в этой истории лишняя: стрелка из неё выходит, а в неё не входит ни одной. Из вершины 1 в неё не попасть.

А какой путь самый длинный?

1 → 8 → 100, его длина 11.0. Самый длинный — тоже не значит «с наибольшим числом шагов».

Ловушки

• Поехали по стрелке против направления.
• Посчитали количество шагов вместо суммы весов.
• Решили, что путь с меньшим числом шагов короче.
• Считают, что из любой вершины можно добраться до любой.
• Пропустили вершину в пути: шаг разрешён, только если стрелка нарисована.

Проверь себя