Page 141 - 4336

КОНТРОЛЬНІ ЗАПИТАННЯ

1. Що таке граф. Які існують типи графів?

2. Яка різниця між планарним та плоским графом?

3. Що таке степінь вершини графа?

4. Які існують способи задання графів?

5. Дайте визначення наступним термінам: маршрут, ланцюг,

простий ланцюг, циклічний маршрут, цикл, простий цикл.

6. Які є основні властивості маршрутів?

7. Що таке пряме відображення та зворотне відображення?

Принцип їх знаходження.

8. Що таке пряме та зворотне транзитивне замикання?

Принцип їх знаходження.

9. Дайте визначення терміну “досяжність”.

10. Що таке матриця досяжності та контрдосяжності?

11. Принцип знаходження шляхів у графах матричним

методом.

12. Дайте визначення терміну “нормалізований граф”.

13. Принцип дії алгоритму Дейкстри пошуку

найкоротшого шляху.

14. Принцип дії алгоритму Белмана-Форда пошуку

найкоротшого шляху.

15. Принцип дії алгоритму Флойда-Уоршола пошуку усіх

найкоротших шляхів.

16. Принцип дії алгоритму Данцига пошуку усіх

найкоротших шляхів.

17. Принцип дії алгоритму подвійного пошуку k

найкоротших шляхів.

18. Дайте визначення терміну “навігація”.

141