Задание 9 ОГЭ по информатике: количество путей в графе

На схеме показаны дороги между городами A, B, C, D, E, F, G, H. Ехать по дороге можно только в ту сторону, куда показывает стрелка. Сколько существует различных путей из города A в город H?

Решение

1. Подписывай у каждого города, сколькими путями в него можно приехать из A. У самого A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки.
2. Иди по схеме слева направо — так, чтобы к моменту подсчёта все нужные слагаемые уже были известны: B = A = 1; C = A + B = 1 + 1 = 2; D = B + C = 1 + 2 = 3; E = C = 2; F = D = 3; G = D + E = 3 + 2 = 5.
3. Последним считаем город H: H = F + G = 3 + 5 = 8. Путей из A в H — 8

Ответ: 8

Если получилось другое число

• 11 — Столько на схеме дорог. А путь — это целый маршрут из A в H, он складывается из нескольких дорог.
• 5 — В город H ведут 2 дороги: из городов F, G. Сложи числа у всех этих городов.

На схеме показаны дороги между городами A, B, C, D, E, F, G, H. Ехать по дороге можно только в ту сторону, куда показывает стрелка. Сколько существует различных путей из города A в город H, которые проходят через город C?

Решение

1. Путь через C состоит из двух частей: из A в C и из C в H. Любое начало можно продолжить любым концом, поэтому число путей — это произведение.
2. Сколько путей из A в C. У A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки. Считаем только города, из которых можно доехать до C: B = A = 1; C = A + B = 1 + 1 = 2. В C ведут 2 пути.
3. Сколько путей из C в H. Начни счёт заново: у C ставим 1 и считаем только города, в которые из C можно попасть: D = C = 1; E = C = 1; F = D = 1; G = D + E = 1 + 1 = 2; H = F + G = 1 + 2 = 3. Из C в H — 3 пути.
4. Перемножь: 2 · 3 = 6

Ответ: 6

Если получилось другое число

• 8 — Это все пути из A в H. Среди них есть такие, которые обходят город C, — их считать не нужно.
• 5 — Числа путей до города C и после него нужно перемножить, а не сложить: каждое начало сочетается с каждым концом.
• 2 — Это пути из A в C. Из C ещё нужно доехать до H, и сделать это можно не одним способом.

На схеме показаны дороги между городами A, B, C, D, E, F, G, H. Ехать по дороге можно только в ту сторону, куда показывает стрелка. Сколько существует различных путей из города A в город H, которые не проходят через город C?

Решение

1. Через город C ехать нельзя — мысленно сотри его вместе со всеми дорогами, которые в него входят и из него выходят.
2. На оставшейся схеме подписывай у каждого города, сколькими путями в него можно приехать из A. У A ставим 1, у каждого следующего города — сумму чисел тех городов, из которых в него ведут стрелки: B = A = 1; D = B = 1; E = 0 (сюда теперь не попасть); F = D = 1; G = D + E = 1 + 0 = 1.
3. Последним считаем город H: H = F + G = 1 + 1 = 2. Путей мимо C — 2

Ответ: 2

Если получилось другое число

• 8 — Это все пути из A в H. Часть из них проходит через город C — их нужно убрать.
• 6 — Это, наоборот, пути, которые проходят через C. Спрашивают про те, что его обходят.