На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
| П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.