Скачать .docx Скачать .pdf

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

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

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

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

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

11 )=2 ; 21 )=2 ; 1 )=4 ;

12 )=2 ; 22 )=2 ; 2 )=4 ;

13 )=2 ; 23 )=2 ; 3 )=4 ;

14 )=2 ; 24 )=2 ; 4 )=4 ;

15 )=2 ; 25 )=2 ; 5 )=4 ;

16 )=2 ; 26 )=2 ; 6 )=4 ;

17 )=2 ; 27 )=2 ; 7 )=4 ;

Локальные степени графа G2

11 )=2 ; 21 )=2 ; 1 )=4 ;

12 )=2 ; 22 )=2 ; 2 )=4 ;

13 )=3 ; 23 )=2 ; 3 )=4 ;

14 )=2 ; 24 )=2 ; 4 )=4 ;

15 )=2 ; 25 )=2 ; 5 )=4 ;

16 )=2 ; 26 )=2 ; 6 )=4 ;

17 )=2 ; 27 )=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