Xreferat.com » Рефераты по математике » Графы. Основные понятия

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

5.4pt 0cm 5.4pt;height:19.85pt;">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               

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: