Задание к лабораторной работе. 1. Для графа составить матрицу Кирхгофа и посчитать количество помеченных остовов.

Исходные данные: граф ,

граф .

1. Для графа составить матрицу Кирхгофа и посчитать количество помеченных остовов.

2. Для графа построить дерево обхода вершин графа (использовать алгоритм в ширину, в глубину).

3. Для графа решить задачу построения остовов кротчайших маршрутов, используя алгоритмы Прима и Краскала. В качестве весов ребер использовать элементы вспомогательной матрицы .

4. Сгенерировать все различные абстрактные, не изоморфные друг другу деревья порядка (4-7).

5. Разделить множество деревьев на 2 подмножества с одной и с двумя центральными вершинами.

Алгоритм генерации варианта GV(p, X) описан в приложении А.

Контрольные вопросы

1. Привести определение дерева и леса.

2. Способы обхода деревьев.

3. Какие вершины дерева называются центром?

4. Что называется остовом?

5. Как можно определить число остовных деревьев?

6. Чем отличаются алгоритмы Краскала и Прима?

Лабораторная работа №4

Циклы и обходы

Цель работы: приобретение практических навыков в нахождении эйлеровых и гамильтоновых циклов в неориентированных графах, решение задач «китайского почтальона» и коммивояжера