Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа

 

1. Олифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы: учебник для вузов - 3-е изд. / Н.А. Олифер. - СПб: Питер, 2006. - 958 с.

2. Олифер, В. Г. Основы сетей передачи данных: курс лекций. Учебное пособие / Н.А. Олифер. - М.: Интернет-Ун-т Информ. технологий, 2005. - 176 с.

1. Новиков, Ю. В. Основы локальных сетей: курс лекций. Учебное пособие / Ю. В. Новиков; С.В. Кондратенко. - М.: Интернет-Ун-т Информ. технологий, 2005.
2. Новиков, Ю. В. Основы локальных сетей: курс лекций. Учебное пособие / Ю. В. Новиков; С.В. Кондратенко. - М.: Интернет-Ун-т Информ. технологий, 2005.

 

Практические работы

Практическая работа №1

Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа

 

Теоретическая часть:

1. Граф (понятие и определение графа, орграфа, неориентированного графа, вершины, ребра, дуги).

2. Определение: степень вершины графа и орграф, висящая, изолированная, ветвящаяся вершина.

3. Способы представления графа в ЭВМ

4. Матрица смежности вершин орграфа и неориентированного графа

5. Матрица инциденций орграфа и неориентированного графа

6. Определение понятий: цикл, цепь, маршрут в графе.

7. Определение понятия «дерево».

8. Определение понятия «эйлеров цикл»

9. Определение понятия «гамильтонов цикл»

10. Назначение Алгоритма

11. Отличие алгоритма Prim от Kruskal

12. Назначение алгоритма Dejkstra

13. Алгоритм Prim (пошаговая реализация)

14. Алгоритм Kruskal (пошаговая реализация)

15. Алгоритм Dejkstra (пошаговая реализация)

 

Практическая часть:

1. Дан граф №1 в матричном виде. Элементами матрицы являются веса ребер. Для данного графа (в соответствии с вариантом) построить:

1) графическое изображение графа;

2) остовное дерево минимального веса по алгоритму Prim;

3) остовное дерево минимального веса по алгоритму Kruskal;

2. Для данного графа №2 найти наикратчайшее расстояние от вершины S до всех остальных вершин по алгоритму Dejkstra

Граф №1

Варианты

1. 2. 3.

4. 5. 6.

 

7. 8. 9.

 

10. 11. 12.

13. 14. 15.

 

16. 17. 18.

 

19. 20. 21.

 

22. 23. 24.

 

25. 26. 27.

 

28. 29. 30.

 

 

Граф №2

Варианты