КАК РЕШАТЬ 1 НОМЕР - ГРАФЫ

Теория графов

Граф — это математическая структура, представляющая собой совокупность объектов и связей между ними. Схема дорог в задании по сути является графом.

Элементы графа:

Вершина (узел): Основной элемент графа. Обозначает объект, в нашем случае город.

Ребро (связь): Линия, соединяющая две вершины. Обозначает связь, в нашем случае дорогу.

Смежные вершины: Две вершины, соединённые ребром.

Также в теории графов есть понятие веса ребра — числа, которое ставится в соответствие ребру и отражает какую-то характеристику. В нашем случае это длина дороги.

Таблица, которую нам дают симметрична по диагонали, потому что в ней отражается длина дороги из каждого пункта в другой (если дорога есть).

Пример решения задачи

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

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

Алгоритм решения:

Первым делом расставим возле каждого пункта количество дорог, которые к нему примыкают.

Пункты 2, 4 и 7 имеют по две дороги, смотрим на схему — это пункты А, В и Е.

Смежные к вершине А — С и В, 3 дороги и 2 дороги у них соответственно. Смежные к вершине В — D и A, 3 дороги и 2 дороги соответственно.

Выходит, что пока в таблице эти пункты не различаются, найдем их. Это пункты 2 и 4, потому что это пункты, из которых выходит две дороги, смотрим через таблицу с какими пунктами они связаны этими дорогами и видим цифры 2 и 3

Теперь надо узнать какой из них принадлежит А. Смотрим смежные с ними пункты, которые имеют три дороги, 6 и 1 (это либо С, либо D). Первый пункт связан с пунктами имеющими 3 и 2 дороги, значит это пункт C. Потому что по схеме пункт D связан с двумя пунктами имеющими 3 дороги. 

Соответственно путь между A и C по таблице это путь между 1 и 4, он равен 30.

Дело осталось за малым, найти G. Смотрим количество дорог у смежных пунктов С и видим еще не подписанный пункт–сосед с тремя дорогами — это наш пункт G под номером 5. Проверяем что у его смежных пунктов стоят тройки. Все верно, путь DG равен 8.

Ответ: AC + DG = 30 + 8 = 38