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

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

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

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

















Лабораторная работа № 1



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

























Выполнил: студент гр. ПО 62 Шиляков И.А.

Проверил: доцентТомакова Р.А.   



























Курск 2007


Задание: 



		По заданным матрицам смежности вершин восстановить графы.

		Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.

		Найти и построить объединение, пересечение, кольцевую сумму заданных графов.

		Найти композицию графов  .

		Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.

		Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.

		Определить хроматические и цикломатические числа данных графов.

		Найти все базы графа.

		Определить в каждом графе сильные компоненты связности, построить конденсацию графа.


Выполнение: 





По заданным матрицам смежности вершин восстановить графы.





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

X1

X3

X4

X6

X7

X5

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14



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

X3

X4

X5

X6

X7

X1

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a14

a13



G2(X2,A2)





Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.







а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            

Найти и построить объединение, пересечение, кольцевую сумму заданных графов.



Объединение графов



X1

X3

X4

X6

X7

X5

X2

      

G3(X3,A3)=G1(X1,A1) YG2(X2,A2); 	X3= X1YX2, A3= A1YA2



Пересечение графов



X1

X3

X4

X6

X7

X5

X2







G3(X3,A3)=G1(X1,A1) ∩G2(X2,A2);      X3= X1∩X2, A3= A1∩A2







Кольцевая сумма графов



X1

X3

X4

X6

X7

X5

X2



G3(X3,A3)=G1(X1,A1)G2(X2,A2)





Найти и построить композицию графов  .





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),







X1

X3

X4

X6

X7

X5

X2G1(G2(Х))



X1

X3

X4

X7

X5

X2

X6

G2(G1(Х))

	



Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.



	Остовные подграфы





X1

X3

X4

X6

X7

X5

a1

a3

a6

a9

a12

a13

a14

X2

G’1(X1,A1)







X3

X4

X5

X6

X7

X1

a1

a2

a3

a9

a10

a14

a13

X2

G’2(X2,A2)



	Произвольные подграфы



X1

X3

X4

X6

a1

a3

a6

a12

G1’’ (X1’’,A1’’)





X3

X4

X1

a1

a2

a3



X3G2’’ (X2’’,A2’’)



Порожденные подграфы



X7

X1

X7

X5

a2

a9

a13

a1

a10

X6

a6



a9



G1P(X1P,A1P)						G2P(X2P,A2P)





Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.



Локальные степени графа 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 ;



Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны. 

Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны. 





Определить хроматические и цикломатические числа данных графов.



2

1

2

1

3

4

3

X1

X3

X6

X7

X5

X2

X4

Хроматическое число γ для графа G1 = 4





3

1

2

4

1

2

3

X3

X6

X7

X1

X2

X4

X5

Хроматическое число γ для графа G2 = 4



Цикломатические числа графов

V(G1)=m-n+r, где m - число рёбер (дуг);

n – число вершин;

r – число компонент связности.			

V(G1)=14-7+1=8;

V(G2)=14-7+1=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}





Определить в каждом графе сильные компоненты связности, построить конденсацию графа.



Сильные компоненты связности G1

СК={x1, x2, x3, x4, x5, x6, x7}

Сильные компоненты связности G2   

СК={x1, x2, x3, x4, x5, x6, x7}







Z1



Z1

Конденсация графа G1				Конденсация графа G2