Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 1
Графы. Основные понятия
Выполнил:студент гр. ПО 62Шиляков И.А.
Проверил:доцентТомакова Р.А.
Курск 2007
Задание:
1. По заданнымматрицам смежности вершин восстановить графы.
2. Построить длякаждого графа матрицу смежности ребер, инцидентности, достижимости,контрдостижимости.
3. Найти и построитьобъединение, пересечение, кольцевую сумму заданных графов.
4. Найти композициюграфов /> />.
5. Для каждого графанайти и построить остовный подграф, произвольный подграф, порожденный подграф.
6. Определить локальныестепени вершин графа, проверить существует ли в данном графе эйлерова цепь,эйлеров цикл.
7. Определитьхроматические и цикломатические числа данных графов.
8. Найти все базыграфа.
9. Определить вкаждом графе сильные компоненты связности, построить конденсацию графа.
Выполнение:
1. По заданным матрицам смежностивершин восстановить графы.
x1
x2
x3
x4
x5
x6
x7
x1 1 1
x2 1 1
x3 1 1
x4 1 1
x5 1 1
x6 1 1
x7 1 1
A1
X2 />
G1(X1,A1)
x1
x2
x3
x4
x5
x6
x7
x1 1 1
x2 1 1
x3 1 1
x4 1 1
x5 1 1
x6 1 1
x7 1 1
A2
X2 />
G2(X2,A2)
2. Построить для каждого графаматрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
а1
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
а1 1 1 1 1 1 1
а2 1 1 1 1 1 1
а3 1 1 1 1 1
а4 1 1 1 1 1 1
а5 1 1 1 1 1
а6 1 1 1 1 1 1
а7 1 1 1 1 1 1
а8 1 1 1 1 1 1
а9 1 1 1 1 1 1
а10 1 1 1 1 1
а11 1 1 1 1 1 1
а12 1 1 1 1 1 1
а13 1 1 1 1 1
а14 1 1 1 1 1 1
B1
а1
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
а1 1 1 1 1 1 1
а2 1 1 1 1 1 1
а3 1 1 1 1 1 1
а4 1 1 1 1 1 1
а5 1 1 1 1 1
а6 1 1 1 1 1
а7 1 1 1 1 1 1
а8 1 1 1 1 1 1
а9 1 1 1 1 1 1
а10 1 1 1 1 1 1
а11 1 1 1 1 1 1
а12 1 1 1 1 1 1
а13 1 1 1 1 1 1
а14 1 1 1 1 1 1
B2
а1
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
x1 1 1 -1 -1
x2 -1 1 1 -1
x3 -1 1 1 -1
x4 -1 1 1 -1
x5 -1 1 1 -1
x6 -1 1 1 -1
x7 -1 -1 1 1
S1
а1
а2
а3
а4
а5
а6
а7
а8
а9
а10
а11
а12
а13
а14
x1 1 1 -1 -1
x2 -1 1 -1 1
x3 -1 1 -1 1
x4 -1 1 -1 1
x5 -1 1 -1 1
x6 1 -1 1 -1
x7 1 -1 1 -1
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’’)
/>
X3 />G2’’ (X2’’,A2’’)
Порожденные подграфы
X7 />
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. Найти все базы графа.