Использование графов при решении задач

1.

2.

2

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

Давайте обсудим
Какая связь между графом и таблицей на
рисунке?
?

13.

Задача 1. Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых приведена в таблице.
(Отсутствие числа в таблице означает, что прямой дороги между
пунктами нет). Постройте взвешенный граф.
13

14.

Задача 2. Между населёнными пунктами A, B, C, D, E построены
дороги, протяжённость которых приведена в таблице. Построить
взвешенный граф.
A
A
B
3
C
5
D
E
B
C
3
5
1
1
6
D
6
4
4
1
E
1
3
3
14

15.

Задача 3. Между населёнными пунктами A, B, C, D, E, F построены
дороги, протяжённость которых приведена в таблице. Построить
взвешенный граф.
15

16.

Задача 4. По взвешенному графу восстановить таблицу
Проверка:
16

17.

Задача 5. По взвешенному графу восстановить таблицу
17

18.

Задача 6. Между населёнными пунктами A, B, C, D, E, F
построены дороги, протяжённость которых (в километрах)
приведена в таблице. Определите длину кратчайшего пути между
пунктами B и C. Передвигаться можно только по дорогам,
протяжённость которых указана в таблице.
A
A
B
3
C
7
B
C
3
7
3
E
1
2
E
F
2
3
D
F
D
1
1
2
1
2
1) 9
2) 10
3) 11
4) 12
18

19.

Задача 7. В таблице приведена стоимость перевозок
между пятью железнодорожными станциями,
обозначенными буквами A, B, C, D и E. Укажите схему,
соответствующую таблице.
A
A
B
C
D
E
1)
B
1
C
4
1
4
D
E
1
3
2
3
1
2)
2
3)
4)
19

20.

20