Лабораторная работа: Графы. Основные понятия

Лабораторная работа: Графы. Основные понятия

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

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

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

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

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