Самостоятельная работа Подсчёт путей в графе. ФИ_ 2 вариант Подсчёт ВСЕХ путей Задание 1 № Сколько существует различных путей из города А в город М? Задание 2 №. Сколько существует различных путей из города А в город Т? Подсчёт путей с обязательной вершиной Задание 3 № Сколько существует различных путей из города А в город М, проходящих через город Л? Подсчёт путей с избегаемой вершиной Задание 4 № Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт В?

Привет! Сейчас я помогу тебе разобраться с этими заданиями. Здесь нужно посчитать количество путей в графах. Давай разберем каждое задание по порядку.

Задание 1

В первом задании нужно посчитать количество различных путей из города А в город М.

Давай посмотрим на граф:

1. Из А можно попасть в B, D.
2. Из B можно попасть в C, F.
3. Из D можно попасть в E, F.
4. Из C можно попасть в G.
5. Из E можно попасть в H, K.
6. Из F можно попасть в G, H, K.
7. Из G можно попасть в L, M.
8. Из H можно попасть в L, M.
9. Из K можно попасть в L, M.
10. Из L можно попасть в M.

Теперь считаем пути:

• Пути через B: A → B → C → G → M (1 путь), A → B → C → G → L → M (1 путь), A → B → F → G → M (1 путь), A → B → F → G → L → M (1 путь), A → B → F → H → M (1 путь), A → B → F → H → L → M (1 путь), A → B → F → K → M (1 путь), A → B → F → K → L → M (1 путь). Итого, 8 путей через B.
• Пути через D: A → D → E → H → M (1 путь), A → D → E → H → L → M (1 путь), A → D → E → K → M (1 путь), A → D → E → K → L → M (1 путь), A → D → F → G → M (1 путь), A → D → F → G → L → M (1 путь), A → D → F → H → M (1 путь), A → D → F → H → L → M (1 путь), A → D → F → K → M (1 путь), A → D → F → K → L → M (1 путь). Итого, 10 путей через D.

Сложим все пути: 8 + 10 = 18 путей.

Ответ: 18

Задание 2

Во втором задании нужно посчитать количество различных путей из города А в город Т.

Давай посмотрим на граф:

1. Из A можно попасть в Б, Г.
2. Из Б можно попасть в В, К.
3. Из Г можно попасть в Д, Л.
4. Из В можно попасть в Е, К.
5. Из Д можно попасть в Е, Л.
6. Из Е можно попасть в М, Н.
7. Из К можно попасть в М, Н, П.
8. Из Л можно попасть в М, Н, Р.
9. Из М можно попасть в Н, П, Р.
10. Из Н можно попасть в П, Р, Т.
11. Из П можно попасть в Т.
12. Из Р можно попасть в Т.

Считаем пути:

• Пути через Б: A → Б → В → Е → Н → Т, A → Б → В → Е → Н → Р → Т, A → Б → В → Е → Н → П → Т, A → Б → В → К → Н → Т, A → Б → В → К → П → Т, A → Б → К → М → Н → Т, A → Б → К → М → П → Т, A → Б → К → Н → Р → Т, A → Б → К → П → Р → Т. Итого, 9 путей.
• Пути через Г: A → Г → Д → Е → Н → Т, A → Г → Д → Е → Н → Р → Т, A → Г → Д → Е → Н → П → Т, A → Г → Д → Л → Н → Т, A → Г → Л → М → Н → Т, A → Г → Л → М → П → Т, A → Г → Л → Н → Р → Т, A → Г → Л → Р → Т. Итого, 8 путей.

Сложим все пути: 9 + 8 = 17 путей.

Ответ: 17

Задание 3

В третьем задании нужно посчитать количество различных путей из города А в город М, проходящих через город Л.

Давай посмотрим на граф:

1. Из А можно попасть в Б, Г, Д.
2. Из Б можно попасть в В, Е.
3. Из Г можно попасть в В, Ж, З.
4. Из Д можно попасть в З, Е.
5. Из В можно попасть в Е, Ж.
6. Из Е можно попасть в Ж, И.
7. Из Ж можно попасть в И, К.
8. Из З можно попасть в Ж, И.
9. Из И можно попасть в К, Л.
10. Из К можно попасть в Л, М.
11. Из Л можно попасть в М.

Считаем пути, проходящие через Л:

• A → Б → В → Е → Ж → И → Л → М, A → Б → В → Е → Ж → К → Л → М, A → Б → Е → Ж → И → Л → М, A → Б → Е → Ж → К → Л → М
• A → Г → В → Е → Ж → И → Л → М, A → Г → В → Е → Ж → К → Л → М, A → Г → Ж → И → Л → М, A → Г → Ж → К → Л → М, A → Г → З → Ж → И → Л → М, A → Г → З → Ж → К → Л → М, A → Г → З → И → Л → М,
• A → Д → З → Ж → И → Л → М, A → Д → З → Ж → К → Л → М, A → Д → З → И → Л → М, A → Д → Е → Ж → И → Л → М, A → Д → Е → Ж → К → Л → М, A → Д → Е → И → Л → М

Всего 17 путей.

Ответ: 17

Задание 4

В четвертом задании нужно посчитать количество различных путей из пункта А в пункт Н, не проходящих через пункт В.

Давай посмотрим на граф:

1. Из А можно попасть в Б, Г.
2. Из Б можно попасть в Д, В.
3. Из Г можно попасть в И, В.
4. Из Д можно попасть в Ж, Е, К.
5. Из Е можно попасть в Ж, К.
6. Из Ж можно попасть в К, Л.
7. Из И можно попасть в Л, М.
8. Из К можно попасть в Л, Н.
9. Из Л можно попасть в Н, М.
10. Из М можно попасть в Н.

Считаем пути, не проходящие через В:

• A → Б → Д → Е → Ж → К → Н, A → Б → Д → Ж → К → Н, A → Б → Д → Е → Ж → Л → Н, A → Б → Д → Ж → К → Л → Н, A → Б → Д → Ж → Л → М → Н,
• A → Г → И → Л → Н, A → Г → И → Л → М → Н, A → Г → И → М → Н

Всего 8 путей.

Ответ: 8

Теперь ты знаешь, как решать такие задачи! Если у тебя возникнут еще вопросы, не стесняйся обращаться!