Пути в ориентированном графе — задачи с решениями (11 класс)
Типовые задачи по теме «Пути в ориентированном графе» с пошаговыми решениями. Если нужен не разбор, а тренировка с проверкой — начните с тренажёра.
Задача 1
DAG: 1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6. Сколько путей от 1 до 6?
Решение:
1
Строим ориентированный граф без циклов.
1→2, 1→3, 2→4, 3→4, 3→5, 4→6, 5→6
2
Считаем все пути от старта до финиша.
От 1 до 6
3
Ответ.
Путей: 3
Ответ: 3
Задача 2
DAG: s→a, s→b, a→c, a→d, b→d, b→e, c→t, d→t, e→t. Сколько путей от s до t?
Решение:
1
Строим ориентированный граф без циклов.
s→a, s→b, a→c, a→d, b→d, b→e, c→t, d→t, e→t
2
Считаем все пути от старта до финиша.
От s до t
3
Ответ.
Путей: 4
Ответ: 4
Задача 3
DAG: A→B, A→C, B→D, C→D, C→E, D→F, E→F, E→G, F→G. Сколько путей от A до G?
Решение:
1
Строим ориентированный граф без циклов.
A→B, A→C, B→D, C→D, C→E, D→F, E→F, E→G, F→G
2
Считаем все пути от старта до финиша.
От A до G
3
Ответ.
Путей: 4
Ответ: 4
Хотите попробовать свои силы?
На платформе тысячи задач с автопроверкой и умными подсказками.
Перейти к задачам