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

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

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

А = 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.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

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

К = Ж = 3.

Н = Ж = 3.

М = Ж + Н = 6.

Л = К + Ж + М = 12.

П = К + Л + М = 21.

Р = П = 21.

С = П = 21.

Т = П + Р + С = 63.

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

Ответ: 63.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город Е, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в горд Е и ко­ли­че­ства путей из го­ро­да Е в город Т.

Най­дем ко­ли­че­ство путей из го­ро­да А в город Е:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Най­дем ко­ли­че­ство путей из го­ро­да Е в город Т. За­ме­тим, что все эти пути долж­ны про­хо­дить через город П. Тогда ко­ли­че­ство путей из го­ро­да Е в город П равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да Е в город П и ко­ли­че­ства путей из го­ро­да П в город Т.

Най­дем ко­ли­че­ство путей из го­ро­да Е в город П (при этом Е - ис­ход­ный пункт):

Е = 1.

Ж = Е = 1.

К = Ж = 1.

Н = Ж = 1.

М = Ж + Н = 2.

Л = К + Ж + М = 4.

П = К + Л + М = 7.

Най­дем ко­ли­че­ство путей из го­ро­да П в город Т (при этом П - ис­ход­ный пункт):

П = 1.

Р = П =1.

С = П = 1.

Т = П + С + Т = 3.

Тогда ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город Е, равно 3 · 7 · 3  =  63.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

В = Б + Г = 3.

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

К = Ж = 3.

Н = Ж = 3.

М = Ж + Н = 6.

Л = К + Ж + М = 12.

П = К + Л + М = 21.

Р = П = 21.

С = П = 21.

Т = Р + С = 42.

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

При­ве­дем дру­гое ре­ше­ние.

За­ме­тим, что путь из го­ро­да А в город Т дол­жен обя­за­тель­но про­хо­дить через го­ро­да Ж и П. Кроме того, по усло­вию путь дол­жен про­хо­дить через город В. Город В лежит на пути из А в Ж. Сле­до­ва­тель­но, чтобы найти ко­ли­че­ство путей из го­ро­да А в город Т, можно найти ко­ли­че­ство путей из го­ро­да А в город В, из го­ро­да В в город Ж, из го­ро­да Ж в город П и из го­ро­да П в город Т, и пе­ре­мно­жить по­лу­чив­ши­е­ся числа.

Най­дем ко­ли­че­ство путей из го­ро­да А в город В:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Из го­ро­да В в город Ж ведет толь­ко один путь.

Най­дем ко­ли­че­ство путей из го­ро­да Ж в город П (при этом Ж - ис­ход­ный пункт):

К = Ж = 1.

Н = Ж = 1.

М = Ж + Н = 2.

Л = К + Ж + М = 4.

П = К + Л + М = 7.

Из го­ро­да П в город Т есть два пути: П—Р—Т и П—С—Т.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город В, равно 3 · 1 · 7 · 2=42.

Ответ: 42.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Л = Ж + К= 19.

Н = Д + Ж = 9.

М = Л = 19 (Ж и Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Л).

П = Л + М = 38 (К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Л).

Р = П = 38.

С = П = 38.

Т = Р + С = 76.

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

Ответ: 76.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город Л, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Л и ко­ли­че­ства путей из го­ро­да Л в город Т.

Най­дем ко­ли­че­ство путей из го­ро­да А в город Л:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Л = Ж + К= 19.

Най­дем ко­ли­че­ство путей из го­ро­да Л в город Т (при этом Л - ис­ход­ный пункт).

Л = 1.

М = Л = 1.

П = Л + М = 2.

Р = П = 2.

С = П = 2.

Т = Р + С = 4.

Сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город Л, равно 19 · 4  =  76.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Н = Д + Ж = 9.

М = Ж + Н = 17.

Л = М = 17. (Ж и К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через М)

П = Л + М = 34 (К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через М).

Р = П = 34.

С = П = 34.

Т = Р + С = 68.

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

Ответ: 68.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город М, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город М и ко­ли­че­ства путей из го­ро­да М в город Т.

Най­дем ко­ли­че­ство путей из го­ро­да А в город М:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж + В = 11.

Н = Д + Ж = 9.

М = Ж + Н = 17.

Най­дем ко­ли­че­ство путей из го­ро­да М в город Т (при этом М  — ис­ход­ный пункт):

М = 1.

Л = М = 1.

П = М + Л = 2.

Р = П = 2.

С = П = 2.

Т = С + Т = 4.

Тогда ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город М, равно 17 · 4  =  68.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д = 1

Ж = Е + В + Г + Д + З = 5 + 4 + 2 + 1 + 1 = 13

И = Ж = 13 (Е и З не учи­ты­ва­ем, по­сколь­ку нужно обя­за­тель­но про­хо­дить через Ж)

К = И = 13

Л = И = 13

М = К + Л + И = 39

Ответ: 39.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж = 8.

Л = Ж + К= 16.

Н = Е + Ж = 11.

М = Л = 16 (Ж и Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Л).

П = Л + М = 32 (К не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Л).

Р = П = 32.

С = П = 32.

Т = Р + С + П = 96.

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

Ответ: 96.

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

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

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

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж = 8.

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

Н = Е + Ж = 11.

М = Л = 8 (Ж и Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через К).

П = Л + М + К = 24.

Р = П + К = 32.

С = П = 24.

Т = Р + С + П = 80.

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

Ответ: 80.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город К, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город К и ко­ли­че­ства путей из го­ро­да К в город Т.

Най­дем ко­ли­че­ство путей из го­ро­да А в город К:

А = 1.

Б = А = 1.

Г = А + Б = 2.

Д = А = 1.

В = Б + Г = 3.

Е = Г + Д = 3.

Ж = В + Г + Е = 8.

К = Ж = 8.

Най­дем ко­ли­че­ство путей из го­ро­да К в город Т (при этом К  — ис­ход­ный пункт):

К = 1.

Л = К = 1.

М = Л = 1.

П = Л + М + К = 3.

Р = П + К = 4.

С = П = 3.

Т = П + Р + С = 10.

Тогда ко­ли­че­ство путей из го­ро­да А в город Т, про­хо­дя­щих через город К, равно 8 · 10  =  80.

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

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

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

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 2.

В = Б + Г + А = 4.

Е = В + Б = 5.

З = Д = 1.

Ж = В + Г + Е + Д + З = 13.

И = Ж + Е + З = 19.

Л = И = 19.

К = И = 19.

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

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

Ответ: 19.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

Е = Б + В = 5

З = Д + Г + В = 7

Ж = В + Е + З = 4 + 5 + 7 = 16

И = Е + Ж + З = 5 + 16 + 7 = 28

Л = И = 28

К = И = 28

М = Л = 28 (путь в М через К не учи­ты­ва­ем, т. к. надо прой­ти через Л)

Ответ: 28.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

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

Ж = Д + Е = 6.

И = Е = 3.

К = Ж + И = 9.

Л = К = М = 9.

Н = Л + М = 18.

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

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город Н, про­хо­дя­щих через город Д, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город Д и ко­ли­че­ства путей из го­ро­да Д в город Н.

Най­дем ко­ли­че­ство путей из го­ро­да А в город Д:

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

Д = В + Б = 3.

Най­дем ко­ли­че­ство путей из го­ро­да Д в город Н (при этом Д  — ис­ход­ный пункт):

Д = 1.

Е = Д = 1.

Ж = Д + Е = 2.

И = Е = 1.

К = Ж + И = 3.

Л = К = М = 3.

Н = Л + М = 6.

Тогда ко­ли­че­ство путей из го­ро­да А в город Н, про­хо­дя­щих через город Д, равно 3 · 6  =  18.

Ответ: 18.

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

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

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

А = 1.

Б = А = 1.

В = А + Б = 2.

Г = А + В = 3.

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

Ж = Е = 3.

И = Е + Г = 6.

К = И + Ж = 9.

Л = К = М = 9.

Н = Л + М = 18.

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

Ответ: 18.

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

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

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

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 2.

В = А + Б + Г = 4.

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

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

Ж = В + Е + З = 12.

И = Е + Ж + З = 20.

К = И = 20.

Л = И = 20.

М = К + И + Л = 60.

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

Ответ: 60.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город В, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город В и ко­ли­че­ства путей из го­ро­да В в город М.

Най­дем ко­ли­че­ство путей из го­ро­да А в город В:

А = 1.

Б = А = 1.

Д = А = 1.

Г = А + Д = 2.

В = А + Б + Г = 4.

Най­дем ко­ли­че­ство путей из го­ро­да В в город М. За­ме­тим, что все эти пути долж­ны прой­ти через город И, сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да В в город М равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да В в город И и ко­ли­че­ства путей из го­ро­да И в город М.

Най­дем ко­ли­че­ство путей из го­ро­да В в город И, при этом В  — ис­ход­ный пункт:

В = 1.

Е = В =1.

З = В = 1.

Ж = В + Е + З = 3.

И = Е + Ж + З = 5.

Из го­ро­да И в город М есть три пути: И—К—М, И—Л—М и И—М.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город В, равно 4 · 5 · 3  =  60.

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1.

Г = А + Б + В + Ж = 4.

Д = Ж = 1.

Е = Д + Г = 5.

И = Г + Е + В = 10.

К = И = 10.

Л = К = 10.

М = Н = Л = 10.

П = Л + Н + М = 30.

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

Ответ: 30.

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из пунк­та А в пункт П, про­хо­дя­щих через пункт И, равно про­из­ве­де­нию ко­ли­че­ства путей из пунк­та А в пункт И и ко­ли­че­ства путей из пунк­та И в пункт П.

Най­дем ко­ли­че­ство путей из пунк­та А в пункт И:

А = 1.

Б = А = В = 1.

Ж = Б = 1.

Г = А + Б + В + Ж = 4.

Д = Ж = 1.

Е = Д + Г = 5.

И = Г + Е + В = 10.

Най­дем ко­ли­че­ство путей их пунк­та И в пункт П (при этом И  — ис­ход­ный пункт):

И = 1.

К = И = 1.

Л = К = 1.

М = Н = Л = 1.

П = Л + М + Н = 3.

Тогда ко­ли­че­ство путей из пунк­та А в пункт П, про­хо­дя­щих через город И, равно 10 · 3  =  30.

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

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

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

А = 1.

Б = А = В = 1.

Ж = Б = 1

Г = А + Б + В + Ж = 4

Д = Ж = 1

И = Г + В = 5.

Е = Д + Г + И = 10.

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

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

М = Н = Л = 20.

П = Л + Н + М = 60.

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

Ответ: 60.

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

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

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

А = 1.

Б = А = 1.

Г = Б = 1.

В = Б + Г = 2.

Е = Г = 1.

Ж = В + Г + Е = 4.

К = Ж = 4.

Л = Ж + К= 8.

Н = Е + Ж = 5.

М = Л + Ж + Н = 17.

П = К + Л + М = 29.

Р = П + К = 33.

С = П = 29.

Т = Р + С + П = 91.

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

Ответ: 91.

При­ме­ча­ние.

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

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

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

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

А = 1.

Д = А = 1.

Г = А + Д = 2.

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

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

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

Ж = В + Е + З = 8.

И = Е + Ж + З = 14.

К = И = 14.

Л = И + К = 28.

М = Л + К = 42.

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

Ответ: 42.

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

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

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

А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Г = 1 + 2 = 3

Б = А + В = 1 + 3 = 4

Е = Б = 4

З = Д + Г + В = 1 + 2 + 3 = 6

Ж = Е + Б + В + З = 4 + 4 + 3 + 6 = 17

И = Ж = 17 (учи­ты­ва­ем толь­ко город, через ко­то­рый дол­жен про­хо­дить путь)

К = И = 17

Л = И = 17

М = К + И + Л = 17 + 17 + 17 = 51

Ответ: 51.

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

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

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

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

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

Ж = В + З = 4 + 4 = 8 (Е не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через В)

И = З + Ж = 4 + 8 = 12

К = Л = И =12

М = К + Л = 24

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

При­ве­дем дру­гое ре­ше­ние.

Ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город В, равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да А в город В и ко­ли­че­ства путей из го­ро­да В в город М.

Най­дем ко­ли­че­ство путей из го­ро­да А в город В:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4.

За­ме­тим, что из го­ро­да В в город М можно до­брать­ся толь­ко через город И. Сле­до­ва­тель­но, ко­ли­че­ство путей из го­ро­да В в город М равно про­из­ве­де­нию ко­ли­че­ства путей из го­ро­да В в город И и ко­ли­че­ства путей из го­ро­да И в город М.

Най­дем ко­ли­че­ство путей из го­ро­да В в город И (при этом В  — ис­ход­ный пункт):

В = 1

З = В =1

Ж = В + З = 1 + 1 = 2

И = З + Ж = 1 + 2 = 3.

Из го­ро­да И в город М есть два пути: И—К—М и И—Л—м.

Таким об­ра­зом, ко­ли­че­ство путей из го­ро­да А в город М, про­хо­дя­щих через город В, равно 4 · 3 · 2  =  24.

Ответ: 24.

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

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

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

А = 1

Б = А = 1

В = А = 1

Д = Б = 1

Г = А + Б + Д = 1 + 1 + 1 = 3

И = В + Г = 4

Ж = Д = 1

Е = Г + Д + Ж + И = 3 + 1 + 1 + 4 = 9

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

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

М = К + Л = 9 + 9 = 18

П = Л + М = 27 (Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Е)

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

Ответ: 27.

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

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

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

А = 1

Б = 1 = 1

В = А = 1

Д = Б = 1

Г = А + Б + Д = 3

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

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

К = Е + И = 9

Л = Е = 6 (Ж и Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

М = К + Л = 15

П = Л + М = 21 (Н не учи­ты­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Г)

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

Ответ: 21.

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

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

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

А = 1

В = А = 1

Г = А = 1

Е = А + В + Г = 3

Б = А + В + Е = 5

Д = Б + Е = 8

К = Д = 8

Л = К = 8

М = Л + К = 16

П = М = 16

Р = М = 16

С = М + П + Р = 48

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

Ответ: 48.

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

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

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

А = 1

Г = А = 1

Б = А = 1

В = А + Б = 2

Д = Б = 1

И = Г = 1

Е = А + Б + В + Г + И + Д = 7

Ж = Д + Е + И = 9

Н = Ж + И = 10

М = Н = 10 (Ж, Л и К не рас­смат­ри­ва­ем, по­сколь­ку путь дол­жен про­хо­дить через Н)

П = М = 10

Р = М = 10

С = М + П + Р = 30

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

Ответ: 30.

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

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

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

А = 1

В = А = 1

Г = А + В = 2

Е = В + Г = 3

Б = А + В + Е = 5

Д = Б + Е = 8

Ж = Д + Е = 11

Л = Д + Ж = 19

К = Л = 19

М = К + Л = 38

П = М = 38

Р = М = 38

С = М + П + Р = 114

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

Ответ: 114.

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

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

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

А = 1

В = А = 1

Г = А + В = 2

Е = В + Г = 3

Б = А + В + Е = 5

Д = Б + Е = 8

Ж = Д + Е = 11

Л = Ж = 11

К = Л = 11

М = Ж + К + Л = 33

П = М = 33

Р = М = 33

С = М + П + Р = 99

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

Ответ: 99.

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

Г = А + В = 3

Е = В + Г = 5

И = Г + Е = 8

Ж = Е + И = 13

Л = Ж = 13

К = Л = 13

Н = Ж = 13

М = Ж + К + Л + Н = 52

П = К + М = 65

Р = М = 52

С = М + П + Р = 169

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

Ответ: 169.

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

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

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

А = 1

Б = А = 1

В = А + Б = 2

Г = А + В = 3

Е = В + Г = 5

Д = Б + Е = 6

И = Г + Е = 8

Ж = Е + И = 13

Л = Д + Е + Ж = 24

К = Л = 24

М = Л + К = 48

П = К + М = 72

Р = М = 48

С = М + П + Р = 168

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

Ответ: 168.

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

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

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

А = 1

Б = А = 1

Г = А = 1

В = А + Г = 2

Е = В + Г = 3

Д = Б + В + Е = 6

И = Г + Е = 4

Ж = Е + И = 7

Л = Ж = 7

К = Л = 7

М = Ж + Л + К = 21

Н = М = 21

П = К + М = 28

Р = М + Н = 42

С = М + П + Р = 91

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

Ответ: 91.

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

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

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

А = 1

Б = А = 1

Г = А = 1

В = А + Г = 2

Е = В + Г = 3

И = Г + Е = 4

Ж = И = 4

Л = Ж = 4

К = Л = 4

М = И + Ж + Л + К = 16

Н = И + М = 20

П = К + М = 20

Р = М + Н = 36

С = М + П + Р = 72

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

Ответ: 72.

Ре­ше­ние. По­счи­та­ем все марш­ру­ты, ис­клю­чив лиш­ние:

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

Ответ: 16.

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

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

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

А = 1

Б = А = 1

Г = А = 1

В = А + Г = 2

Е = В + Г = 3

Д = Б + В + Е = 6

Л = Д + Е = 9

К = Л = 9

М = Л = 9

Н = М = 9

П = К = 9

Р = Н = 9

С = К + Л + М + П + Р = 45

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

Ответ: 45.

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

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

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

А = 1

Б = А = 1

Г = А = 1

В = А + Г = 2

Е = В + Г = 3

И = Г + Е = 4

Ж = Е + И = 7

М = Ж = 7

Н = М = 7

Р = Н = 7

С = М + Р = 14

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

Ответ: 14.

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

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

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

А = 1;

Г = А = 1;

В = А + Г = 2;

Е = В + Г = 3;

И = Е = 3;

Л = Е = 3;

Ж = Е + И + Л = 9;

Н = И + Ж = 12;

М = Ж + Н = 21;

Р = М = 21;

С = М + Р = 42.

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

Ответ: 42.

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

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

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

А = 1;

Г = А = 1;

В = А + Г = 2;

Б = А + В = 3;

Д = Б + В = 5;

Л = Д = 5;

Ж = Л = 5;

К = Д + Л + Ж = 15;

Н = Ж = 5;

М = Ж + К + Н = 25;

Р = М = 25;

С = М + Р = 50.

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

Ответ: 50.

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

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

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

В = 1

А = В = 1

Б = А + В = 2

Г = А + В = 2

Д = Б + В = 3

И = Д = 3

Л = Д + И + Е = 7

К = Л = 7

Ж = Г + Л + К = 16

Е = Г + Д + Ж = 21

Ответ: 21.

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

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

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

Ж  =  1;

К  =  Ж  =  1;

М  =  К + Ж  =  2;

И  =  К + Ж  =  2;

Е  =  И  =  2;

Л  =  М + Ж  =  3;

Г  =  Л  =  3;

Б  =  Е  =  2;

А  =  Б  =  2;

В  =  Г + А  =  5;

Д  =  Г + В + А + Е  =  12.

Ответ: 12.

При­ме­ча­ние.

Марш­ру­ты Е − Ж и А − Е в ре­ше­нии не учи­ты­ва­ем, так как они про­хо­дят через на­се­лен­ные пунк­ты, ко­то­рые уже по­се­ща­ли по до­ро­ге.

Ре­ше­ние. По­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из пунк­тов:

Ж  =  1 (на­чаль­ный пункт);

Л  =  Ж  =  1;

М  =  Ж + К  =  2;

Л  =  Ж + М  =  3;

И  =  К + Ж  =  2;

Е  =  И  =  2;

Б  =  Е  =  2;

А  =  Б  =  2;

Г  =  Л  =  3;

В  =  А + Г  =  5;

Д  =  Г + В + А + Е  =  12;

Ж  =  Д + Е  =  14 (ко­неч­ный пункт).

При­ме­ча­ние. До­ро­гу А−Е не рас­смат­ри­ва­ем, так как эта до­ро­га прой­дет через уже по­се­щен­ный пункт.

Ответ: 14.

Ре­ше­ние. По­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из пунк­тов:

Ж  =  1 (на­чаль­ный пункт);

Л  =  Ж  =  1;

М  =  Ж + К  =  2;

Л  =  Ж + М  =  3;

И  =  К + Ж  =  2;

Е  =  И  =  2;

Б  =  Е  =  2;

А  =  Б  =  2;

Г  =  Л  =  3;

В  =  А + Г  =  5;

Д  =  Г + В + А + Е  =  12;

Ж  =  Д + Е  =  14 (ко­неч­ный пункт).

Ответ: 17.

При­ме­ча­ние.

До­ро­гу А−Е не рас­смат­ри­ва­ем, так как эта до­ро­га прой­дет через уже по­се­щен­ный пункт.

Ре­ше­ние. По­счи­та­ем по­сле­до­ва­тель­но ко­ли­че­ство путей до каж­до­го из пунк­тов:

Д  =  1 (на­чаль­ный пункт);

Далее есть два ва­ри­ан­та: до­ро­га Д - Ж и Д - В.

Рас­смот­рим ва­ри­ант до­ро­ги Д - Ж:

Ж  =  Д  =  1;

К  =  Ж  =  1;

М  =  Ж + К  =  2;

Л  =  М  =  2;

И  =  К  =  2;

Е  =  И  =  2;

Б  =  В  =  2;

А  =  Б  =  2;

В  =  А  =  2;

Г  =  В + Л  =  4;

Д  =  Г + А  + Б  + Е  =  10 (ко­неч­ный пункт)

Рас­смот­рим ва­ри­ант до­ро­ги Д - В:

В  =  Д  =  1;

Г  =  В  =  1;

Ж  =  Г  =  1;

К  =  Ж  =  1;

И  =  К + Ж  =  2;

Е  =  И  =  2;

Б  =  В  =  2;

А  =  Б  =  2;

Г  =  В + Л  =  4;

Д  =  Г + А  + Б  + Е  =  7 (ко­неч­ный пункт)

Всего дорог, ко­то­рые на­чи­на­ют­ся и за­кан­чи­ва­ют­ся в пунк­те Д, не со­дер­жат этот пункт в ка­че­стве про­ме­жу­точ­но­го и про­хо­дят через любой дру­гой пункт не более од­но­го раза: 10 + 7 = 17

Ответ: 17.

Ре­ше­ние. За­ме­тим, что пути Б–Д, Б–Е и Ж–Л можно не рас­смат­ри­вать. Если сна­ча­ла от­пра­вить­ся из пунк­та Е в точку В, то тогда мы по­лу­чим, что в пункт Г ведет 1 до­ро­га, в пункт И ведут 2 до­ро­ги, в пункт Н ведут 2 до­ро­ги, в пункт М ведут 4 до­ро­ги, тогда в пункт Ж ведут 4 + 1  =  5 дорог. Если же сна­ча­ла от­пра­вить­ся в пункт Л, то в К ведет 1 до­ро­га, в пункт Д  — 2, в пункт А  — 2, в пункт В  — 2, в Г  — 2, в И  — 4, в Н  — 4, в М  — 8. Тогда в пункт Ж ведут 2 + 8  =  10 дорог. Не за­бу­дем учесть путь Е–Ж, по­лу­ча­ем, что всего путей: 5 + 10 + 1  =  16.

Ответ: 16.

Ре­ше­ние. Из­ба­вим­ся от лиш­них дорог, как по­ка­за­но на ри­сун­ке:

Если от­пра­вить­ся сна­ча­ла в пункт В, то в пункт Г ведет 1 до­ро­га, в И  — 2, в Н  — 2, в М  — 4, в Л  — 4, в К  — 4, в Д  — 8, в А  — 8, в Б  — 16, тогда в Е ведут 16 + 8  =  24 до­ро­ги.

Если же от­пра­вить­ся сна­ча­ла в пункт Л, то в пункт К ведет 1 до­ро­га, в Д  — 2, в А  — 2, в Б  — 4, тогда в Е ведут 4 + 2  =  6 дорог.

Зна­чит, всего в Е ведут 24 + 6  =  30 дорог.

Ответ: 30.

Ре­ше­ние. За­ме­тим, что до­ро­ги К–Д и Ж–Г можно не учи­ты­вать, так как они при­во­дят к по­вто­ре­нию пунк­тов про­хож­де­ния. Тогда, по­счи­та­ем ко­ли­че­ство путей до каж­до­го из го­ро­дов:

Д  =  Е  =  1.

А  =  Д + Е  =  2.

Б  =  А  =  2.

В  =  Б  =  2.

Г  =  В  =  2.

И  =  Г  =  2.

Н  =  И  =  2.

М  =  И + Н  =  4.

Л  =  М  =  4.

К  =  Л  =  4.

Ж  =  В + М + Л + К  =  14.

Ис­ко­мое ко­ли­че­ство путей: 14 + 2  =  16.

Ответ: 16.

Ре­ше­ние. За­ме­тим, что до­ро­гу В–Е можно не учи­ты­вать, так как она при­во­дит к по­вто­ре­нию пунк­тов про­хож­де­ния. Тогда, по­счи­та­ем ко­ли­че­ство путей до каж­до­го из го­ро­дов:

Е  =  Ж  =  1.

Д  =  К + Е  =  1 + К.

А  =  Д + Е  =  2 + К.

Б  =  А  =  2 + К.

В  =  Б  =  2 + К.

Г  =  Ж + В − К  =  3.

И  =  Г  =  3.

Н  =  И  =  3.

М  =  Н + И  =  6.

Л  =  М  =  6.

К  =  Л  =  6.

За­ме­тим, что из по­лу­чен­ных К для Д, А, Б и В под­хо­дят толь­ко 2 до­ро­ги, ко­то­рые не ведут к по­вто­рам. Итого, по­лу­ча­ем:

Д  =  3.

А  =  4.

В  =  Б  =  А  =  4.

Итак, ис­ко­мое ко­ли­че­ство путей: 6 + 6 + 6 + 4  =  22.

Ответ: 22.

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

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

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

А  =  1

Б  =  А  =  1

В  =  А  =  1

Д  =  А + Б + В  =  3

Ж  =  В  =  1

И  =  Ж + В + Д  =  5

Г  =  А  =  1

Е  =  А + Г  =  2

З  =  Е + Г  =  3

К  =  З  =  3

Л  =  К  =  3

М  =  К + л  =  6 (До­ро­гу Е  — М не учи­ты­ва­ем, она не про­хо­дит через пункт К)

Н  =  И + М  =  11 (До­ро­гу Ж  — Н не учи­ты­ва­ем, она не про­хо­дит через пункт И).

Ответ: 11.

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

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

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

А  =  1

Б  =  А  =  1

В  =  А  =  1

Д  =  А + Б  =  2

И  =   Д  =  2 (Марш­ру­ты через го­ро­да В и Ж не про­хо­дят через город Д, по­это­му их не учи­ты­ва­ем)

Е  =  А  =  1

З  =  Е  =  1 (До­ро­гу А - З и марш­ру­ты через город Г не учи­ты­ва­ем, они не про­хо­дят через пункт Е)

К  =  З  =  1

Л  =  К  =  1

М  =  Е + З + Л  =  3

Н  =  И + М  =  5

Ответ: 5.

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

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

А = 1.

Б = А = 1.

Е = Б = 1.

В = Б + Е = 2.

Ж = В = 2.

М = Ж = 2.

Г = В = 2.

И = Г + В + М = 6.

Н = И = 2.

Ко­ли­че­ство раз­лич­ных путей, ко­то­рые на­чи­на­ют­ся в пунк­те А, за­кан­чи­ва­ют­ся в пунк­те Н и про­хо­дят через любой пункт не более од­но­го раза равно 6.

Ответ: 6.

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

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

Н = 1.

М = Н = 1.

И = М = 1.

Ж = И = 1.

Е = М + Ж = 2.

Л = М + Е = 3.

К = Л = 3.

Д = К + Л + Е = 8.

А = Д = 8.

Ко­ли­че­ство раз­лич­ных путей, ко­то­рые на­чи­на­ют­ся в пунк­те Н, за­кан­чи­ва­ют­ся в пунк­те А и про­хо­дят через любой пункт не более од­но­го раза равно 8.