Задания к контрольной по графам (Матмех з/о, 1 высшее, 2011г.).

1. Найти радиус, диаметр и центры графа.
2. Найти эйлеров цикл или доказать, что его нет.
3. Найти гамильтонов цикл или доказать, что его нет.
4. Проверить планарность графа (доказать правильность ответа).
5. Найти максимальный полный подграф.
6. Найти оптимальную раскраску (доказать правильность ответа).
7. Построить обыкновенный связный граф с теми же степенями вершин, что и исходный, но не изоморфный исходному (неизоморфность доказать).

8. Рёбрам графа приписаны веса по правилу: вес ребра (u,v) равен (u+v)mod5. Найти минимальный каркас графа алгоритмом Краскла (порядок и результат просмотра алгоритмом ребер дерева должен быть указан явно).

9. Граф задает отношение предшествования для работ 1-9 (все рёбра ориентированы от вершины с меньшим номером к вершине с большим номером). Время выполнения работы u равно (u^2)mod10. Найти минимальное время выполнения проекта и критические работы.