Тема 1. Графы – матрица смежности

1.02 Длина дороги между пунктами (таблица и граф)

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела графы – матрица смежности

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#136674Максимум баллов за задание: 1

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


	1	2	3	4	5	6	7	8

1		15			24			12

2	15						13

3					18	43

4						9		41

5	24		18					39

6			43	9			37

7		13				37

8	12			41	39

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

В ответе запишите целое число.

Показать ответ и решение

Подпишем кратность вершин на графе:

$PIC$

Из таблицы видно, что двухдорожные пункты – это 2, 3, 4, 7; трехдорожные – 1, 5, 6, 8.

Отсюда легко найти вершину $H$ , так как только этот пункт связан с тремя двухдорожными. Получаем, что вершишна $H$ имеет номер 6, так как он связан с номерами 3, 4 и 7.

Единственный двухдорожный пункт, который не связан с $H$ – пункт $E$ . Значит, его номер – 2.

Далее найдем вершину $F$ , так как она единственная выходит из $H$ и при этом связана не с трехдорожным пунктом, а с двухдорожным пунктом $E$ . Номер вершины $F$ – 7.

Из вершины $E$ можно попасть в вершину $G$ . Значит, $G$ имеет номер 1.

Теперь можно считать ответ: протяженность дороги между пунктами $G$ и $E$ равна 15, а между пунктами $F$ и $H$ – 37.

Сумма протяженностей равна:

15 +37 = 52

Ответ: 52