Экзаменационные вопросы по МДК 01.02.. Экзаменационные вопросы по мдк 01. 02
 Скачать 181.4 Kb.
|
|
Экзаменационные вопросы по МДК 01.02. 1. Что называется графом? Ориентированным графом? Приведите примеры. Что такое степень вершины? 2. Что называется маршрутом, циклом и цепью графа? 3. Сформулируйте понятие связности графа. Какой граф называют связным? 4. Какие два графа называются изоморфными? Сформулируйте алгоритм изоморфизма двух графов. 5. Дайте определение Эйлерова графа. 6. Сформулируйте алгоритм построения Эйлерова цикла. 7. Какой граф называют Гамильтоновым и чем отличается эйлеров путь от гамильтонова? 8. Дайте определение конечного и бесконечного графа 9. Как в задачах применяется ориентированный граф? 10. Какой граф можно начертить, не отрывая карандаша от бумаги, при этом можно начинать с любой вершины графа и завершить его в той же вершине? 11. Когда вершина графа называется четной, а когда нечетной? 12. Дайте определение остов графа и минимальный остов графа. 13. В чем смысл алгоритма Краскала? 14. Дайте определение планарности графа. 15. Какой используется граф, в определении двудольного графа? 16. Перечислите основные способы представления графов. 17. В чем особенности представления графа матрицей смежности? 18. В чем особенности представления графа матрицей инцидентности? 19. Перечислите основные компоненты связности графов. 20. Запишите теорему Форда-Фалкерсона 1 (о максимальном потоке и минимальном разрезе). 21. Какое множество вершин графа называется независимым? 22. Чем отличается путь от маршрута? 23. Дайте определение понятию поиск кратчайшего пути? 24. Перечислите, какие алгоритмы по поиску кратчайшего пути вы знаете? |