Лабораторная работа: Графы. Основные понятия
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= X1YX2, A3= A1YA2
Пересечение графов
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
