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

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

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

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

Лабораторная работа № 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


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