Главная / Алгоритмы и дискретные структуры /
Введение в теорию графов / Тест 9
Введение в теорию графов - тест 9
Упражнение 1:
Номер 1
Обновление пометок происходит по формуле:
Ответ:
 (1) L(хi) = min [ L(хi), L(p) + C(p, хi) ]
 
 (2) L(хi) = min [ L(хi), L(p) - C(p, хi) ]
 
 (3) L(хi) = min [ L(хi), C(p, хi) ]
 
Номер 2
Для чего использую алгоритм Дейкстра?
Ответ:
 (1) для поиска максимального сильного подграфа 
 (2) для поиска кратчайших путей 
 (3) для поиска вершин графа, имеющих нечетную степень 
 (4) для построения матрицы смежности 
Номер 3
Обновление пометок на каждой итерации алгоритма Дейкстры происходит
Ответ:
 (1) для вершин графа, имеющих временные метки и входящих в прямое отображение для рассматриваемой вершины 
 (2) для всех вершин графа 
 (3) для вершин графа, имеющих временные метки 
Упражнение 2:
Номер 1
Для нахождения кратчайшего пути от s
к хi
, предшествующую вершину xi*
можно найти как одну из вершин, для которой
Ответ:
 (1) L(xi*)-c(xi*)=L(xi)
 
 (2) L(xi*) c(xi*)=L(xi)
 
 (3) L(xi*) + c(xi*)=L(xi* xi)
 
Номер 2
Если с помощью алгоритма Дейкстры требуется найти кратчайшие пути от вершины x3 до других вершин графа, то в первой итерации ей присваивается пометка со значением ...
Ответ:
 (1) 3 
 (2) 0 
 (3) равным количеству вершин графа 
 (4) равным количеству ребер графа 
Номер 3
Значение постоянной метки показывает
Ответ:
 (1) значение среднего пути 
 (2) значение кратчайшего пути 
 (3) число итераций 
Упражнение 3:
Номер 1
Найти кратчайший путь от вершины 1 к вершине 5 графа, представленного на рисунке
Ответ:
 (1) 12 
 (2) 15 
 (3) 16 
Номер 2
Найти кратчайший путь от вершины 1 к вершине 6 графа, представленного на рисунке
Ответ:
 (1) 8 
 (2) 13 
 (3) 15 
Номер 3
Найти кратчайший путь от вершины 1 к вершине 8 графа, представленного на рисунке
Ответ:
 (1) 16 
 (2) 19 
 (3) 13 
Упражнение 4:
Номер 1
Найти кратчайший путь от вершины x1
к вершине x5
графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис.Б
Ответ:
 (1) 13 
 (2) 19 
 (3) 18 
Номер 2
Найти кратчайший путь от вершины x1
к вершине x10
графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б
Ответ:
 (1) 15 
 (2) 16 
 (3) 18 
Номер 3
Найти кратчайший путь от вершины x1
к вершине x9
графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б
Ответ:
 (1) 21 
 (2) 12 
 (3) 10 
Упражнение 5:
Номер 1
Для графа, представленного на рисунке 1а, построить базу относительно вершины х1
.
Ответ:
 (1) рис. 2a 
 (2) рис. 2b 
 (3) рис. 2c 
Номер 2
Для графа, представленного на рисунке 1а, построить базу относительно вершины х7
.
Ответ:
 (1) рис. 2a 
 (2) рис. 2b 
 (3) рис. 2c 
Номер 3
Для графа, представленного на рисунке 1а, построить базу относительно вершины х3
.
Ответ:
 (1) рис. 2b 
 (2) рис. 2a 
 (3) рис. 2c