Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом если путь дол­жен не про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при подсчёте сумм. А если город на­о­бо­рот обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = В = 4

Ж = В + Е = 4 + 4 = 8

З = 0 (по­сколь­ку в З не ведёт ни одна до­ро­га из В)

И = Е + Ж = 4 + 8 = 12

К = Л = И =12

М = К + И + Л = 36

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

Ответ: 36.

Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом, если путь не дол­жен про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при подсчёте сумм. А если город, на­о­бо­рот, обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = В = 4 (Б не учи­ты­ва­ем, т. к. там не про­хо­дим через В)

З = В = 4 (Д и Г не учи­ты­ва­ем по тому же прин­ци­пу)

Ж = В + Е + З = 4 + 4 + 4 = 12

И = Е + Ж + З = 4 + 12 + 4 = 20

К = Л = И =20

М = К + Л = 40

Ответ: 40.

Ко­ли­че­ство путей до го­ро­да Х = ко­ли­че­ство путей до­брать­ся в любой из тех го­ро­дов, из ко­то­рых есть до­ро­га в Х.

При этом если путь дол­жен не про­хо­дить через какой-то город, нужно про­сто не учи­ты­вать этот город при подсчёте сумм. А если город на­о­бо­рот обя­за­тель­но дол­жен ле­жать на пути, тогда для го­ро­дов, в ко­то­рые из нуж­но­го го­ро­да идут до­ро­ги, в сум­мах нужно брать толь­ко этот город.

С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б = 1

З = Д = 1

Ж = Б + В + Г+ Д + Е + З = 1 + 4 + 2 + 1 + 1 + 1 = 10

И = Ж = 10 (путь в И через З и Е не учи­ты­ва­ем, т. к. надо прой­ти через Ж)

Л = И = 10

К = И = 10

М = К + Л = 20

Ответ: 20.

Ко­ли­че­ство путей до го­ро­да Т равно сумме путей в каж­дый из тех го­ро­дов, из ко­то­рых есть до­ро­га в T. С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов, кроме тех, ко­то­рые не про­хо­дят через город Л:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = А + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

K = Ж = 8

Н = Ж = 8

М = Ж + Н = 16

Л = К + Ж + М = 8 + 8 + 16 = 32

П = Л = 32 (так как ищем пути про­хо­дя­щие через город Л)

Р = П = 32

С = П = 32

Т = 32 + 32 = 64

Ответ: 64.

Ко­ли­че­ство путей до го­ро­да Т равно сумме путей в каж­дый из тех го­ро­дов, из ко­то­рых есть до­ро­га в T. С по­мо­щью этого на­блю­де­ния по­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из го­ро­дов, кроме тех, ко­то­рые не про­хо­дят через город Л:

А = 1

Б = А = 1

Д = А = 1

Г = А + Б = 1 + 1 = 2

В = Б + Г = 1 + 2 = 3

Е = Г + Д = 2 + 1 = 3

Ж = В + Г + Е = 3 + 2 + 3 = 8

Н = Ж = 8

М = Н = 8 (так как ищем пути про­хо­дя­щие через город Н)

Л = М = 8

П = Л + М = 16

Р = П = 16

С = П = 16

Т = 16 + 16 = 32

Ответ: 32.