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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Курск 2007


Задание:

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

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

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

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

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

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

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

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

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


Выполнение:

 

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

x1

x2

x3

x4

x5

x6

x7

x1

1 1

x2

1 1

x3

1 1

x4

1 1

x5

1 1

x6

1 1

x7

1 1

A1

X2

  />

G1(X1,A1)

x1

x2

x3

x4

x5

x6

x7

x1

1 1

x2

1 1

x3

1 1

x4

1 1

x5

1 1

x6

1 1

x7

1 1

A2

 

X2

  />

G2(X2,A2)

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

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

1 1 1 1 1 1

а2

1 1 1 1 1 1

а3

1 1 1 1 1

а4

1 1 1 1 1 1

а5

1 1 1 1 1

а6

1 1 1 1 1 1

а7

1 1 1 1 1 1

а8

1 1 1 1 1 1

а9

1 1 1 1 1 1

а10

1 1 1 1 1

а11

1 1 1 1 1 1

а12

1 1 1 1 1 1

а13

1 1 1 1 1

а14

1 1 1 1 1 1

B1

 


а1 

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

а1

1 1 1 1 1 1

а2

1 1 1 1 1 1

а3

1 1 1 1 1 1

а4

1 1 1 1 1 1

а5

1 1 1 1 1

а6

1 1 1 1 1

а7

1 1 1 1 1 1

а8

1 1 1 1 1 1

а9

1 1 1 1 1 1

а10

1 1 1 1 1 1

а11

1 1 1 1 1 1

а12

1 1 1 1 1 1

а13

1 1 1 1 1 1

а14

1 1 1 1 1 1

B2

 

а1 

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1 1 -1 -1

x2

-1 1 1 -1

x3

-1 1 1 -1

x4

-1 1 1 -1

x5

-1 1 1 -1

x6

-1 1 1 -1

x7

-1 -1 1 1

S1                                                    

а1 

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

а12

а13

а14

x1

1 1 -1 -1

x2

-1 1 -1 1

x3

-1 1 -1 1

x4

-1 1 -1 1

x5

-1 1 -1 1

x6

1 -1 1 -1

x7

1 -1 1 -1

                                                                                                                                                     


                                                                 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.    Найти все базы графа.

еще рефераты
Еще работы по математике