Главная / Алгоритмы и дискретные структуры /
Введение в теорию графов / Тест 4
Введение в теорию графов - тест 4
Упражнение 1:
Номер 1
Для графа, представленного на рисунке 1 построить матрицу достижимости R
а | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 0 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 1 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 1 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 1 |
---|
| б | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 0 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 0 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 0 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 0 |
---|
| в | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 1 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 1 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 1 |
---|
|
Ответ:
 (1) б 
 (2) а 
 (3) в 
Номер 2
Какая из представленных матриц достижимости соответствует графу на рисунке 1?
а | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 0 | 0 | 0 | 1 | 1 | 1 |
---|
R= | X2 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 0 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 0 |
---|
| б | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
R= | X2 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
| X3 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X6 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
|
Ответ:
 (1) а 
 (2) б 
 (3) в 
Номер 3
Для графа, представленного на рисунке построить матрицу достижимости и определить для какой из вершин графа достижимо наибольшее число вершин.
Ответ:
 (1) Х1
 
 (2) Х2
 
 (3) Х1 и Х2
 
Упражнение 2:
Номер 1
Для графа, приведенного на рисунке 1, найти матрицу контрдостижимости.
а | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
| б | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 0 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
|
Ответ:
 (1) а 
 (2) в 
 (3) б 
Номер 2
Какая из представленных матриц контрдостижимости соответствует графу на рис. 1?
а | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 0 | 0 | 0 | 1 | 1 | 1 |
---|
Q= | X2 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 0 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 0 |
---|
| б | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
Q= | X2 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
Q= | X2 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
| X3 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X6 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
|
Ответ:
 (1) а 
 (2) б 
 (3) в 
Номер 3
Для графа, представленного на рисунке построить матрицу контрдостижимости и определить какая из вершин достижима для наибольшего числа вершин графа.
Ответ:
 (1) Х1
 
 (2) Х4
 
 (3) Х2
 
Упражнение 3:
Номер 1
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1
и х7.
Ответ:
 (1) {х1, х2, х3, х4 }
 
 (2) {х1, х2, х4, х7}
 
 (3) { х1, х2, х3, х4, х7}
 
Номер 2
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1
и х6
.
Ответ:
 (1) {х1, х2, х3, х4, х6, х7}
 
 (2) {х1, х2, х3, х4, х7}
 
 (3) {х1, х2, х5, х4 }
 
Номер 3
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1
и х3
.
Ответ:
 (1) {х1, х2, х3, х7}
 
 (2) {х1, х2, х3, х4 , х7}
 
 (3) {х1, х2, х3, х4}
 
Упражнение 4:
Номер 1
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 2.
Ответ:
 (1) между F
и A
 
 (2) между D
и B
 
 (3) между E
и C
 
Номер 2
Для графа, данного на рисунке найти количество путей длиной 2 между всеми вершинами графа.
Ответ:
 (1) 8 
 (2) 18 
 (3) 13 
Номер 3
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F
и C
или D
и B
Ответ:
 (1) одинаковое количество 
 (2) между D
и B
 
 (3) между F
и C
 
Упражнение 5:
Номер 1
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 3.
Ответ:
 (1) между D
и B
 
 (2) между A
и D
 
 (3) между A
и C
 
Номер 2
Для графа, данного на рисунке найти количество путей длиной 3 между всеми вершинами графа.
Ответ:
 (1) 13 
 (2) 9 
 (3) 11 
Номер 3
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: A
и C
или B
и D
Ответ:
 (1) между A
и C
 
 (2) одинаковое количество 
 (3) между B
и D
 
Упражнение 6:
Номер 1
Для графа, данного на рисунке найти количество путей длиной 4 между всеми вершинами графа
Ответ:
 (1) 14 
 (2) 24 
 (3) 15 
Номер 2
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 4.
Ответ:
 (1) между B
и A
 
 (2) между A
и C
 
 (3) между D
и C
 
 (4) между D
и B
 
Номер 3
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F
и C
или E
и C
Ответ:
 (1) между F
и C
 
 (2) одинаковое количество 
 (3) между E
и C