Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Омский государственный технический университет»
Системы и структуры
Методические указания к практическим занятиям
по дисциплине «Системный анализ и элементы оптимизации»
Омск
Издательство ОмГТУ
2009
Составитель Шендалева Елена Владимировна, канд. техн. наук
В методических указаниях приведены работы по практическому использованию методов системного анализа при рассмотрении различных систем и структур.
Методические указания предназначены для студентов специальности 200503 «Стандартизация и сертификация», изучающих дисциплину «Системный анализ и элементы оптимизации».
Печатается по решению редакционно-издательского совета
Омского государственного технического университета
Практическая работа № 1 графы
Цель работы
Изучение способов описания структур и их топологических свойств.
Отношения между элементами структуры могут быть представлены в виде графа, что позволяет формализовать процесс исследования неизменных во времени свойств системы и использовать хорошо развитый математический аппарат теории графов.
Графом называют пару G = (A, В), в которой A – множество вершин, В – множество ребер (дуг). Каждое ребро графа связывает две смежные вершины. Граф с пронумерованными вершинами называют отмеченным, при этом каждое ребро задается парой (i, j), где i и j – номера смежных вершин. Если все ребра графа заданы парами (i, j), в которых порядок расположения номеров смежных вершин имеет значение, то граф называется ориентированным.
Ориентированный граф можно задать диаграммой (рис. 1.1а), матрицей смежности вершин V = ||vij|| (рис. 1.1б), матрицей инцидентности (инциденций) W = ||wij|| (рис. 1.1в) или списком R = [R(i)] (рис. 1.1г).
а)
б)
в)
г) R = [R(1) = {2}, R(2) = {3, 4}, R(3) = {4}, R(4) = {0}]
или R = [1(2), 2(3, 4), 3(4), 4(0)]
Рис. 1.1. Ориентированный граф:
а) диаграмма; б) матрица смежности; в) матрица инцидентности; г) список
Элементы матриц смежности и инцидентности представлены ниже:
(1.1)
(1.2)
Среднее геометрическое число ребер g рассчитывают как корень n-степени из произведения числа ребер, инцидентных каждой n-вершине:
g = (γ1 × γ2 × … × γn)1/n. (1.3)
В графе выделяют изолированные, висячие и тупиковые вершины. Изолированные вершины не соединены ребрами с другими вершинами, висячие – соответствуют вершинам, в которые нельзя попасть из других вершин, тупиковые – вершинам, из которых нельзя попасть в другие вершины графа.
Пример
По заданной диаграмме графа (рис. 1.2):
1) определить изолированные, висячие и тупиковые вершины;
2) составить матрицы смежности и инцидентности графа;
3) записать граф в виде списков;
4) определить среднее геометрическое количество ребер, приходящееся на одну вершину графа.
Рис. 1.2. Граф
Выполнение задания
1. Изолированные вершины отсутствуют; висячие вершины – 5, 11; тупиковые вершины – 3, 8, 14.
2. С правой стороны от матрицы смежности (рис. 1.1б) в виде столбца проставлены i-вершины, над матрицей смежности проставлены j-вершины. Для каждой i-вершины (строки i) по рис. 1.2 определяют наличие ребра ij, то есть ребра, выходящего из вершины i в вершину j. При наличии такого ребра в матрице смежности на место пересечения строки i и столбца j ставят 1, в противном случае – 0 (рис. 1.3).
С правой стороны от матрицы инцидентности (рис. 1.1в) в виде столбца проставлены i-вершины, над матрицей проставлены ребра ij. Для каждого ij-ребра (столбца ij) по рис. 1.2 определяют вершину i, из которой ребро выходит, и вершину j, в которою ребро входит. В матрице инцидентности на место пересечения строки i и столбца ij ставят 1, на место пересечения строки j и столбца ij ставят –1, в остальных случаях – 0 (рис. 1.4).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
5
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
6
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
11
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
12
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
13
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
14
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
15
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
16
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
17
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
Vij
=
Wij
=
Р
|
1 17 |
2 3 |
2 4 |
2 7 |
4 6 |
4 10 |
4 15 |
5 6 |
5 8 |
5 9 |
7 14 |
9 17 |
10 13 |
10 15 |
11 12 |
12 13 |
12 16 |
13 16 |
15 16 |
15 17 |
|
1 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
0 |
1 |
–1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
3 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
1 |
0 |
–1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
7 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
11 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
–1 |
1 |
0 |
0 |
0 |
|
13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
–1 |
0 |
0 |
|
14 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
15 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
1 |
–1 |
|
16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
1 |
–1 |
0 |
|
17 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
–1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
3. В списке
перечисляют все i-вершины
графа и указывают смежные для них
j-вершины,
в которые приходят ребра ij.
R = [R(1) = {0}, R(2) = {3, 7}, R(3) = {0}, R(4) = {2, 10, 15}, R(5) = {6, 8, 9}, R(6) = {4}, R(7) = {14}, R(8) = {0}, R(9) = {17}, R(10) = {15}, R(11) = = {12}, R(12) = {16}, R(13) = {10, 12}, R(14) = {0}, R(15) = {16}, R(16) = = {13}, R(17) = {1, 15}]
или
R = [1(0), 2(3, 7), 3(0), 4(2, 10, 15), 5(6, 8, 9), 6(4), 7(14), 8(0), 9(17), 10(15), 11(12), 12(16), 13(10, 12), 14(0), 15(16), 16(13), 17(1, 15)].
4. Среднее геометрическое число ребер g рассчитывают как корень n-степени из произведения числа ребер, приходящихся на каждую n-вершину, то есть входящих в вершину и выходящих из нее (1.3).
.
Контрольные вопросы
Дайте определение понятию графа.
Чем граф отличается от структурной схемы?
Перечислите возможные формы представления графа.
Дайте определение изолированной, висячей и тупиковой вершины.
Дайте определение отмеченному и ориентированному графу.