Файл: Контрольная 2017 (Часть 3. Элементы теории графов в информатике).doc
Добавлен: 20.10.2018
Просмотров: 619
Скачиваний: 14
Задание 1
Задание 2
Задание 3
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.
|
|
A |
B |
C |
D |
E |
F |
Z |
|
A |
|
4 |
6 |
|
|
|
30 |
|
B |
|
|
3 |
4 |
|
|
|
|
C |
|
|
|
11 |
|
|
27 |
|
D |
|
|
|
|
4 |
7 |
10 |
|
E |
|
|
|
|
|
4 |
8 |
|
F |
|
|
|
|
|
|
2 |
|
Z |
29 |
|
|
|
|
|
|
Сколько существует таких маршрутов из A в Z, которые проходят через 6 и
более населенных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.
Задание 4
Задание 5
На
рисунке – схема дорог, связывающих
города А, Б, В, Г, Д, Е, Ж, И, К. По каждой
дороге можно двигаться только в одном
направлении, указанном стрелкой. Сколько
существует различных путей из города
А в
город К, проходящих через город Д?
Задание 6
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.
