Контрольная Работа по Дискретной Математике,тема: Графы

Запишите весовую матрицу (0.5 балла) и нарисуйте диаграмму графа (0.5 балла)

2. Проверьте ваш граф на "планарность". Нарисуйте его плоское изображение,

если это возможно (0.5 балла)

3. Проверьте ваш граф на "двудольность" (0.5 балла)

4. Найдите минимальное остовное дерево с помощью любого известного Вам

алгоритма (0.5 балла). Покажите его построение по шагам (1 балл). Укажите вес

полученного дерева. (0.5 балла)

5. Выберите одну из вершин в качестве начального узла. По шагам найдите

кратчайшие пути из начального узла во все остальные (с помощью любого

известного Вам алгоритма) (2 балла)

6. Выполните обход графа двумя способами - в глубину (0.5 балла) и в ширину (0.5

балла). Укажите последовательность обхода вершин.

7. Найдите длину оптимального маршрута китайского почтальона (1 балл) и один

из таких маршрутов (1 балл).

8. Выполните раскраску графа в минимальное число цветов с помощью любого

известного Вам алгоритма (1 балл)