Исходные данные: граф 
,
граф 
.
1. Для графа 
составить матрицу Кирхгофа и посчитать количество помеченных остовов.
2. Для графа 
построить дерево обхода вершин графа (использовать алгоритм в ширину, в глубину).
3. Для графа решить задачу построения остовов кротчайших маршрутов, используя алгоритмы Прима и Краскала. В качестве весов ребер использовать элементы вспомогательной матрицы 
.
4. Сгенерировать все различные абстрактные, не изоморфные друг другу деревья порядка (4-7).
5. Разделить множество деревьев на 2 подмножества с одной и с двумя центральными вершинами.
Алгоритм генерации вариантаGV(p,X)описан в приложении А.
Контрольные вопросы
1. Привести определение дерева и леса.
2. Способы обхода деревьев.
3. Какие вершины дерева называются центром?
4. Что называется остовом?
5. Как можно определить число остовных деревьев?
6. Чем отличаются алгоритмы Краскала и Прима?
Лабораторная работа №4
Циклы и обходы
Цель работы:приобретение практических навыков в нахождении эйлеровых и гамильтоновых циклов в неориентированных графах, решение задач «китайского почтальона» и коммивояжера
