| Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 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
 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
 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
| |
а1
|
а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
| |
а1
|
а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
| |
а1
|
а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. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
Объединение графов
G3
(X3
,A3
)=G1
(X1
,A1
) YG2
(X2
,A2
); X3
= X1
YX2,
A3
= A1
YA2
Пересечение графов
G3
(X3
,A3
)=G1
(X1
,A1
) ∩G2
(X2
,A2
); X3
= X1
∩X2,
A3
= A1
∩A2
Кольцевая сумма графов
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
),
|
 G1
(G2
(Х))
G2
(G1
(Х))
5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
Остовные подграфы
G’1
(X1
,A1
)
G’2
(X2
,A2
)
Произвольные подграфы
G1
’’ (X1
’’,A1
’’)
 G2
’’ (X2
’’,A2
’’) Порожденные подграфы
 G1P
(X1P
,A1P
) G2P
(X2P
,A2P
)
6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
Локальные степени графа G1
 1
(х1
)=2 ; 2
(х1
)=2 ; (х1
)=4 ;
1
(х2
)=2 ; 2
(х2
)=2 ; (х2
)=4 ;
1
(х3
)=2 ; 2
(х3
)=2 ; (х3
)=4 ;
1
(х4
)=2 ; 2
(х4
)=2 ; (х4
)=4 ;
 1
(х5
)=2 ; 2
(х5
)=2 ; (х5
)=4 ;
1
(х6
)=2 ; 2
(х6
)=2 ; (х6
)=4 ;
1
(х7
)=2 ; 2
(х7
)=2 ; (х7
)=4 ;
Локальные степени графа G2
1
(х1
)=2 ; 2
(х1
)=2 ; (х1
)=4 ;
1
(х2
)=2 ; 2
(х2
)=2 ; (х2
)=4 ;
1
(х3
)=3 ; 2
(х3
)=2 ; (х3
)=4 ;
1
(х4
)=2 ; 2
(х4
)=2 ; (х4
)=4 ;
1
(х5
)=2 ; 2
(х5
)=2 ; (х5
)=4 ;
 1
(х6
)=2 ; 2
(х6
)=2 ; (х6
)=4 ;
 1
(х7
)=2 ; 2
(х7
)=2 ; (х7
)=4 ;
Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны.
Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны.
7. Определить хроматические и цикломатические числа данных графов.
Хроматическое число γ для графа G1
= 4
Хроматическое число γ для графа 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
}
 
Конденсация графа G1
Конденсация графа G2
|