Материал: АиСД. Практикум (in dev)

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

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

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

1 2

10

6 7

3 4

11

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

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

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

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

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.

33. Задание к лабораторной работе 4

Построить остовное дерево графа методами Крускала и Прима.

1 ; 24

2 ; 23

3 ; 22

4 ; 21

5 ; 20

6; 19

7 ; 18

8; 17

9 ; 16

1 0; 15; 25

1 1; 14

12; 13

34. Решение задач

Задача 1. Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Соединить все города автострадой минимальной длины, т.е. построить остовное дерево методами Прима и Крускала.

Задача 3. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера, Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Юпитер, Юпитер-Марс и Марс-Уран. Можно ли добраться с Земли до Марса?

Задача 4. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Задача 5. Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами? Какое минимальное число висячих вершин оно может иметь? Сделайте рисунки таких деревьев.

Задача 6. В доме отдыха Вишкиль 57 корпусов. Электрик решил соединить телефонными проводами каждый корпус ровно с пятью другими. Сможет ли он это сделать?

Задача 7. У предприятия имеется 4 завода и 9 торговых точек. Каждый завод должен поставлять свою продукцию во все торговые точки. Сколько всего дорог необходимо проложить, чтобы осуществить задуманное? Определите вид полученного графа.

Задача 8. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дорогу от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам. Может ли осуществиться их намерение?

Задача 9. Муравей забрался в банку из-под сахара, имеющую форму куба. Сможет ли он последовательно обойти все рёбра куба, не проходя дважды по одному ребру?

Задача 10. На занятии 20 школьников решили каждый по 6 задач, причём каждая задача была решена ровно двумя школьниками. Можно ли организовать разбор всех задач таким образом, чтобы каждый школьник рассказал ровно по 3 задачи.

4. Лабораторная работа - Алгоритмы нахождения на графах кратчайших путей

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

Продолжительность работы – 2 часа.

35. Теоретические сведения