Поиск количества путей в ориентированном графе (страница 4)

Изменим граф, убрав ребра, через которые проходили пути, минующие пункт В.

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт Г можно попасть только из пункта А. Следовательно, Г \(=\) А \(=\) 1.
В пункт В можно попасть из пунктов А и Г. Следовательно, В \(=\) А \(+\) Г \(=\) 2.
В пункт Б можно попасть только из пункта В. Следовательно, Б \(=\) В \(=\) 2.
В пункт Д можно попасть только из пункта Б. Следовательно, Д \(=\) Б \(=\) 2.
В пункт Ж можно попасть только из пункта В. Следовательно, Ж \(=\) В \(=\) 2.
В пункт Е можно попасть из пунктов Д, Б, В, Ж. Следовательно, Е \(=\) Д \(+\) Б \(+\) В \(+\) Ж \(=\) 8.
В пункт И можно попасть только из пункта Е. Следовательно, И \(=\) Е \(=\) 8.
В пункт К можно попасть только из пункта Е. Следовательно, К \(=\) Е \(=\) 8.
В пункт М можно попасть из пунктов И, Е, К. Следовательно, М \(=\) И \(+\) Е \(+\) К \(=\) 24.

Ответ: 24

Изменим граф, убрав ребра, через которые проходили пути, минующие пункт В.

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт Г можно попасть только из пункта А. Следовательно, Г \(=\) А \(=\) 1.
В пункт Б можно попасть только из пункта А. Следовательно, Б \(=\) А \(=\) 1.
В пункт В можно попасть из пунктов Б, А, Г. Следовательно, В \(=\) Б \(+\) А \(+\) Г \(=\) 3.
В пункт Д можно попасть только из пункта В. Следовательно, Д \(=\) В \(=\) 3.
В пункт Ж можно попасть только из пункта Д. Следовательно, Ж \(=\) Д \(=\) 3.
В пункт Е можно попасть из пунктов Д и Ж. Следовательно, Е \(=\) Д \(+\) Ж \(=\) 6.
В пункт И можно попасть из пунктов Д и Ж. Следовательно, И \(=\) Д \(+\) Ж \(=\) 6.
В пункт К можно попасть из пунктов Е и И. Следовательно, К \(=\) Е \(+\) И \(=\) 12.

Ответ: 12

Изменим граф, убрав ребра, через которые проходили пути, включавшие в себя пункт В.

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт Г можно попасть только из пункта А. Следовательно, Г \(=\) А \(=\) 1.
В пункт Б можно попасть только из пункта А. Следовательно, Б \(=\) А \(=\) 1.
В пункт Д можно попасть из пунктов Б и Г. Следовательно, Д \(=\) Б \(+\) Г \(=\) 2.
В пункт Ж можно попасть только из пункта Д. Следовательно, Ж \(=\) Д \(=\) 2.
В пункт Е можно попасть из пунктов Д и Ж. Следовательно, Е \(=\) Д \(+\) Ж \(=\) 4.
В пункт И можно попасть из пунктов Д и Ж. Следовательно, И \(=\) Д \(+\) Ж \(=\) 4.
В пункт К можно попасть из пунктов Е и И. Следовательно, К \(=\) Е \(+\) И \(=\) 8.

Ответ: 8

Изменим граф, убрав ребра, через которые проходили пути, включавшие в себя пункт В, и пути, минующие пункт Ж.

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт Г можно попасть только из пункта А. Следовательно, Г \(=\) А \(=\) 1.
В пункт Б можно попасть только из пункта А. Следовательно, Б \(=\) А \(=\) 1.
В пункт Д можно попасть из пунктов Б и Г. Следовательно, Д \(=\) Б \(+\) Г \(=\) 2.
В пункт Ж можно попасть только из пункта Д. Следовательно, Ж \(=\) Д \(=\) 2.
В пункт Е можно попасть только из пункта Ж. Следовательно, Е \(=\) Ж \(=\) 2.
В пункт И можно попасть только из пункта Ж. Следовательно, И \(=\) Ж \(=\) 2.
В пункт К можно попасть из пунктов Е и И. Следовательно, К \(=\) Е \(+\) И \(=\) 4.

Ответ: 4

Изменим граф, убрав ребра, через которые проходили пути, включавшие в себя пункт Е, и пути, минующие пункт В.

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт В можно попасть только из пункта А. Следовательно, В \(=\) А \(=\) 1.
В пункт Б можно попасть только из пункта В. Следовательно, Б \(=\) В \(=\) 1.
В пункт Д можно попасть только из пункта В. Следовательно, Д \(=\) В \(=\) 1.
В пункт Ж можно попасть из пунктов Б, В, Д. Следовательно, Ж \(=\) Б \(+\) В \(+\) Д \(=\) 3.
В пункт К можно попасть только из пункта Ж. Следовательно, К \(=\) Ж \(=\) 3.

Ответ: 3

Посчитаем сколькими путями можно придти в каждый дом:

Ответ: 25

Посчитаем сколькими путями можно придти в каждый дом:

Ответ: 13