игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 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)

 (2)

 (3) равным количеству вершин графа 

 (4) равным количеству ребер графа 


Номер 3
Значение постоянной метки показывает

Ответ:

 (1) значение среднего пути 

 (2) значение кратчайшего пути 

 (3) число итераций 


Упражнение 3:
Номер 1
Найти кратчайший путь от вершины 1  к вершине 5 графа, представленного на рисунке files

Ответ:

 (1) 12 

 (2) 15 

 (3) 16 


Номер 2
Найти кратчайший путь от вершины 1  к вершине 6 графа, представленного на рисунке files

Ответ:

 (1)

 (2) 13 

 (3) 15 


Номер 3
Найти кратчайший путь от вершины 1  к вершине 8 графа, представленного на рисунке files

Ответ:

 (1) 16 

 (2) 19 

 (3) 13 


Упражнение 4:
Номер 1
Найти кратчайший путь от вершины x1 к вершине x5 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис.Б files

Ответ:

 (1) 13 

 (2) 19 

 (3) 18 


Номер 2
Найти кратчайший путь от вершины x1 к вершине x10 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б files

Ответ:

 (1) 15 

 (2) 16 

 (3) 18 


Номер 3
Найти кратчайший путь от вершины x1 к вершине x9 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Бfiles

Ответ:

 (1) 21 

 (2) 12 

 (3) 10 


Упражнение 5:
Номер 1
Для графа, представленного на рисунке  1а, построить базу относительно вершины х1.filesfiles

Ответ:

 (1) рис. 2a 

 (2) рис. 2b 

 (3) рис. 2c 


Номер 2
Для графа, представленного на рисунке  1а, построить базу относительно вершины х7.filesfiles

Ответ:

 (1) рис. 2a 

 (2) рис. 2b 

 (3) рис. 2c 


Номер 3
Для графа, представленного на рисунке  1а, построить базу относительно вершины х3.filesfiles

Ответ:

 (1) рис. 2b 

 (2) рис. 2a 

 (3) рис. 2c 




Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 9