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

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

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

А = 1.

Б = А = 1.

Г = А = 1.

Д = Б = 1.

Е = Д = 1 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Ж = Д = 1.

И = Г + Е = 2.

К = Ж + Е + И + Д = 5.

Л = К = М = 5.

Н = Л + М + К = 15.

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

Ответ: 15.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = Б + В = 3.

И = В + Г = 5 (Е не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город Е).

Ж = Д = 3.

К = Ж + И + Д = 11.

Л = К = М = 11.

Н = Л + М + К = 33.

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

Ответ: 33.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А = 1 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Д = Б = 1 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Е = Г + Д = 2 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Ж = Д = 1.

И = Г = 1.

К = Д + Ж + И + Е = 5.

Л = К = 5.

М = К + И = 6.

Н = К + Л + М = 16.

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

Ответ: 16.

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

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

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

А = 1.

Б = А = 1.

Г = А = 1 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Д = Б = 1 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Е = Г + Д = 2 (В не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город В).

Ж = Д = 1.

И = Г + Е = 3.

К = Д + Ж + И = 5.

Л = К + Ж = 6.

М = К = 5.

Н = К + Л + М = 16.

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

Ответ: 16.

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

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

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

А = 1.

Б = А = 1.

В = А = 1.

Г = А + Б + В = 3.

Д = Г = 3.

И = Г = 3 (Е не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город Е).

Ж = Д = 3.

К = И = 3 (Е не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город Е).

Л = Д + Ж + К = 3 + 3 + 3 = 9 (Е не учи­ты­ва­ем, по­сколь­ку путь не дол­жен про­хо­дить через город Е).

Н = Л = 9.

М = Л = 9.

П = Н + Л + М = 9 + 9 + 9 = 27.

Ответ: 27.