Главная / Алгоритмы и дискретные структуры /
Введение в теорию графов / Тест 1
Номер 3
Ответ:
Введение в теорию графов - тест 1
Упражнение 1:
Номер 1
Ответ:
Номер 1
Какого типа граф изображен на рисунке?
Ответ:
(1) орграф
(2) граф
(3) смешанный граф
Номер 2
Ответ:
Является ли граф, изображенный на рисунке орграфом?
Ответ:
(1) не является
(2) является
(3) это смешанный граф
Является ли граф, изображенный на рисунке смешанным графом?
Ответ:
(1) не является
(2) является
Упражнение 2:
Номер 1
Ответ:
Номер 1
Какие вершины инцидентны дугеfв графе на рисунке?
Ответ:
(1) 2
(2) 1, 2, 3
(3) 2, 3
Номер 2
Ответ:
Какие вершины инцидентны дугеdв графе на рисунке?
Ответ:
(1) 1, 3
(2) 1, 2, 3
(3) 2
Номер 3
Ответ:
Какие вершины инцидентны дугеbв графе на рисунке?
Ответ:
(1) 1, 2
(2) 2
(3) 1, 2, 3
Упражнение 3:
Номер 1
Ответ:
Номер 1
Какие дуги инцидентны вершине3в графе на рисунке?
Ответ:
(1)
a
(2)
a, e, f
(3)
d, e, f
Номер 2
Ответ:
Какие дуги инцидентны вершине2в графе на рисунке?
Ответ:
(1)
c
(2)
b, c, f
(3)
e, c, f
Номер 3
Ответ:
Какие дуги инцидентны вершине1в графе на рисунке?
Ответ:
(1)
b, e
(2)
a
(3)
a, b, d, e
Упражнение 4:
Номер 1
Ответ:
Номер 1
Перечислите дуги, являющиеся петлями в графе на рисунке?
Ответ:
(1)
a, c
(2)
c, a, d, e
(3)
d, e
Номер 2
Ответ:
Какие дуги являются петлями в графе на рисунке?
Ответ:
(1)
a, c
(2)
f, c
(3)
c, a, d, e
(4) f
Номер 3
Ответ:
Какие дуги являются петлями в графе на рисунке ?
Ответ:
(1)
d
(2)
d и f
(3)
c и b
Упражнение 5:
Номер 1
Ответ:
Номер 1
Найдите полустепени исхода и захода для вершиных2графа
Ответ:
(1)
d0(х2)=3, dt(х2)=2
(2)
d0(х2)=2, dt(х2)=2
(3)
d0(х2)=2, dt(х2)=1
Номер 2
Ответ:
Найдите полустепени исхода и захода для вершиных3графа
Ответ:
(1)
d0(х3)=3, dt(х3)=2
(2)
d0(х3)=1, dt(х3)=2
(3)
d0(х3)=2, dt(х3)=1
Номер 3
Ответ:
Найдите полустепени исхода и захода для вершиных1(вершина обзначена на рисунке цифрой1) графа
Ответ:
(1)
d0(х1)=3, dt(х1)=2
(2)
d0(х1)=2, dt(х1)=2
(3)
d0(х1)=2, dt(х1)=1
Упражнение 6:
Номер 1
Ответ:
Номер 1
Для графа, изображенного на рисунке, дать описание перечислением.
Ответ:
(1)
G4=(Х, А)
, где
Х = { хi }, i = 1, 2, 3,4
– множество вершин;
А = { ai }, i = 1, 2, ..., 5
множество дуг, причем
А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4) }
(2)
G=(Х, А)
, где
Х = { хi }, i = 1, 2, 3,4
– множество вершин;
А = { ai }, i = 1, 2, ..., 5
множество дуг, причем
А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4) }
(3)
G=(Х, А)
, где
Х = { хi }, i = 1, 2, 3,4
– множество вершин;
А = { ai }, i = 1, 2, ..., 5
множество дуг, причем
А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4), (х3, х3) }
Номер 2
Ответ:
Для графа, изображенного на рисунке, дать описание с помощью отображений
Ответ:
(1)
G = (X, Г))
, где
X = {хi}, i = 1, 2, ..., 4
– множество вершин,
Г(х1)= , Г(х2) ={ х1, х4 }, Г(х3) = { х1, х3 }, Г(х4) = { х1 }
– отображения
(2)
G = (X, Г))
, где
X = {хi}, i = 1, 2, ..., 4
– множество вершин,
Г(х2) ={ х1, х4 }, Г(х3) = { х1, х3 }, Г(х4) = { х1 }
– отображения
(3)
G = (X, Г))
, где
X = {хi}, i = 1, 2, ..., 4
– множество вершин,
Г(х1)= , Г(х2) ={ х1, х4 }, Г(х3) = { х1}, Г(х4) = { х1 }
– отображения
Номер 3
Ответ:
ДляG = (X, Г), гдеX = {хi}, i = 1, 2, 3, 4– множество вершин,Г(х1)= , Г(х2) ={ х1, х4 }, Г(х3) = { х1, х3 }, Г(х4) = { х1 }– отображения. Верно ли оно?
Ответ:
(1) не верно
(2) верно
Упражнение 7:
Номер 1
Ответ:
Номер 1
Для графа, представленного на рисунке, дана матрица смежности. Верно ли представлен граф?
| X1 | X2 | X3 | X4 | |
|---|---|---|---|---|
| X1 | 1 | 1 | 0 | 0 |
| X2 | 0 | 0 | 1 | 1 |
| X3 | 0 | 0 | 0 | 0 |
| X4 | 1 | 1 | 1 | 0 |
Ответ:
(1) не верно
(2) верно
Номер 2
Ответ:
Для графа, представленного на рисунке, дана матрица инциденций. Верно ли представлен граф?
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | |
|---|---|---|---|---|---|---|---|
| X1 | 0 | 1 | 1 | 0 | 0 | 0 | -1 |
| X2 | 0 | -1 | 0 | -1 | 1 | 0 | 0 |
| X3 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
| X4 | 0 | 0 | -1 | 1 | 0 | 1 | 1 |
Ответ:
(1) верно
(2) не верно
Номер 3
Ответ:
Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке?
|
|
Ответ:
(1) соответствует матрица инцидентности
(2) не соответствуют обе матрицы
(3) соответствует матрица смежности
Упражнение 8:
Номер 1
Ответ:
Номер 1
По матрице смежности, данной ниже подсчитать количество петель графа.
| 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
Ответ:
(1) петель нет
(2) 3
(3) 2
Номер 2
Ответ:
По матрице смежности, данной ниже подсчитать полустепень исхода второй вершины do(х2) | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
Ответ:
(1)
d0(х2)=2
(2)
d0(х2)=3
(3)
d0(х2)=-2
Номер 3
Ответ:
По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt(х2) | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
Ответ:
(1)
dt(х2)=2
(2)
dt(х2)=3
(3)
dt(х2)=-2
Упражнение 9:
Номер 1
Ответ:
Номер 1
По матрице инциденций найти полустепени исхода для Х2 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| X1 | 1 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
| X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
| X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
| X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
Ответ:
(1)
d0(х2)=3
(2)
d0(х2)=1
(3)
d0(х2)=2
Номер 2
Ответ:
По матрице инциденций найти полустепени захода для Х2 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| X1 | 2 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
| X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
| X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
| X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
Ответ:
(1)
dt(х2)=2
(2)
dt(х2)=3
(3)
dt(х2)=1
Номер 3
Ответ:
Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже):
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| X1 | 1 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
| X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
| X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
| X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
| X1 | X2 | X3 | X4 | X5 | X6 | |
|---|---|---|---|---|---|---|
| X1 | 1 | 1 | 1 | 1 | 0 | 0 |
| X2 | 1 | 0 | 1 | 0 | 0 | 0 |
| X3 | 0 | 0 | 0 | 1 | 0 | 1 |
| X4 | 0 | 0 | 0 | 0 | 1 | 0 |
| X5 | 0 | 0 | 0 | 0 | 0 | 0 |
| X6 | 0 | 0 | 0 | 0 | 1 | 0 |
Ответ:
(1) соответсвует только для неориентированного графа
(2) не соответствует
(3) соответсвует