Графы: схемы дорог, кратчайший путь и число путей
Таблица смежности, метод пометок для кратчайшего пути и метод накопления для подсчёта количества маршрутов.
В графовых заданиях ОГЭ встречаются две разные задачи: найти длину кратчайшего пути (складываем веса) и найти количество путей (складываем числа путей в предыдущие вершины). Перепутать методы — значит потерять балл.
В таблице на пересечении строки и столбца стоит вес дороги между пунктами; пустая клетка означает отсутствие прямой дороги. Таблица неориентированного графа симметрична относительно главной диагонали. Число дорог, выходящих из пункта, равно числу заполненных клеток в его строке.
Схема дорог (веса в километрах)
| Пункт | А | Б | В | Г | Д | Е |
|---|---|---|---|---|---|---|
| А | — | 3 | 4 | |||
| Б | 3 | — | 2 | |||
| В | 4 | — | 1 | 8 | ||
| Г | 2 | 1 | — | 5 | 9 | |
| Д | 8 | 5 | — | 2 | ||
| Е | 9 | 2 | — |
- ·Складываем веса дорог
- ·В каждой вершине берём минимум
- ·Ответ — число километров
- ·Сравниваем суммы, а не длину маршрута в рёбрах
- ·Веса не используются вообще
- ·В вершину: сумма путей всех предшественников
- ·Ответ — количество маршрутов
- ·Старт помечается единицей
Условие: по таблице выше определите длину кратчайшего пути между пунктами А и Е (при условии, что двигаться можно только по указанным дорогам). Решение. Перебираем все маршруты и складываем веса: А-Б-Г-Е = 3 + 2 + 9 = 14 А-Б-Г-Д-Е = 3 + 2 + 5 + 2 = 12 А-В-Г-Е = 4 + 1 + 9 = 14 А-В-Г-Д-Е = 4 + 1 + 5 + 2 = 12 А-В-Д-Е = 4 + 8 + 2 = 14 Минимум равен 12. В бланк: 12
Условие: на рисунке схема дорог с односторонним движением: А→Б, А→В, Б→Г, В→Г, В→Д, Г→Д, Г→Е, Д→Е. Сколько существует различных путей из города А в город Е? Решение. Помечаем вершины числом путей из А, двигаясь так, чтобы все предшественники уже были посчитаны. А = 1 Б = А = 1 В = А = 1 Г = Б + В = 1 + 1 = 2 Д = В + Г = 1 + 2 = 3 Е = Г + Д = 2 + 3 = 5 В бланк: 5
Если требуется число путей, проходящих через пункт К, считают произведение: (пути из А в К) × (пути из К в конца). Если нужны пути, НЕ проходящие через К, вершину К просто вычёркивают из схемы вместе со всеми её дорогами и считают заново. Ещё одна ошибка — в задаче на кратчайший путь выбирать маршрут с наименьшим числом дорог: короткий по рёбрам путь часто длиннее по километрам.
- ✓Определено, что ищется: длина пути или количество путей
- ✓Для длины складывались веса, для количества — числа путей
- ✓Вершины обрабатывались в порядке, где все предшественники уже посчитаны
- ✓Учтена односторонность дорог, если она указана
- ✓Проверено требование «через пункт» или «минуя пункт»
- ✓В бланке одно число без единиц измерения