1. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 

A B C D E F
A 3 4 4 16
B 3 5
C 4 2
D 4 5 2 6 10
E 6 3
F 16 10 3

 

Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.

Решение.

Найдём все маршруты, удовлетворяющие условию, посчитаем расстояние и выберем кратчайшее.

 

A-B-D-F 18

A-B-D-E-F 17

A-C-D-F 16

A-C-D-E-F 15

A-D-F 14

A-D-E-F 13

A-F 16

 

Кратчайшим является A-D-E-F с длиной 13.

2. На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

 

 

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и G на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице. Необходимо определить номера населенных пунктов A и G. Из F ведут шесть дорог. Таким образом F — 3. Заметим, что из пунктов A и G нет дороги в населённые пункты C и E, из которых идут 2 дороги. Следовательно, пункты 6 и 7 это либо A, либо G.

 
Ответ: 67.

3. На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Г в пункт Е. В ответе запишите целое число.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице.

Из Г ведут четыре дороги. Только из пункта П8 ведут четыре дороги, следовательно, пункт П8 — это и есть Г.

Из Е ведут три дороги. Из пунктов П1, П3, П5, П6 также ведут три дороги. Заметим, что из Е дороги идут в пункты с двумя, четырьмя и двумя дорогами. Сопоставляя с таблицей, получим, что Е соответствует пункту П1.

 

Длина дороги из П1 в П8 равна 18.

 
 
Ответ: 18.

4. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 4 6 16
B 2 5
C 4 1
D 6 5 1 4 9
E 4 6
F 16 9 6

 

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D, F.

Из пункта B можно попасть в пункт D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—D—E—F: длина маршрута 17 км.

 

A—B—D—F: длина маршрута 16 км.

 

A—C—D—E—F: длина маршрута 15 км.

 

A—C—D—F: длина маршрута 14 км.

 

A—D—E—F: длина маршрута 16 км.

 

A—D—F: длина маршрута 15 км.

 

A—F: длина маршрута 16 км.

 
Ответ: 14.

5. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта Г в пункт Ж, если передвигаться можно только по указанным дорогам. В ответе запишите целое число — длину пути в километрах.

Решение.

Заметим, что Е — единственная вершина степени 2. Следовательно, Е соответствует П4. С вершиной Е соединена вершина Ж степени 4. Значит, Ж соответствует П5. Вершина Г — единственная вершина степени 3, которая соединена с вершиной Е. Следовательно, Г соответствует П1. А — единственная вершина степени 4, которая соединена с вершиной Г. А соответсвует П3. Д — единственная вершина степени 3, которая соединена с вершинами А и Г. Следовательно, Д соответсвует П2. Далее рассмотрим два варианта:

1. В соответсвует П6, а Б соответствует П7. Тогда кратчайшее расстояние из пункта Г в пункт Ж равняется 23.

2. В соответсвует П7, а Б соответствует П6. Тогда кратчайшее расстояние из пункта Г в пункт Ж равняется 23.

 
Ответ: 23.

6. На рисунке схема дорог изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами. Отсутствие звёздочки означает, что такой дороги нет.


 

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

Пример. Пусть населённым пунктам Д и Е соответствуют номера П1 и П2. Тогда в ответе нужно написать 12.

Решение.

Заметим, что Е — единственная вершина степени 2, которая связана с вершинами третьей степени Д и К, связаными с остальными вершинами степени 2. Значит, Е соответствует П5. Далее рассмотрим два варианта:

1. Пусть Д соответствует П4, а К соответствует П7. В — единственная вершина степени 3, в которую есть дорога из Д, следовательно, В соответствует П2. Б — единственная вершина степени 3, в которую есть дорога из К, следовательно, Б соответствует П6.

2. Пусть Д соответствует П7, а К соответствует П4. В — единственная вершина степени 3, в которую есть дорога из Д, следовательно, В соответствует П6. Б — единственная вершина степени 3, в которую есть дорога из К, следовательно, Б соответствует П2.

Таким образом, населённым пунктам Б и В соответствуют П2 и П6.

 
Ответ: 26.

7. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 4 6 16
B 2 3
C 4 3
D 6 3 3 4 9
E 4 3
F 16 9 3

 

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D, F.

Из пункта B можно попасть в пункт D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—D—E—F: длина маршрута 12 км.

 

A—B—D—F: длина маршрута 14 км.

 

A—C—D—E—F: длина маршрута 14 км.

 

A—C—D—F: длина маршрута 16 км.

 

A—D—E—F: длина маршрута 13 км.

 

A—D—F: длина маршрута 15 км.

 

A—F: длина маршрута 16 км.

8. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

 

П1 П2 П3 П4 П5 П6 П7
П1 4 5
П2 12 9
П3 4 3
П4 12 17 10
П5 17 13
П6 5 10 13 7
П7 9 3 7

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта Г в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах.

ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.

Решение.

1) Д — единственная вершина, степень которой 4, значит, Д соответствует П6.

2) Можно заметить, что есть два населённых пунктов с тремя дорогами и четыре с двумя. Из этого можно сделать вывод: П4 и П7 это, либо Б, либо В, а населённые пункты П1, П3, П2 и П5 это Е, Г, А или К. Исходя из таблицы видно, что между П1 и П5 дороги нет, зато есть дорога, идущая вокруг Д(П6): П5—П4—П2—П7—П3—П1. Отсюда получаем: Е и К это, либо П5, либо П1. Из П5 есть дорога в П4, далее, в свою очередь есть дорога в Д(П6), а из П1 есть дорога в П3, но потом нет дороги в Д(П6).

3) Таким образом, П5 — К, П1 — Е. А если учесть цепочку П5—П4—П2—П7—П3—П1, то можно найти все оставшиеся: Г — П3, Б — П7, А — П2, В — П4.

Тогда ответ: кратчайший путь из Г в Д равен 9 км: Г(П3)—Е(П1)—Д(П6).

 
Ответ:9.

9. Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F Z
A 4 10 15 34
B 4 9 6
C 10 9 2
D 15 6 2 3 11 15
E 3 8 13
F 11 8 4
Z 34 15 13 4

 

Определите длину кратчайшего пути между пунктами А и Z (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в Z и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D и Z.

Из пункта B можно попасть в пункты C, D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F и Z.

Из пункта E можно попасть в пункты F и Z.

Из пункта F можно попасть в пункт Z.

 

Путь A-B-С — 13 км, а A-С — 10 км. Следовательно, варианты, начинающиеся с A-B-СA-B-С не рассматриваем.

 

A-Z: Длина маршрута 34 км.

 

A-D-Z: Длина маршрута 30 км.

 

A-D-F-Z: Длина маршрута 30 км.

 

A-D-E-Z: Длина маршрута 31 км.

 

A-D-E-F-Z: Длина маршрута 30 км.

 

A-B-D-Z: Длина маршрута 25 км.

 

A-B-D-F-Z: Длина маршрута 25 км.

 

A-B-D-E-Z: Длина маршрута 26 км.

 

A-B-D-E-F-Z: Длина маршрута 25 км.

 

A-C-D-Z: Длина маршрута 27 км.

 

A-C-D-E-Z: Длина маршрута 28 км.

 

A-C-D-F-Z: Длина маршрута 27 км.

 

A-C-D-E-F-Z: Длина маршрута 27 км.

 

Видно, что кратчайший путь равен 25 км.

10. На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

 

 

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и C на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение.

Заметим, что D — единственная вершина степени 2, которая связана с вершинами степени 3 — B и C, связаными с остальными вершинами степени 2. Значит, D соответствует П4. Таким образом, населённым пунктам B и C соответствуют пункты П2 и П6.

 
Ответ: 26.

11. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.


 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину пути из пункта Б в пункт В, если передвигаться можно только по указанным дорогам. В ответе запишите целое число — длину пути в километрах.

Решение.

Заметим, что Е — единственная вершина степени 1. Следовательно, Е соответствует П3. С вершиной Е соединена вершина Д степени 2. Значит, Д соответствует П4. Вершина В — единственная вершина степени 4, которая соединена с вершиной Д. Следовательно, В соответствует П5. Г — единственная вершина степени 3, которая соединена с вершиной Д. Г соответсвует П6. А — единственная вершина степени 2, следовательно, А соответсвует П2. Таким образом, Б соответствует П1. Значит, длина пути из пункта Б в пункт В равняется 15.

 
Ответ: 15.

12. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 3 4 4 16
B 3 5
C 4 2
D 4 5 2 6 10
E 6 3
F 16 10 3

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D, F.

Из пункта B можно попасть в пункт D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—D—E—F: длина маршрута 17 км.

 

A—B—D—F: длина маршрута 18 км.

 

A—C—D—E—F: длина маршрута 15 км.

 

A—C—D—F: длина маршрута 16 км.

 

A—D—E—F: длина маршрута 13 км.

 

A—D—F: длина маршрута 14 км.

 

A—F: длина маршрута 16 км.

13. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными пунктами (звездочка означает, что дорога между соответствующими городами есть).

 

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населенных пунктов A и G в таблице. В ответе запишите числа в порядке возрастания без разделителей.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице. Нам необходимо определить номера населенных пунктов A и G. Из В ведут пять дорог. Таким образом В — 4. Проверим первый пункт: из первого пункта есть дорога во второй, а из второго есть путь в три пункта. Получается, что D — 2. Следовательно, 1, 2 и 6 номера не подходят. Остаются два населенных пункта 3 и 5. Это и есть ответ. Записываем ответ в порядке возрастания без разделителей.

 
Ответ: 35.

14. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог (в километрах).

 

П1 П2 П3 П4 П5 П6 П7 П8
П1 15 20 18
П2 15 25
П3 25 24 22
П4 20 12
П5 13 16 17
П6 24 13 15
П7 12 16
П8 18 22 17 15

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Е в пункт Л. В ответе запишите целое число.

Решение.

Сопоставим таблицу и схему дорог.

Из пункта Г ведёт четыре дороги, только из пункта П8 ведёт четыре дороги, значит, П8 и есть пункт Г.

Из пункта В ведёт две дороги, каждая в пункт, имеющий три дороги. Из пункта П2 также ведут ведут две дороги в пункты с тремя дорогами, значит, пункт П2 и есть пункт В.

Из пункта Б ведёт три дороги, одна — в пункт с тремя дорогами, вторая — в пункт с четырьмя дорогами, третья — в пункт с тремя дорогами. Из пункта П6 дороги идут аналогично. Значит, пункт П6 и есть пункт Б.

Из пункта А ведут дороги в пункты Б, Г и В. Видим из таблицы, что из пункта П3 дороги ведут в Б, Г и В, значит, П3 и есть пункт А.

Из пункта Д ведут дороги в Б, Г и К. Из таблицы видим, что из пунктов П3 и П5 идут дороги в Б и Г, известно, что пункт П3 — А, значит, П5 и есть пункт Д.

Из пункта К ведут две дороги, одна — в пункт Д, другая — в пункт Л, имеющий две дороги. Из таблицы видим, что аналогичные пути идут из пункта П7, значит, П7 и есть пункт К, и П4 — пункт Л.

Из пункта Г ведут четыре дороги — в А, Б, Д и Е, известно, что А — пункт П3, Б — пункт П6, Д — пункт П5, следовательно, П1 и есть пункт Е.

Из таблицы находим, что длина дороги из пункта Е в пункт Л равна 20.

 
Ответ: 20.

15. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

П1 П2 П3 П4 П5 П6 П7
П1 10 12
П2 10 8
П3 11 15
П4 5
П5 11 13 6
П6 15 5 13
П7 12 8 6

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта E в пункт K. В ответе запишите целое число. ВНИМАНИЕ! Длины отрезков на схеме не отражают длины дорог.

Решение.

1) Из В идет единственная дорога, значит, В соответствует П4.

2) Единственная дорога из В идет в Б, а т. к. единственная дорога из П4 идет в П6, значит, Б соответствует П6.

3) К — единственная вершина, имеющая два ребра и ведущая при этом в Б, значит, П3 соответствует К.

4) Е — единственная вершина, имеющая ребро с Б и К, значит, Е соответствует П5.

Тогда ответ — дорога из П3 в П5, которая равна 11.

 
Ответ: 11.

16. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 12
B 2 2 4
C 2 1
D 4 1 3 5
E 3 3
F 12 5 3

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

 

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, F.

Из пункта B можно попасть в пункт C, D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—C—D—E—F: длина маршрута 11 км.

A—B—C—D—F: длина маршрута 10 км.

A—B—D—E—F: длина маршрута 12 км.

A—B—D—F: длина маршрута 11 км.

A—F: длина маршрута 12 км.

 
Ответ: 10.

17. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 17
B 2 4 8
C 4 5
D 8 5 3 6
E 3 2
F 17 6 2

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, F.

Из пункта B можно попасть в пункт C, D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—C—D—E—F: длина маршрута 16 км.

 

A—B—C—D—F: длина маршрута 17 км.

 

A—B—D—F: длина маршрута 16 км.

 

A—F: длина маршрута 17 км.

 

A—B—D—E—F: длина маршрута 15 км, кратчайшая.

 
Ответ: 15.

18. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

П1 П2 П3 П4 П5 П6 П7
П1 59 22 27
П2 59 24 44 10 21
П3 24 25 9
П4 22 44 8 32
П5 10 25
П6 27 8 11
П7 21 9 32 11

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Г в пункт К. В ответе запишите целое число.

Решение.

На карте есть только один пункт с 5 дорогами, это Г. В таблице же это П2.

На карте есть только один пункт с 2 дорогами, это Б. В таблице же это П5.

К — пункт, из которого выходит 3 дороги, который связан с Г, но не связан с Б. Из всех пунктов в таблице только П1 под это подходит.

Таким образом, Г = П2, К = П1. Длина дороги между П2 и П1 — 59.

19. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 4 6 16
B 2 3
C 4 3
D 6 3 3 4 9
E 4 3
F 16 9 3

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D, F.

Из пункта B можно попасть в пункт D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—D—E—F: длина маршрута 12 км.

 

A—B—D—F: длина маршрута 14 км.

 

A—C—D—E—F: длина маршрута 17 км.

 

A—C—D—F: длина маршрута 16 км.

 

A—D—E—F: длина маршрута 13 км.

 

A—D—F: длина маршрута 15 км.

 

A—F: длина маршрута 16 км.

20. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

П1 П2 П3 П4 П5 П6 П7
П1 45 10
П2 45 40 55
П3 15 60
П4 10 40 20 35
П5 15 55
П6 55 60 20 55 45
П7 35 45

 
 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Решение.

Пункт Г − единственный пункт с тремя дорогами, значит, ему соответствует П2, а пункт Е − единственный с четырьмя дорогами, значит, ему соответствует П4.

 

Длина дороги из П2 в П4 равна 40.

 
Ответ: 40.

21. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

 

A B C D E F
A 7 4 8 16
B 7 3
C 4 3
D 8 3 3 2 3
E 2 5
F 16 3 5

 

 

Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт E. Передвигаться можно только по указанным дорогам.

Решение.

Рассмотрим все возможные пути. Кратчайшим окажется путь A-C-D-F длиной 10.

22. На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице.

Из Б ведут три дороги. Из пунктов П1, П3, П5, П6 также ведут три дороги. Заметим, что из Б дороги идут в пункты с тремя, четырьмя и тремя дорогами. Сопоставляя с таблицей, получим, что Б соответствует пункту П6.

Из Г ведут четыре дороги. Только из пункта П8 ведут четыре дороги, следовательно, пункт П8 — это и есть Г.

Длина дороги из П6 в П8 равна 15.

 
Ответ: 15.

23. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F Z
A 4 9 37
B 4 3
C 9 3 11 27
D 11 4 7 10
E 4 8
F 7 2
Z 37 27 10 8 2

 

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

 

Решение.

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—C—D—E—Z, его длина равна 30 км. Теперь, начиная с конца маршрута, будем изменять населённые пункты:

 

A—B—C—D—F—Z: длина маршрута 27 км,

A—B—C—D—Z: длина маршрута 28 км.

 

Дальнейшее изменение населённых пунктов, через которые проходит маршрут, бессмысленно, поскольку длины маршрутов будут более 27 км. Следовательно, длина кратчайшего маршрута равна 27 км.

24. На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

 


 

П1 П2 П3 П4 П5 П6 П7
П1 11 5 12
П2 11 8 15 23
П3 5 8 10 7
П4 15 10
П5 12 10 11
П6 23 10
П7 7 11

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число — так, как оно указано в таблице.

Решение.

Заметим, что Д — единственная вершина степени 3, которая связана сразу с двумя вершинами степени 4. Значит, Д соответствует П1. Вершина В — единственная вершина степени 4, которая соединена с двумя вершинами степени 2. Следовательно, В соответствует П2. Вершина Г — единственная вершина степени 4, которая соединена с вершиной В. Значит, вершина Г соответствует П3.

Таким образом, длина дороги из пункта В в пункт Г равна 8.

 
Ответ: 8.

25. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.


 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина дороги DE меньше, чем длина дороги AB. Определите длину дороги AG. В ответе запишите целое число — длину дороги в километрах.

Решение.

Заметим, что E — единственная вершина степени 2, которая связана с двумя вершинами степени 3. Следовательно, E соответствует П4. Заметим, что A и B — единственные вершины степени 2, которые связаны друг с другом. Значит, A и B соответствуют П5 и П7. Далее рассмотрим два варианта:

1. A соответсвует П5, а B соответствует П7. Значит, C соответствует П2, а G соответствует П3. Тогда D соответсвует П6, а F соответсвует П1. Длина дороги DE равняется 8, а длина дороги AB равняется 9. Данный вариант удовлетворяет условию, длина дороги DE меньше, чем длина дороги AB. Длина дороги AG — 6.

2. B соответсвует П5, а A соответствует П7. Значит, C соответствует П3, а G соответствует П2. Тогда D соответсвует П1, а F соответсвует П6. Длина дороги DE равняется 15, а длина дороги AB равняется 9. Данный вариант не удовлетворяет условию, длина дороги DE больше, чем длина дороги AB.

 
Ответ: 6.

26. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 4
B 4 6 3 6
C 6 4
D 3 2
E 6 4 2 5
F 5

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Варианты маршрутов:

 

A-B-C-E-F. Длина маршрута 4 + 6 + 4 + 5 = 19

 

A-B-D-E-F. Длина маршрута 4 + 3 + 2 + 5 = 14

 

A-B-E-F. Длина маршрута 4 + 6 + 5 = 15

 

Видно, что кратчайший путь равен 14.

27. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.


 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, в какой пункт ведёт самая короткая дорога из пункта В.

Решение.

1. Г — единственная вершина степени 3, которая ведёт сразу в 3 вершины степени 4. Следовательно, Г соответствует П7, а Д соответствует П4.

2. Заметим, что вершина К — единственная вершина степени 2, которая связана дорогой с вершиной Д. Следовательно, К соответствует П3, а Б соответствует П1.

3. В — единственная вершина степени 4, которая связана дорогами одновременно и с вершиной Д, и с вершиной К. Из этого можно заключить, что В соответствует П2.

4. Заметим, что вершина В соединена дорогой с вершиной А, но не соединена дорогой с вершиной Е. Следовательно, А соответствует П5, а Е соответствует П6.

Таким образом, самая короткая дорога из пункта В ведёт в пункт Д.

 
Ответ: Д.

28. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице (отсутствие числа в таблице означает, что прямой дороги между пунктами нет):

 

A B C D E F
A 3 2 6 20
B 3 5
C 2 2
D 6 5 2 8 12
E 8 2
F 20 12 2

 

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, C, D, F.

Из пункта B можно попасть в пункт D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—D—E—F: длина маршрута 18 км.

 

A—B—D—F: длина маршрута 20 км.

 

A—C—D—E—F: длина маршрута 14 км.

 

A—C—D—F: длина маршрута 16 км.

 

A—D—E—F: длина маршрута 16 км.

 

A—D—F: длина маршрута 18 км.

 

A—F: длина маршрута 20 км.

29. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

П1 П2 П3 П4 П5 П6 П7
П1 10 12
П2 10 8
П3 11 15
П4 5
П5 11 13 6
П6 15 5 13
П7 12 8 6

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Е. В ответе запишите целое число. ВНИМАНИЕ! Длины отрезков на схеме не отражают длины дорог.

Решение.

1) Из В идет единственная дорога, значит, В соответствует П4.

2) Единственная дорога из В идет в Б, а т.к. единственная дорога из П4 идет в П6, значит, Б соответствует П6.

3) К — единственная вершина, имеющая два ребра и ведущая при этом в Б, значит, П3 соответствует К.

4) Е — единственная вершина, имеющая ребро с Б и К, значит, Е соответствует П5.

Тогда ответ — дорога из П5 в П6, которая равна 13.

 
Ответ: 13.

30. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых в километрах приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 5 10
B 2 1 2
C 1 3 2
D 3 1
E 5 2 2 3
F 10 1 3

 
 

Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам). В ответе укажите только число.

Решение.

Нарисуем граф.

 

Найдём все пути из A в F.

 

A→B→C→D→F — 7

A→B→C→E→F — 8

A→B→E→C→D→F — 10

A→B→E→F — 7

A→E→B→C→D→F — 12

A→E→C→D — 11

A→E→F — 8

A→F — 10

 

Кратчайшие пути имеют длину 7.

31. Между населёнными пунктами А, В, С, D, Е, F, Z построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F Z
A 8 47
B 8 5 7 17
C 5 3
D 7 3 2
E 17 2 2 6
F 2 3
Z 47 6 3

 

Определите длину кратчайшего пути между пунктами А и Z (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Варианты маршрутов:

 

A-B-C-D-E-F-Z. Длина маршрута 8 + 5 + 3 + 2 + 2 + 3 = 23.

 

A-B-C-D-E-Z. Длина маршрута 8 + 5 + 3 + 2 + 6 = 24.

 

A-Z. Длина маршрута 47.

 

A-B-D-E-F-Z. Длина маршрута 8 + 7 + 2 + 2 + 3 = 22.

 

A-B-D-E-Z. Длина маршрута 8 + 7 + 2 + 6 = 23.

 

A-B-E-F-Z. 8 + 17 + 2 + 3 = 30.

 

A-B-E-Z. 8 + 17 + 6 = 31.

 

Видно, что кратчайший путь равен 22.

32. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.

 

 

П1 П2 П3 П4 П5 П6 П7
П1 3 7 4
П2 15 2
П3 3 6
П4 6 8 12
П5 7 15 8 9
П6 4 9
П7 2 12

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах.

ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.

Решение.

Заметим, что Д — единственная вершина степени 4. Поэтому Д соответствует П5. Вершина Е — единственная вершина степени 2, которая соединена с вершиной Д степени 4 и вершиной Г степени 2. Следовательно, Е соответствует П2. Вершина Г — единственная вершина степени 2, которая соединена с вершиной Е. Значит, Г соответствует П7. Вершина Б — единственная вершина степени 3, которая соединена с вершиной Г. Следовательно, Б соответствует П4. Поскольку вершина Б степени 3 соответствует П4, вершина В степени 3 соответствует П1. Вершина А — единственная вершина степени 2, которая соединена с вершинами Б и В. Значит, вершина А соответствует П3, а К соответствует П6.

Тогда ответ: кратчайший путь из A в Д равен 10 км А(П3)—В(П1)—Д(П5).

 
Ответ:10.

33. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 4 11 33
B 4 4
C 11 4 7 11 20
D 7 13
E 11 8
F 33 20 13 8

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

В пункт F можно попасть из пунктов А, С, D, E.

В пункты Е и D можно попасть только пункта С.

В пункт С можно попасть из пунктов А и B.

В пункт В можно попасть из пункта А.

В пункты E и D можно попасть только из пункта С.

 

A-F. Длина маршрута 33.

 

A-C-F. Длина маршрута 11 + 20 =31.

 

A-С-E-F. Длина маршрута 11 + 11 + 8 = 30.

 

A-С-D-F. Длина маршрута 11 + 7 + 13 = 31.

 

Участок A-B-C может войти в три предыдущих пути, поэтому подставим его в самый короткий из них (A-С-E-F):

 

A-В-С-E-F. Длина маршрута 4 + 4 + 11 + 8 = 27.

 

Видно, что кратчайший путь равен 27.

34. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

 

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Б в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Решение.

Заметим, что Е — единственная вершина степени 1. Следовательно, Е соответствует П2. С вершиной Е соединена вершина Д степени 2. Значит, Д соответствует П6. Вершина В — единственная вершина степени 4, которая соединена с вершиной Д. Следовательно, В соответствует П1. Г — единственная вершина степени 3, которая соединена с вершиной Д, Г соответствует П4. А — единственная вершина степени 2, следовательно, А соответствует П3. Таким образом, Б соответствует П5. Значит, длина пути из пункта Б в пункт В равняется 15.

 
Ответ: 15.

35. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 

A B C D E F
A 2 4 8 16
B 2 3
C 4 3
D 8 3 3 2 3
E 2 5
F 16 3 5

 

Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Решение.

Найдём все варианты маршрутов, удовлетворяющих условию и выберем самый короткий.

 

A−C−D−E−F. Длина маршрута 14.

 

A−D−E−F. Длина маршрута 15.

 

Кратчайший путь равен 14.

 
Ответ: 14.

36. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

П1 П2 П3 П4 П5 П6 П7
П1 45 10
П2 45 40 55
П3 15 60
П4 10 40 20 35
П5 15 55
П6 55 60 20 55 45
П7 35 45

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

Решение.

Пункт В − единственный пункт с пятью дорогами, значит, ему соответствует П6, а пункт Г − единственный с тремя дорогами, значит, ему соответствует П2.

 

Длина дороги из П6 в П2 равна 55.

 
Ответ: 55.

37. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 2 17
B 2 4 8
C 4 5
D 8 5 5 6
E 5 2
F 17 6 2

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

Из пункта A можно попасть в пункты B, F.

Из пункта B можно попасть в пункт C, D.

Из пункта C можно попасть в пункт D.

Из пункта D можно попасть в пункты E, F.

Из пункта E можно попасть в пункт F.

 

A—B—C—D—E—F: длина маршрута 18 км.

A—B—C—D—F: длина маршрута 17 км.

A—B—D—E—F: длина маршрута 17 км.

A—B—D—F: длина маршрута 16 км.

A—F: длина маршрута 17 км.

38. На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

П1 П2 П3 П4 П5 П6 П7
П1 57 20 25
П2 57 22 42 8 21
П3 22 23 8
П4 20 42 7 33
П5 8 23
П6 25 7 9
П7 21 8 33 9

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта А в пункт Г. В ответе запишите целое число.

Решение.

На карте есть только один пункт с 5 дорогами, это Г. В таблице же это П2.

На карте есть только один пункт с 2 дорогами, это Б. В таблице же это П5.

А — пункт, из которого выходит 3 дороги, который связан и с Г, и с Б. Из всех пунктов в таблице только П3 под это подходит.

Таким образом, Г = П2, А = П3. Длина дороги между П2 и П3 — 22.

39. На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).

 
 


 
 

П1 П2 П3 П4 П5 П6 П7
П1 7
П2 7 8 3 4
П3 8 11 6
П4 11 5
П5 3 6 5 9
П6 4
П7 9

 

 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Г. В ответе запишите целое число — так, как оно указано в таблице.

Решение.

Сопоставим населённые пункты графа и населённые пункты в таблице.

Из А ведут три дороги. Только из пункта П3 ведут три дороги, следовательно, пункт П3 — это А.

Из К ведёт одна дорога — в Г. Заметим, из таблицы, что из пункта П7 ведёт одна дорога в пункт П5, следовательно, П7 — это пункт К, а П5 — пункт Г.

Таким образом, длина дороги из А в Г равна длине дороги из П3 в П5 — 6.

 
Ответ: 6.

40. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 1
B 1 6 3 6
C 6 4
D 3 2
E 6 4 2 3
F 3

 

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в F и выберем самый короткий.

 

A−B−C−E−F. Длина маршрута 1 + 6 + 4 + 3 = 14.

A−B−D−E−F. Длина маршрута 1 + 3 + 2 + 3 = 9.

A−B−E−F. Длина маршрута 1 + 6 + 3 = 10.

 

Кратчайший путь равен 9.

41. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

 

A B C D E F
A 1 4 3
B 4 5
C 4 2 1
D 1 2 2
E 4 1
F 3 5 2

 

Определите длину кратчайшего пути между пунктами A и B (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в B и выберем самый короткий.

 

В пункт B можно попасть из пунктов С и F.

В пункт F можно попасть из пунктов А и D.

В пункт С можно попасть из пунктов D и Е.

В пункты D и Е можно попасть из пункта А.

 

A-D-C-B. Длина маршрута 1 + 2 + 4 = 7.

 

A-E-C-B. Длина маршрута 4 + 1 + 4 = 9.

 

A-F-B. Длина маршрута 3 + 5 = 8.

 

A-D-F-B. Длина маршрута 1 + 2 + 5 = 8.

 

Видно, что кратчайший путь равен 7.

42. На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами.

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания указанные на графе буквенные обозначения пунктов от П1 до П7: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.

Решение.

Заметим, что Б — единственная вершина степени 5. Значит, Б соответствует П4. Заметим, что Д — единственная вершина степени 2, которая не соединена с вершиной Б. Следовательно, Д соответствует П5. Е — единственная вершина степени 3, которая соединена и с вершиной Д, и с вершиной Б, но при этом не соединена с другими вершинами степени 2. Значит, вершина Е соответствует П1. Вержина Ж — единственная вершина степени 3, которая соединена с вершиной Е. Значит, вершина Ж — это П6. Вершина В — единственная вершина степени 2, которая соединена с вершиной Ж. Следовательно, В соответствует П2. Таким образом, А соответствует П3, Г соответствует П7.

 
Ответ: ЕВАБДЖГ.

43. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.


 

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Укажите кратчайший путь из пункта А в пункт К. В ответе перечислите все населённые пункты, через которые проходит путь. Например, путь из Г в Д через Е и К записывается как ГЕКД.

Решение.

1. А — единственная вершина степени 1. Следовательно, пункт П3 соответствует вершине А.

2. Заметим, что вершина Б — единственная вершина степени 3, которая связана дорогой с вершиной А. Следовательно, Б соответствует П7, а К соответствует П6.

3. В — единственная вершина степени 4, которая связана дорогой с вершиной Б. Из этого можно заключить, что В соответствует П1.

4. Г — единственная вершина степени 3, которая связана дорогой с вершиной Б. Из этого можно заключить, что Г соответствует П5.

5. Д — единственная вершина степени 3, связанная дорогой с вершиной К, следовательно, Д соответствует П2, а Е соответствует П4.

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут А—Б—В—Г—Е—К, его длина равна 43 км. Теперь, начиная с конца маршрута, будем изменять населённые пункты:

А—Б—Г—Е—К: длина маршрута 41 км.

А—Б—В—Е—К: длина маршрута 40 км.

Дальнейшее изменение населённых пунктов, через которые проходит маршрут, бессмысленно, поскольку длины маршрутов будут более 40 км. Следовательно, длина кратчайшего маршрута равна 40 км.

 
Ответ: АБВЕК.

44. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.

 

A B C D E F G
A 5 12 25
B 5 8
C 2 4 5 10
D 12 8 2
E 4 5
F 5 5
G 25 10 5 5

 

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—C—E—G, его длина равна 24 км. Теперь, начиная с конца маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, C—E—G больше расстояния C—G, то заменяем участок маршрута C—E—G на C—G.

A—D—C—E—G: длина маршрута 23 км.

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

Ответ: 23 км.

45. Между населенными пунктами A, B, C, D, E, F, Z построены дороги, протяженность которых приведена в таблице (отсутствие числа в таблице означает, что прямой дороги между пунктами нет).

 

A B C D E F Z
A 4 6 27
B 4 1
C 6 1 2 11 20
D 2 4
E 4 2 5
F 11 2
Z 27 20 5

 

Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно только по построенным дорогам).

Решение.

Найдём все варианты маршрутов из A в Z и выберем самый короткий.

 

В пункт B можно попасть из пунктов A и C.

В пункт C можно попасть из пунктов A, B, D, F, Z.

В пункт D можно попасть из пунктов C и E.

В пункт E можно попасть из пунктов D, F, Z.

В пункт F можно попасть из пунктов C, E.

В пункт Z можно попасть из пунктов A, C, E.

 

Длина маршрута A-Z равна 27.

 

Длина маршрута A-B-C-Z равна 4+1+20= 25.

 

Длина маршрута A-C-Z равна 6+20 = 26.

 

Длина маршрута A-B-C-D-E-Z равна 4+1+2+4+5 = 16.

 

Длина маршрута A-C-F-E-Z равна 6+11+ 2+5 = 24.

 

Длина маршрута A-B-C-F-E-Z равна 4+1+11+2+5 = 23,

 

Кратчайший путь равен 16.

Задание №3 ЕГЭ информатика