На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в... | Яндекс.Репетитор

Задание#T4868

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

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

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

В ответе запишите целое число – длину пути в километрах.

Показать разбор и ответ

Указание:

Определите, сколько дорог выходит из каждого пункта.

Решение:

На схеме есть три пункта, из которых выходит по две дороги: , и . В таблице им соответствуют , и . Только из пункта обе дороги ведут в пункты, из которых выходит по четыре дороги. Значит, – это .

Из и выходит по дороги, значит, это пункты и (пока непонятно, в каком порядке), а и – это и (также непонятно, в каком порядке).

Поскольку граф симметричный, группу пунктов