игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 6

Введение в теорию графов - тест 6

Упражнение 1:
Номер 1
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его подграфами?files files

Ответ:

 (1) а 

 (2)

 (3) с 

 (4)

 (5)

 (6)


Номер 2
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его остовными подграфами?filesfiles

Ответ:

 (1) а, с, d, e, f 

 (2) а, e 

 (3) все 


Номер 3
Дан граф на риунке 1. Какой из приведенных на рисунке 2 графов является для него порожденным подграфом?filesfiles

Ответ:

 (1)

 (2)

 (3) с 

 (4)

 (5) ef 

 (6)


Упражнение 2:
Номер 1
Для графа G = (X, A), представленного на рисунке 1, описать матрицей смежности порожденный подграф 12345}files
а
X1X2X3X4X5
X101000
X200101
X300001
X400100
X500100
b
X1X2X3X4X5
X101000
X200101
X300011
X400010
X500110
c
X1X2X3X4X5
X101000
X200101
X300011
X400000
X500100

Ответ:

 (1)

 (2)

 (3) а  


Номер 2
Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф 123, ,х5, х7}

files
а
X1X2X3X5X7
X101000
X200101
X300001
X500100
X700100
b
X1X2X3X5X7
X101000
X200110
X300010
X500100
X710010
c
X1X2X3X5X7
X101000
X200101
X300011
X500001
X710100

Ответ:

 (1)

 (2)

 (3) а  


Номер 3
Для графа   G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф 23, х45, х6}

files
а
X2X3X4X5X6
X201010
X300110
X400001
X501000
X600100
b
X2X3X4X5X6
X201000
X300110
X400100
X500010
X610010
c
X2X3X4X5X6
X201000
X300101
X400001
X501001
X610100

Ответ:

 (1)

 (2)

 (3)


Упражнение 3:
Номер 1
Для графа   G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда  i+j  нечетно files

Ответ:

 (1) G = (Х, А), где Х = {хi}, i = 1, 2, …, 8 – множество вершин; А = {ai }, i = 1, 2, ..., 7 – множество дуг, причем А = {(х1, х2), (х4, х7), (х2, х4 ), (х2, х3), (х3, х8), (х4 , х1), (х7 , х6), } 

 (2) G = (Х, А), где Х = {хi}, i = 1, 2, …,8 – множество вершин; А = {ai }, i = 1, 2, ... – множество дуг, причем А = {(х1, х2), (х2, х3), (х2, х5 ), (х2, х7), (х3, х4), (х8 , х7), (х7 , х6), (х3, х6), (х5 , х7), (х7 , х6) }  

 (3) G = (Х, А), где Х = {хi}, i = 1, 2, …,8 – множество вершин; А = {ai }, i = 1, 2, ..., 7– множество дуг, причем А = {(х1, х2), (х2, х3), (х2, х5 ), (х3, х4), (х1, х8), (х8 , х7), (х7 , х6), }  


Номер 2
Для графа   G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈X тогда и только тогда, когда  i+j  четно files

Ответ:

 (1) G = (Х, А), где X – множество вершин; А = {ai }, i = 1, 2, ..., 5– множество дуг, причем А = {(х7, х5), (х5, х3), (х3, х5 ), (х4, х6), (х6, х4), (х7, х1) }  

 (2) G = (Х, А), где Х = {хi}, i = 1, 2, …,8– множество вершин; А = {ai }, i = 1, 2, ..., 7– множество дуг, причем А = {(х1, х3), (х2, х4), (х2, х6 ), (х3, х5), (х1, х7), (х8 , х6), (х7 , х1) } 

 (3) G = (Х, А), где Х = {хi}, i = 1, 2, …,8 – множество вершин; А = {ai }, i = 1, 2, ...– множество дуг, причем А = {(х1, х3), (х2, х4), (х2, х6 ), (х2, х8), (х3, х5), (х3 , х7), (х4 , х6), (х6, х8) } 


Номер 3
Для графа   G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда  i+j < 10files

Ответ:

 (1) G = (Х, А), где Х = {хi}, i = 1, 2, …, 8 – множество вершин; А = {ai }, i = 1, 2, ..., 7– множество дуг, причем А = {(х1, х2), (х4, х5), (х2, х4 ), (х2, х3), (х3, х5), (х4 , х1), (х7 , х1), }  

 (2) G = (Х, А), где Х = {хi}, i = 1, 2, …,8– множество вершин; А = {ai }, i = 1, 2, ...7 – множество дуг, причем А = {(х1, х2), (х1, х8), (х2, х3 ), (х2, х5), (х3, х5), (х5 , х3), (х3 , х4), (х7 , х1) }  

 (3) G = (Х, А), где Х = {хi}, i = 1, 2, …,8 – множество вершин; А = {ai }, i = 1, 2, ..., 7 – множество дуг, причем А = {(х1, х2), (х2, х3), (х2, х5 ), (х3, х4), (х1, х8), (х1 , х7), (х5 , х3), } 


Упражнение 4:
Номер 1
Найти максимальный сильно связанный подграф, включающий вершину C,  для графа, матрица смежности которого представлена ниже 
ABCDEFGK
A11001000
B00101100
C00101000
D00000001
E00000100
F10000010
G00000001
K00010000

Ответ:

 (1) Gмсс={ B, C, E, F}  

 (2) Gмсс={A, B, C, E, F} 

 (3) Gмсс={A, B, C, F}  


Номер 2
Найти максимальный сильно связанный подграф, включающий вершину Е,  для графа, матрица смежности которого представлена ниже 
ABCDEFGK
A11001000
B00101100
C00101000
D00000001
E00000100
F10000010
G00000001
K00010000

Ответ:

 (1) Gмсс={ B, C, E, F}  

 (2) Gмсс={A, B, C, E, F}  

 (3) Gмсс={A, B, E, F}  


Номер 3
Найти максимальный сильно связанный подграф, включающий вершину F,  для графа, матрица смежности которого представлена ниже
ABCDEFGK
A11001000
B00101100
C00101000
D00000001
E00000100
F10000010
G00000001
K00010000

Ответ:

 (1) Gмсс={ B, C, E, F}  

 (2) Gмсс={A, B, C, E, F} 

 (3) Gмсс={A, B, E, F}  


Упражнение 5:
Номер 1
Какие из приведенных на рисунке графов являются сильно связными?files

Ответ:

 (1) a, d, e  

 (2) a, d  

 (3)


Номер 2
Какие из приведенных на рисунке графов являются односторонне связными?files

Ответ:

 (1) d, e  

 (2) a, d 

 (3)


Номер 3
Какие из приведенных на рисунке графов являются слабо связными?files

Ответ:

 (1) b, f  

 (2) b, c, f 

 (3) c, f 


Упражнение 6:
Номер 1
Выделить в графе на рисунке с сильную компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х2, х3, х4, х5 >  

 (2) < х2, х4, х5 >  

 (3) < х4, х5 >  


Номер 2
Выделить в графе на рисунке e сильную компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х1, х2, х4, х5 >  

 (2) < х1, х2, х3, х4, х5 >  

 (3) < х2, х4, х5 >  


Номер 3
Выделить в графе на рисунке f сильную компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х3, х2, х4, х5 >  

 (2) < х2, х4, х5 >  

 (3) < х2, х5 >  


Упражнение 7:
Номер 1
Выделить в графе на рисунке b одностороннюю  компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х2, х3, х5 >  

 (2) < х1, х2, х5 > 

 (3) < х1, х2, х3, х5 >  


Номер 2
Выделить в графе на рисунке а одностороннюю  компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х2, х3, х4, х5> 

 (2) < х2, х3, х4 >  

 (3) < х1, х3, х4 >  


Номер 3
Выделить в графе на рисунке f одностороннюю  компоненту, содержащую максимальное число элементов. files

Ответ:

 (1) < х1, х2, х45 >  

 (2) < х1, х4, х5 >  

 (3) < х12, х3, х45 > 


Упражнение 8:
Номер 1
Для графа на рисунке найти сильную компоненту, содержащую элемент  х1files

Ответ:

 (1) G1 = {х1, х2}  

 (2) G1 = {х1, х2, х8 }  

 (3) G1 = {х1, х7, х8 }  


Номер 2
Для графа на рисунке найти сильную компоненту, содержащую элемент  х5files

Ответ:

 (1) G2 = { х3, х5}  

 (2) G2 = { х3, х4, х5} 

 (3) G2 = { х2, х35}  


Номер 3
Для графа на рисунке найти сильную компоненту, содержащую элемент  х4files

Ответ:

 (1) G2 = { х43}  

 (2) G2 = { х4, х6}  

 (3) G2 = { х4, х36, х7}  




Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 6