Задача №2 Составление матрицы связности для ориентированного и неориентированного графа

Учебная цель: научится составлять матрицы связности для ориентированного и неориентированного графа.

 

Учебные задачи:

1. Ознакомится с правилами составления матриц связности для ориентированного и неориентированного графа

2. Научится составлять матрицы связности для ориентированного и неориентированного графа сети связи.

 

Образовательные ресурсы, заявленные во ФГОС третьего поколения:

Студент должен:

Уметь:

- Составлять матрицу связности для ориентированного и неориентированного графа

 

Знать:

- Теорию графов и сетей.

 

Обеспеченность занятия

 

1. Учебно-методическая литература:

- Величко В.В., Катунин Г.П., Шувалов В.Д., Основы информационных технологий – М – М.: Горячая линия – Телеком 2009.

2. Отчет по выполнению практической работы

3. Карандаш простой

4. Чертежные принадлежности: линейка.

 

Краткие теоретические и учебно-методические материалы по теме практической работы

 

       Матрицы связности строятся на основе графа сети связи. По строкам и столбцам матрицы отмечаются номера вершин, а в точку с этими координатами проставляется 1 или 0 в зависимости от того, существует или нет ребро, соединяющее эти вершины. Граф связный, если между двумя любыми вершинами есть маршрут, в противном случае граф несвязный.

 

Например для неориентированного графа вида (ГТС с четырьмя РАТС, соединенными по принципу каждая с каждой).

 

 

 Матрица связности будет иметь вид:

 

	1	2	3	4
1	0	1	1	1
2	1	0	1	1
3	1	1	0	1
4	1	1	1	0

 

Для ориентированного графа:

 

 

Матрица связности будет иметь вид:

 

	1	2	3	4
1	0	1	1	0
2	1	0	1	1
3	1	1	0	1
4	1	1	1	0

 

Матрица связности дает возможность построить граф сети.

Например:

 

Граф сети будет иметь вид:

Для матрицы связности:    

 

	1	2	3	4
1	0	1	0	0
2	1	0	1	1
3	0	1	0	0
4	0	1	0	0

 

 

Инструкция по выполнению практической работы.

1. Построить матрицу связности по виды графа сети связи. Исходные данные для выполнения работы представлены в таблицах 1 и 2.

2. Построить графы сети по виду матрицы связности. Исходные данные представлены в таблице 3 и перечне матриц.

Задания для практического занятия.

Таблица 1. Графы сети для построения матрицы связности.

 

№ граф	1	2	3
№ граф	4	5	6
№ граф	7	8	9
№ граф	10

Таблица номеров схема для выполнения задания 1.

 

№ п/п	1	2	3	4	5	6	7	8	9	10
№ схем	1,4 6,9	0,5,7 8	1,5 8,10	2,4 7,9	3,5 6,10	4,5,6 8	5,7 8,9	3,5 8,10	1,4 6,10	2,3 5,10

 

№ п/п	11	12	13	14	15	16	17	18	19	20
№ схем	1,3 4,7	2,4 6,10	3,5 7,9	4,6 7,9	1,5 8,10	2,6 9,10	1,6 7,8	2,3 5,10	1,3 6,10	2,4 6,7

 

№ п/п	21	22	23	24	25	26	27	28	29	30
№ схем	3,6 7,9	1,5 8,10	1,6 8,10	2,3 5,7	1,3 6,7	2,6 8,10	2,5 7,9	1,3 6,7	1,6 8,10	1,5 9,10

 

Исходные данные для выполнения задания 2

Матрица 1

	1	2	3	4	5
1	0	1	0	0	1
2	1	0	1	0	0
3	0	1	0	1	0
4	0	0	1	0	1
5	1	0	0	1	0

 

Матрица 2

	1	2	3	4	5
1	0	1	0	0	0
2	1	0	1	1	1
3	0	1	0	0	0
4	0	1	0	0	0
5	0	1	0	0	0

 

Матрица 3

	1	2	3	4	5	6
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	0	1	0	1	0	0
4	0	0	1	0	1	0
5	0	0	0	1	0	1
6	0	0	0	0	1	0

 

Матрица 4

	1	2	3	4	5	6	7
1	0	1	1	0	0	0	0
2	1	0	0	1	1	0	0
3	1	0	0	0	0	1	1
4	0	1	0	0	0	0	0
5	0	1	0	0	0	0	0
6	0	0	1	0	0	0	0
7	0	0	1	0	0	0	0

 

Матрица 5

	1	2	3	4
1	0	1	1	1
2	1	0	1	1
3	1	1	0	1
4	1	1	1	0

 

Матрица 6

	1	2	3	4	5
1	0	1	1	1	1
2	1	0	1	1	1
3	1	1	0	1	1
4	1	1	1	0	1
5	1	1	1	1	0

 

 

Матрица 7

	1	2	3	4	5	6	7	8
1	0	1	0	0	0	0	0	0
2	0	1	0	0	1	1	0	0
3	0	1	0	0	1	1	0	0
4	0	1	0	0	0	0	1	1
5	0	0	1	0	0	0	0	0
6	0	0	1	0	0	0	0	0
7	0	0	0	1	0	0	0	0
8	0	0	0	1	0	0	0	0

 

Матрица 8    

	1	2	3	4	5	6	7
1	0	1	1	0	0	0	0
2	1	0	1	0	0	0	0
3	0	0	0	0	1	0	0
4	1	1	0	0	0	0	0
5	0	0	0	1	0	1	0
6	0	0	0	1	1	0	0
7	0	0	0	0	0	0	0

 

Матрица 9

	1	2	3	4	5	6	7	8
1	0	1	0	1	0	0	0	0
2	1	0	0	1	0	0	0	0
3	1	1	0	0	0	0	0	0
4	0	0	0	0	0	1	0	0
5	0	0	1	0	0	0	0	0
6	0	0	0	0	0	0	1	1
7	0	0	0	0	1	0	0	1
8	0	0	0	0	1	0	1	0

 

Матрица 10

	1	2	3	4	5	6	7	8
1	0	1	1	1	0	0	0	0
2	1	0	0	0	1	0	0	0
3	1	0	0	0	0	1	1	0
4	1	0	0	0	0	0	0	1
5	0	1	0	0	0	0	0	0
6	0	0	1	0	0	0	0	0
7	0	0	1	0	0	0	0	0
8	0	0	0	1	0	0	0	0

 

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

       1. Какой граф называется “связный”?

       2. Какой граф называется неориентированный?

       3. Какова связь между графом и матрицей связности?

       4. Что такое граф сети?

       5. Матрица какого графа симметрична?

 

Порядок выполнения отчета по практической работе

 

1. Ознакомится с теоретическим материалом по практической работе.

2. Записать краткий конспект теоретической части.

3. Выполнить предложенное задание согласно варианту по списку группы.

4. Продемонстрировать результаты выполнения предложенных заданий преподавателю.

5. Ответить на контрольные вопросы.

6. Записать выводы о проделанной работе.