Графы Основные понятия

Министерство образования и науки Российской Федерации

Курский государственный технический университет

Кафедра ПО ВТ и АС

Лабораторная работа № 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
)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. Найти все базы графа.

Базы графа 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