2. Пример со схемой компьютерной сети

Пусть дана схема компьютерной сети.

Необходимо соединить компьютеры таким образом , чтобы длина проводки была минимальной.

1 2

10

6 7

3 4

11

Определим цикломатическое число графа: γ = n – m +1 = 8 – 5 + 1 = 4

Выбранные вершины	Невыбранные вершины
	V1	V2	V3	V4
V5	10	6	7	11
V2	1	*	7	3
V1	*	*	2	3
V3	*	*	*	3

При просмотре строки таблицы находим минимальную величину веса ребра, выделяем её и больше этот столбец, в котором находится эта величина, в рассмотрении не участвует.

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

В итоге получим остовное дерево минимального веса:

1. 2

6

3

30. Лабораторное задание

Для проведения лабораторной работы необходимо выполнить следующие действия.

1. Изучить основные понятия теории графов

2. Вызвать систему Ostov1, включающую в себя изучение методов Крускала и Прима.

Система работает в диалоговом режиме с использованием “меню”. Вся необходимая информация во время работы системы отображается на экране дисплея и не требует специальных пояснений.

Для графов, содержащих 10 и 12 вершин построить остовные деревья двумя методами.

По окончании работы выставляется оценка.

3. Вызвать системы Ostov2 и Ostov3 для исследования методов Крускала и Прима.

Результаты записать в тетрадь.

31. Требования к отчёту

Отчёт должен содержать:

5. конспект лабораторной работы;

6. примеры работы методов Крускала и Прима;

7. результаты выполнения работы;

8. выводы по работе;

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

1. Что понимается под остовным деревом?

2. Каковы особенности методов Крускала и Прима?

3. В чём состоит методика анализа сложности алгоритмов построения остовного

дерева графа?

1. Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

2. Д.Кнут Искусство программирования , том 1. Основные алгоритмы. Уч . пос. М.:Изд. Дом " Вильямс ", 2000.

3. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. М : Финансы и статистика, 2004.