Тема "Графы" является важной в курсе информатики и изучается в рамках раздела "Информационное моделирование". Самостоятельная работа включает два варианта по три задания в каждом: задача на подсчёт количества путей, анализ схемы, построение графа по его весовой матрице и определение оптимального маршрута. Приблизительное время выполнения: 15 минут.
1. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из
города А в город К?
Вариант 1
А
Б
В
Г
Д
И
Ж
К
Е
2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из
города А в город З?
А
Б
В
Г
Д
Е
З
Ж
3. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых
приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
4
6
43
A
B
C
D
E
F
Z
B
4
1
C
6
1
15
32
D
E
15
4
6
10
4
8
F
6
2
Z
43
32
10
8
2
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться можно
только по построенным дорогам).1. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге
можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных
путей из города А в город К?
Вариант 2
Е
Б
В
А
Г
Д
Ж
К
З
И
2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно
двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из
города А в город З?
А
Б
В
Г
Д
Е
З
Ж
3. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги, протяжённость которых
приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
4
6
3
3
A
B
C
D
E
F
Z
B
4
1
C
6
1
5
2
7
Z
3
3
2
7
1
0
8
2
D
E
F
5
4
8
1
0
4
1
8
8
1
2
Определите длину кратчайшего пути между пунктами A и Z (при условии, что передвигаться
можно только по построенным дорогам).
Ср Графы.docx
