Таблицы и графы. Решение задач

1.

2.

Взвешенный граф
Граф называется взвешенным, если его вершины или
рёбра
характеризуются
некоторой
дополнительной
информацией - весами вершин или рёбер.
90
80
C
D
70
60
B
E
50
A
90
Протяжённость дорог в километрах

3.

Таблицы и графы
Таблица «Схема дорог»
Взвешенный граф
Одной и той же таблице могутAсоответствовать
B
C
D графы,
E
внешне не похожие друг на друга
80
C
A
90
90
50
D
Таблица «Схема дорог»
70
60
B
A
B
A 50
B
C
50
A
50
90
C
DE E
90
90
90
B
C
50
60
90
DA
E
80
50 «Схема
90 дорог»
Граф
90
90
80
60
C
80
70
60
60
70
80
D
Если между парой населённых пунктов существует дорога,
90
70
тоD в ячейку 80
на пересечении
соответствующих
строки
и
70
EПустые клетки
B
столбца
записывается
число,
равное
её
длине.
E 90
60 70
в таблице означают, что дорог между соответствующими
населёнными пунктами нет.

4.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в
таблице содержатся сведения о длинах этих дорог (в километрах).
П1
П1
П2
П2
П3
45
П4
45
40
40
П5
П6
П7
60
20
15
55
П7
55
15
10
П6
10
П3
П4
П5
60
35
55
20
35
55
45
45
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными
обозначениями на графе. Определите, какова длина дороги из пункта В в
пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

5.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице
содержатся сведения о длинах этих дорог (в километрах).
П1
П1
П2
П2
П3
45
П4
45
40
40
П5
П6
П7
60
20
15
55
П7
55
15
10
П6
10
П3
П4
П5
60
35
55
20
35
55
45
45
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями на
графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе
запишите целое число – так, как оно указано в таблице.

6.

На рисунке схема дорог Н-ского района изображена в виде графа, в
таблице содержатся сведения о длине этих дорог (в километрах).
П1
П1
П2
П3
15
15
П3
П4
П2
П4
П5
25
24
20
22
12
13
24
П7
13
12
18
П8
18
25
П6
П7
20
П5
П8
П6
22
16
17
15
16
17
15
Так как таблицу и схему рисовали независимо друг от друга, нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями
на графе. Определите длину дороги из пункта Е в пункт Л. В ответе запишите
целое число.

7.

На рисунке справа схема дорог Н-ского района изображена в виде графа, в
таблице содержатся сведения о длинах этих дорог (в километрах).
П1
П1
П2
П2
П3
45
П4
45
40
40
П5
П6
П7
60
20
15
55
П7
55
15
10
П6
10
П3
П4
П5
60
35
55
20
35
55
45
45
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными
обозначениями на графе. Определите, какова длина дороги из пункта В в
пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

8.

На рисунке справа схема дорог Н-ского района изображена в виде графа; в
таблице слева содержатся сведения о протяжённости каждой из этих дорог (в
километрах).
П1
П1
П2
П2
П3
П4
10
10
20
П3
П5
П6
8
5
12
4
П4
20
П5
8
П6
5
12
4
15
15
7
7
Так как таблицу и схему рисовали независимо друг от друга, то нумерация
населённых пунктов в таблице никак не связана с буквенными обозначениями на
графе. Определите, какова длина дороги из пункта Б в пункт В. В ответе
запишите целое число — так, как оно указано в таблице.