Графы_2_8-9 класс

Задача 1: Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице:

	A	B	C	D	E	F
A	-	15	10	-	12	-
B	15	-	-	8	-	13
C	10	-	-	-	-	16
D	-	8	-	-	-	-
E	12	-	-	-	-	11
F	-	13	16	-	11	-

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

Решение:

1.    Строим граф, вершинами которого являются населенные пункты, а рёбрами – дороги между ними:

Опишем и сравним пути:

А-B-F=15+13=28

A-C-F=10+16=26

A-E-F=12+11= 23.

Ответ: 23.

Задача 2:

Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет ровна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время. Сколько минут он планирует пробыть в пути?

Решение:

1)               (15 + 25) : 16 = 2,5 (ч) – время в пути A-B-E

2)               (19 + 17) : 18 = 2 (ч)  – время в пути A-D-E

3)               (11 + 34) : 20 = 2,25 (ч) – время в пути A-С-E

4)               2 < 2,25 < 2,5

5)               2 (ч) = 120 (мин)

Ответ: 120 минут он планирует пробыть  пути.