Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 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= 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 ;
Эйлерова цепь существует в двух графах, т.к. ............
