Контрольные задания. 1. Определить, является ли связным заданный граф

1. Определить, является ли связным заданный граф.

2. Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа.

3. Найти все вершины графа, достижимые из заданной.

4. Подсчитать количество компонент связности заданного графа.

5. Найти диаметр графа, т.е. максимум расстояний между всевозможными парами его вершин.

6. Найти такую нумерацию вершин орграфа, при которой всякая дуга ведет от вершины с меньшим номером к вершине с большим номером.

7. Дан взвешенный граф. Построить остовное дерево минимальной стоимости.

8. Определить является ли граф гамильтоновым. Найти гамильтонов цикл, т. е. цикл, проходящий через все вершины графа.

9. Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через заданное множество городов.

10. В заданном графе указать все его четырехвершинные полные подграфы.

11. Известно, что заданный граф - не дерево. Проверить, можно ли удалить из него одну вершину (вместе с инцидентными ей ребрами), чтобы в результате получилось дерево.

Лабораторная работа № 5.

Основные стратегии решения задач

Цель работы: Получить представление об основных стратегиях решения задач