Лабораторная работа

Лабораторная работа на тему Графы Основные понятия

Работа добавлена на сайт bukvasha.ru: 2014-12-15

Бесплатно
Узнать стоимость работы
Рассчитаем за 1 минуту, онлайн


Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 1
Графы. Основные понятия
Выполнил: студент гр. ПО 62 Шиляков И.А.
Проверил: доцентТомакова Р.А.  
Курск 2007

Задание:
1.  По заданным матрицам смежности вершин восстановить графы.
2.  Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
3.  Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
4.  Найти композицию графов   .
5.  Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
6.  Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
7.  Определить хроматические и цикломатические числа данных графов.
8.  Найти все базы графа.
9.  Определить в каждом графе сильные компоненты связности, построить конденсацию графа.

Выполнение:
1.     По заданным матрицам смежности вершин восстановить графы.
x1
x2
x3
x4
x5
x6
x7
x1
0
1
0
0
0
0
1
x2
0
0
1
0
0
1
0
x3
0
1
0
1
0
0
0
x4
1
0
0
0
1
0
0
x5
1
0
0
0
0
0
1
x6
0
0
1
1
0
0
0
x7
0
0
0
0
1
1
0
A1
X2
 
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14

G1(X1,A1)
x1
x2
x3
x4
x5
x6
x7
x1
0
1
1
0
0
0
0
x2
0
0
0
1
1
0
0
x3
0
1
0
0
0
0
1
x4
1
0
0
0
1
0
0
x5
0
0
0
0
0
1
1
x6
1
0
0
1
0
0
0
x7
0
0
1
0
0
1
0
A2
X2
 
 SHAPE  \* MERGEFORMAT
X3
X4
X5
X6
X7
X1
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a14
a13

G2(X2,A2)
2.     Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
а1
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
а1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
а2
1
0
0
0
0
0
1
0
1
1
0
0
1
1
а3
1
0
0
1
1
1
0
0
0
0
1
0
0
0
а4
1
0
1
0
1
0
0
0
0
0
1
1
0
1
а5
1
0
1
1
0
1
0
0
0
0
1
0
0
0
а6
0
0
1
0
1
0
1
1
0
0
1
1
0
0
а7
1
1
0
0
0
1
0
1
1
0
0
1
0
0
а8
0
0
0
0
0
1
1
0
1
1
0
1
1
0
а9
1
1
0
0
0
0
1
1
0
1
0
0
1
0
а10
0
1
0
0
0
0
0
1
1
0
0
0
1
1
а11
0
0
1
1
1
1
0
0
0
0
0
1
0
1
а12
0
0
0
1
0
1
1
1
0
0
1
0
0
1
а13
0
1
0
0
0
0
0
1
1
1
0
0
0
1
а14
0
1
0
1
0
0
0
0
0
1
1
1
1
0
B1

а
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
а1
0
1
0
1
1
1
1
0
1
0
0
0
0
0
а2
1
0
1
1
1
1
0
1
0
0
0
0
0
0
а3
0
1
0
1
0
0
1
1
0
0
0
1
1
0
а4
1
1
1
0
0
0
1
1
1
0
0
0
0
0
а5
1
1
0
0
0
1
0
0
0
1
1
0
0
0
а6
1
1
0
0
1
0
0
0
0
1
1
0
0
0
а7
1
0
1
1
0
0
0
0
1
0
0
1
1
0
а8
0
1
1
1
0
0
0
0
0
0
1
0
1
1
а9
1
0
0
1
0
0
1
0
0
1
0
1
0
1
а10
0
0
0
0
1
1
0
0
1
0
1
1
0
1
а11
0
0
0
0
1
1
0
1
0
1
0
0
1
1
а12
0
0
1
0
0
0
1
0
1
1
0
0
1
1
а13
0
0
1
0
0
0
1
1
0
0
1
1
0
1
а14
0
0
0
0
0
0
0
1
1
1
1
1
1
0
B2
а
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
x1
1
1
0
0
0
0
-1
0
-1
0
0
0
0
0
x2
-1
0
1
1
-1
0
0
0
0
0
0
0
0
0
x3
0
0
-1
0
1
1
0
0
0
0
-1
0
0
0
x4
0
0
0
0
0
-1
1
1
0
0
0
-1
0
0
x5
0
0
0
0
0
0
0
-1
1
1
0
0
-1
0
x6
0
0
0
-1
0
0
0
0
0
0
1
1
0
-1
x7
0
-1
0
0
0
0
0
0
0
-1
0
0
1
1
S1                                                    
а
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
x1
1
0
0
1
0
0
-1
0
-1
0
0
0
0
0
x2
0
-1
1
-1
0
0
0
1
0
0
0
0
0
0
x3
-1
1
0
0
-1
1
0
0
0
0
0
0
0
0
x4
0
0
-1
0
0
0
1
0
0
0
0
-1
1
0
x5
0
0
0
0
0
0
0
-1
0
0
1
0
-1
1
x6
0
0
0
0
0
0
0
0
1
-1
0
1
0
-1
x7
0
0
0
0
1
-1
0
0
0
1
-1
0
0
0
                                                                                                                                                     

                                                                  S2                                          
x1
x2
x3
x4
x5
x6
x7
x1
1
1
1
1
1
1
1
x2
1
1
1
1
1
1
1
x3
1
1
1
1
1
1
1
x4
1
1
1
1
1
1
1
x5
1
1
1
1
1
1
1
x6
1
1
1
1
1
1
1
x7
1
1
1
1
1
1
1
x1
x2
x3
x4
x5
x6
x7
x1
1
1
1
1
1
1
1
x2
1
1
1
1
1
1
1
x3
1
1
1
1
1
1
1
x4
1
1
1
1
1
1
1
x5
1
1
1
1
1
1
1
x6
1
1
1
1
1
1
1
x7
1
1
1
1
1
1
1
      R1                                                                                             R2
x1
x2
x3
x4
x5
x6
x7
x1
1
1
1
1
1
1
1
x2
1
1
1
1
1
1
1
x3
1
1
1
1
1
1
1
x4
1
1
1
1
1
1
1
x5
1
1
1
1
1
1
1
x6
1
1
1
1
1
1
1
x7
1
1
1
1
1
1
1
x1
x2
x3
x4
x5
x6
x7
x1
1
1
1
1
1
1
1
x2
1
1
1
1
1
1
1
x3
1
1
1
1
1
1
1
x4
1
1
1
1
1
1
1
x5
1
1
1
1
1
1
1
x6
1
1
1
1
1
1
1
x7
1
1
1
1
1
1
1
     
                         Q1                                                                                                Q2           
3.     Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
Объединение графов
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
X2

     
G3(X3,A3)=G1(X1,A1) YG2(X2,A2);   X3= X1YX2, A3= A1YA2
Пересечение графов
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
X2

G3(X3,A3)=G1(X1,A1) ∩G2(X2,A2);      X3= X1∩X2, A3= A1∩A2
Кольцевая сумма графов
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
X2

G3(X3,A3)=G1(X1,A1) G2(X2,A2)
4.     Найти и построить композицию графов   .
G1(Х)
G2(Х)
G1(G2(Х))
G2(G1(Х))
x1
(x1,x2), (x1,x7)
(x1,x2), (x1,x3)
(x1,x3), (x1,x6),
(x1,x2), (x1,x4),
(x1,x4), (x1,x5),
(x1,x3), (x1,x6),
x2
(x2,x3),
(x2,x6)
(x2,x4),
(x2,x5)
(x2,x1), (x2,x5),
(x2,x7),
(x2,x2), (x2,x7),
(x2,x1), (x2,x4),
x3
(x3,x2),
(x3,x4)
(x3,x2),
(x3,x7)
(x3,x3), (x3,x6),
(x3,x5),
(x3,x4), (x3,x5),
(x3,x1),
x4
(x4,x1), (x4,x5)
(x4,x1), (x4,x5)
(x4,x2), (x4,x7),
(x4,x1),
(x4,x2), (x4,x3),
(x4,x6), (x4,x7),
x5
(x5,x1), (x5,x7)
(x5,x6), (x5,x7)
(x5,x3), (x5,x4),
(x5,x5), (x5,x6),
(x5,x2), (x5,x3),
(x5,x6),
x6
(x6,x3),
(x6,x4)
(x6,x1),
(x6,x4)
(x6,x2), (x6,x7),
(x6,x1), (x6,x5),
(x6,x2), (x6,x7),
(x6,x1), (x6,x5),
x7
(x7,x5), (x7,x6)
(x7,x3), (x7,x6)
(x7,x2), (x7,x4),
(x7,x3),
(x7,x6), (x7,x7),
(x7,x1), (x7,x4),
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
X2
G1(G2(Х))
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X7
X5
X2
X6

G2(G1(Х))
5.     Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
Остовные подграфы
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
X7
X5
a1
a3
a6
a9
a12
a13
a14
X2

G’1(X1,A1)
 SHAPE  \* MERGEFORMAT
X3
X4
X5
X6
X7
X1
a1
a2
a3
a9
a10
a14
a13
X2

G’2(X2,A2)
Произвольные подграфы
 SHAPE  \* MERGEFORMAT
X1
X3
X4
X6
a1
a3
a6
a12

G1’’ (X1’’,A1’’)
 SHAPE  \* MERGEFORMAT
X3
X4
X1
a1
a2
a3

X3
 
G2’’ (X2’’,A2’’)
Порожденные подграфы
X7
 
 SHAPE  \* MERGEFORMAT
X1
X7
X5
a2
a9
a13
a1
a10
X6
a6
a9

G1P(X1P,A1P)                                                        G2P(X2P,A2P)
6.     Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
Локальные степени графа G1
11)=2 ;  21)=2 ;   (х1)=4 ;
12)=2 ;  22)=2 ;   (х2)=4 ;
13)=2 ;  23)=2 ;   (х3)=4 ;
14)=2 ;  24)=2 ;   (х4)=4 ;
15)=2 ;  25)=2 ;   (х5)=4 ;
16)=2 ;  26)=2 ;   (х6)=4 ;
17)=2 ;  27)=2 ;   (х7)=4 ;
Локальные степени графа G2
11)=2 ;  21)=2 ;   (х1)=4 ;
12)=2 ;  22)=2 ;   (х2)=4 ;
13)=3 ;  23)=2 ;   (х3)=4 ;
14)=2 ;  24)=2 ;   (х4)=4 ;
15)=2 ;  25)=2 ;   (х5)=4 ;
16)=2 ;  26)=2 ;   (х6)=4 ;
17)=2 ;  27)=2 ;   (х7)=4 ;
Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.
Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.
7.     Определить хроматические и цикломатические числа данных графов.
 SHAPE  \* MERGEFORMAT
2
1
2
1
3
4
3
X1
X3
X6
X7
X5
X2
X4

Хроматическое число γ для графа G1 = 4
 SHAPE  \* MERGEFORMAT
3
1
2
4
1
2
3
X3
X6
X7
X1
X2
X4
X5

Хроматическое число γ для графа G2 = 4
Цикломатические числа графов
V(G1)=m-n+r, где m - число рёбер (дуг);
n – число вершин;
r – число компонент связности.                      
V(G1)=14-7+1=8;
V(G2)=14-7+1=8;
8.     Найти все базы графа.

Базы графа G1
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}
Базы графа G2
B1={x1}
B2={x2}
B3={x3}
B4={x4}
B5={x5}
B6={x6}
B7={x7}

9.     Определить в каждом графе сильные компоненты связности, построить конденсацию графа.
Сильные компоненты связности G1
СК={x1, x2, x3, x4, x5, x6, x7}
Сильные компоненты связности G2  
СК={x1, x2, x3, x4, x5, x6, x7}
 SHAPE  \* MERGEFORMAT
Z1
 SHAPE  \* MERGEFORMAT
Z1

Конденсация графа G1                                                       Конденсация графа G2               

1. Реферат Современная субкультура байкеров рокеров
2. Сочинение на тему Сочинения на свободную тему - Портрет моей учительницы 1
3. Доклад Классификация водных препятствий
4. Биография Утепов, Ташен Саменович
5. Сочинение на тему Пушкин а. с. - Личное и историческое в лирике пушкина
6. Курсовая на тему Використання диференціаційного навчання при вивченні креслення на прикладі теми Нанесення розмірів
7. Курсовая на тему Организация энергетического хозяйства в ЗАО ЗКПД4 Инвест 2
8. Контрольная работа Понятие жилого помещения в гражданском праве
9. Реферат Философия экзистенциализма 2
10. Курсовая Психологические особенности акцентуации характера подростков