Главная Учебники - Разные Лекции (разные) - часть 50
|
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 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
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
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
) 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
),
G2
(G1
(Х)) 5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф. Остовные подграфы G’1
(X1
,A1
) G’2
(X2
,A2
) Произвольные подграфы G1
’’ (X1
’’,A1
’’) X3
Порожденные подграфы X7
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||