Контрольные вопросы

1. Как выполняется обход вершин и ребер графа ?

2. Как проводится поиск в глубину при заданных смежных вершин ?

3. В чем заключается задача раскраски графа ?

4. Какая раскраска графа называется правильной ?

5. В чем состоит алгоритм минимальной раскраски ?

6. Какие существуют оценки хроматического числа ?

7. Как формируется задача построения кратчайшего остовного дерева (остова минимального веса) ?

8. В чем заключается алгоритм Краскала ?

9. Как формируется задача поиска путей между двумя вершинами графа ?

10. В чем заключается алгоритм Дийкстры ?

11. Чем отличаются алгоритмы Форда и Дийкстры ?

12. В чем заключается алгоритм Флойда ?

13. Как формулируются потоковые задачи ?

14. Как определить поток в цепи ?

15. Как формулируется задача поиска максимального потока в сети ?

16. Как формулируются задачи поиска потока минимальной стоимости и максимального потока минимальной стоимости?

17. В чем заключается алгоритм поиска максимальн

18. В чем заключается алгоритм поиска максимального потока ?

19. В чем заключается алгоритм поиска потока минимальной стоимости?

20. Какие алгоритмы используются для решения задач о динамических потоках ?

21. В чем заключается сущьность алгоритма дефекта ?