Моделирование

 

Задача 1. Путешественник пришел в 08:00 на автостанцию населенного пункта КАЛИНИНО и обнаружил следующее расписание автобусов:

Пункт
отправления
Пункт
отправления
Время
отправления
Время
прибытия
МЫШКИНО КАЛИНИНО 08:15 09:10
КАЛИНИНО БУКОВОЕ 09:10 10:15
РАКИТИНО МЫШКИНО 10:00 11:10
РАКИТИНО КАЛИНИНО 10:05 12:25
РАКИТИНО БУКОВОЕ 10:10 11:15
КАЛИНИНО РАКИТИНО 10:15 12:35
КАЛИНИНО МЫШКИНО 10:20 11:15
БУКОВОЕ КАЛИНИНО 10:35 11:40
МЫШКИНО РАКИТИНО 11:25 12:30
БУКОВОЕ РАКИТИНО 11:40 12:40

Определите самое ранее время, когда путешественник сможет оказаться в пункте РАКИТИНО согласно этому расписанию.
                1)12:25                              2)12:30                               3)12:35                                4)12:40

Решение:   Изобразим данные таблицы в виде графа.

Введем обозначения:  К-Калинино, Р-Ракитино, Б-Буково, М-Мышкино

Построим граф, показывающий все пути из К в Р:

Есть 3-и пути:

1-й путь: К→ Р (10.15 -12.35). Путешественник прибыл в 12.35

2-й путь: К→ М(10.20 -11.15), М → Р (11.25 -12.30). Путешественник прибыл в 12.30

3-й путь: К→ Б (9.10 -10.15), Б → Р (11.40 -12.40). Путешественник прибыл в 12.40

Получаем самое раннее время прибытия: 12.30

Ответ:  2

 

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

  A B C D E F
A   2 4      
B 2   1   7  
C 4 1   3 4  
D     3   3  
E   7 4 3   2
F         2  

Определите длину кратчайшего пути между пунктами A и  F (при условии, что передвигаться можно только по построенным дорогам):              

1)  9                                2) 10                                           3)  11                           4) 12

Решение:   Изобразим данные таблицы в виде графа.

Имеем 3 варианта пути

A B E F   2 + 7 + 2 = 9

A C E F   4 + 4 + 2 = 10

A C D E F   4 + 3 + 3 + 2 = 12

Очевидно, что кратчайший путь = 9

Ответ:  1

 

Задача 3. На рисунке – схема дорог, связывающих населенные пункты A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из А в Н?

 Решение:   Построим граф.

 

Ответ:  9