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

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

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

Ответ:

 (1) а 

 (2) b 

 (3) с 

 (4) d 

 (5) e 

 (6) f 

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

Ответ:

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

 (2) а, e 

 (3) все 

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

Ответ:

 (1) a 

 (2) b 

 (3) с 

 (4) d 

 (5) ef 

 (6) f 

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

а
X1X2X3X4X5
X101000
X200101
X300001
X400100
X500100
b
X1X2X3X4X5
X101000
X200101
X300011
X400010
X500110


c
X1X2X3X4X5
X101000
X200101
X300011
X400000
X500100

Ответ:

 (1) c 

 (2) b 

 (3) а  

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

files

а
X1X2X3X5X7
X101000
X200101
X300001
X500100
X700100
b
X1X2X3X5X7
X101000
X200110
X300010
X500100
X710010


c
X1X2X3X5X7
X101000
X200101
X300011
X500001
X710100

Ответ:

 (1) c 

 (2) b 

 (3) а  

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

files

а
X2X3X4X5X6
X201010
X300110
X400001
X501000
X600100
b
X2X3X4X5X6
X201000
X300110
X400100
X500010
X610010


c
X2X3X4X5X6
X201000
X300101
X400001
X501001
X610100

Ответ:

 (1) b 

 (2) c 

 (3) a 

Упражнение 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) d 

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

Ответ:

 (1) d, e  

 (2) a, d 

 (3) e 

Номер 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, х4,х5 >  

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

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

Упражнение 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, х3,х5}  

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

Ответ:

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

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

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



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