Главная / Алгоритмы и дискретные структуры /
Введение в теорию графов / Тест 6
Введение в теорию графов - тест 6
Упражнение 1:
Номер 1
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его подграфами?
Ответ:
 (1) а 
 (2) b 
 (3) с 
 (4) d 
 (5) e 
 (6) f 
Номер 2
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его остовными подграфами?
Ответ:
 (1) а, с, d, e, f 
 (2) а, e 
 (3) все 
Номер 3
Дан граф на риунке 1. Какой из приведенных на рисунке 2 графов является для него порожденным подграфом?
Ответ:
 (1) a 
 (2) b 
 (3) с 
 (4) d 
 (5) ef 
 (6) f 
Упражнение 2:
Номер 1
Для графа G = (X, A)
, представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3,х4,х5}
а | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 1 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X4 | 0 | 0 | 0 | 1 | 0 |
---|
X5 | 0 | 0 | 1 | 1 | 0 |
---|
| c | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X4 | 0 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
|
Ответ:
 (1) c 
 (2) b 
 (3) а  
Номер 2
Для графа G = (X, A)
, представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3, ,х5, х7}
а | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 1 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 1 | 0 | 0 | 1 | 0 |
---|
| c | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X5 | 0 | 0 | 0 | 0 | 1 |
---|
X7 | 1 | 0 | 1 | 0 | 0 |
---|
|
Ответ:
 (1) c 
 (2) b 
 (3) а  
Номер 3
Для графа G = (X, A)
, представленного на рисунке 1, описать матрицей смежности порожденный подграф {х2,х3, х4,х5, х6}
а | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 1 | 1 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 1 | 1 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 |
---|
X6 | 1 | 0 | 0 | 1 | 0 |
---|
| c | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 1 | 0 | 1 |
---|
X4 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 0 | 1 |
---|
X6 | 1 | 0 | 1 | 0 | 0 |
---|
|
Ответ:
 (1) b 
 (2) c 
 (3) a 
Упражнение 3:
Номер 1
Для графа G = (X, A)
, представленного на рисунке, описать явно остовный подграф(X, A’)
, где xi,xj ∈ A'
тогда и только тогда, когда i+j
нечетно
Ответ:
 (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
четно
Ответ:
 (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 < 10
Ответ:
 (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
, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Ответ:
 (1) Gмсс={ B, C, E, F}
 
 (2) Gмсс={A, B, C, E, F}
 
 (3) Gмсс={A, B, C, F}
 
Номер 2
Найти максимальный сильно связанный подграф, включающий вершину Е
, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Ответ:
 (1) Gмсс={ B, C, E, F}
 
 (2) Gмсс={A, B, C, E, F}
 
 (3) Gмсс={A, B, E, F}
 
Номер 3
Найти максимальный сильно связанный подграф, включающий вершину F
, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Ответ:
 (1) Gмсс={ B, C, E, F}
 
 (2) Gмсс={A, B, C, E, F}
 
 (3) Gмсс={A, B, E, F}
 
Упражнение 5:
Номер 1
Какие из приведенных на рисунке графов являются сильно связными?
Ответ:
 (1) a, d, e
 
 (2) a, d
 
 (3) d 
Номер 2
Какие из приведенных на рисунке графов являются односторонне связными?
Ответ:
 (1) d, e
 
 (2) a, d 
 (3) e 
Номер 3
Какие из приведенных на рисунке графов являются слабо связными?
Ответ:
 (1) b, f
 
 (2) b, c, f 
 (3) c, f 
Упражнение 6:
Номер 1
Выделить в графе на рисунке с сильную компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х2, х3, х4, х5 >
 
 (2) < х2, х4, х5 >
 
 (3) < х4, х5 >
 
Номер 2
Выделить в графе на рисунке e сильную компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х1, х2, х4, х5 >
 
 (2) < х1, х2, х3, х4, х5 >
 
 (3) < х2, х4, х5 >
 
Номер 3
Выделить в графе на рисунке f сильную компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х3, х2, х4, х5 >
 
 (2) < х2, х4, х5 >
 
 (3) < х2, х5 >
 
Упражнение 7:
Номер 1
Выделить в графе на рисунке b одностороннюю компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х2, х3, х5 >
 
 (2) < х1, х2, х5 >
 
 (3) < х1, х2, х3, х5 >
 
Номер 2
Выделить в графе на рисунке а одностороннюю компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х2, х3, х4, х5>
 
 (2) < х2, х3, х4 >
 
 (3) < х1, х3, х4 >
 
Номер 3
Выделить в графе на рисунке f одностороннюю компоненту, содержащую максимальное число элементов.
Ответ:
 (1) < х1, х2, х4,х5 >
 
 (2) < х1, х4, х5 >
 
 (3) < х1,х2, х3, х4,х5 >
 
Упражнение 8:
Номер 1
Для графа на рисунке найти сильную компоненту, содержащую элемент х1
Ответ:
 (1) G1 = {х1, х2}
 
 (2) G1 = {х1, х2, х8 }
 
 (3) G1 = {х1, х7, х8 }
 
Номер 2
Для графа на рисунке найти сильную компоненту, содержащую элемент х5
Ответ:
 (1) G2 = { х3, х5}
 
 (2) G2 = { х3, х4, х5}
 
 (3) G2 = { х2, х3,х5}
 
Номер 3
Для графа на рисунке найти сильную компоненту, содержащую элемент х4
Ответ:
 (1) G2 = { х4,х3}
 
 (2) G2 = { х4, х6}
 
 (3) G2 = { х4, х3,х6, х7}