Главная / Алгоритмы и дискретные структуры /
Графы и алгоритмы / Тест 2
Номер 3
Ответ:
Графы и алгоритмы - тест 2
Упражнение 1:
Номер 1
Ответ:
Номер 1
Сколько имеется связных абстрактных графов с 4 вершинами?
Ответ:
(1) 5
(2) 6
(3) 7
(4) 8
Номер 2
Ответ:
Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
Ответ:
(1) 2
(2) 3
(3) 4
(4) 5
Сколько имеется абстрактных графов с 4 вершинами радиуса 1?
Ответ:
(1) 3
(2) 4
(3) 5
(4) 6
Упражнение 2:
Номер 1
Ответ:
Номер 1
Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?
Ответ:
(1) 2
(2) 3
(3) 4
(4) 5
Номер 2
Ответ:
Какие из следующих утверждений верны?
Ответ:
(1) граф, дополнительный к связному, всегда связен
(2) граф, дополнительный к связному, всегда несвязен
(3) граф, дополнительный к несвязному, всегда связен
(4) граф, дополнительный к несвязному, всегда несвязен
Номер 3
Ответ:
Какие из следующих утверждений верны для любого графаи любого его подграфа
?
Ответ:
(1) 
(2) 
(3) если - порожденный подграф, то
- порожденный подграф, то
(4) если - остовный подграф, то
- остовный подграф, то
Упражнение 3:
Номер 1
Ответ:
Номер 1
Что происходит с диаметром графа при удалении ребра?
Ответ:
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним.
(4) может увеличиться, уменьшиться или остаться прежним
Номер 2
Ответ:
Что происходит с диаметром графа при удалении вершины?
Ответ:
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним
(4) может увеличиться, уменьшиться или остаться прежним.
Номер 3
Ответ:
Что происходит с радиусом графа при добавлении нового ребра?
Ответ:
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним
(4) может увеличиться, уменьшиться или остаться прежним
Упражнение 4:
Номер 1
Ответ:
Номер 1
Какие из следующих утверждений верны?
Ответ:
(1) любое ребро, соединяющее два шарнира, является перешейком
(2) если два перешейка имеют общую вершину, то эта вершина - шарнир.
(3) любая вершина, инцидентная перешейку, является шарниром
(4) любая вершина, инцидентная перешейку и имеющая степень больше 1, является шарниром.
Номер 2
Ответ:
Какое из следующих утверждений верно?
Ответ:
(1) простой цикл не может проходить через перешеек.
(2) замкнутый маршрут не может проходить через перешеек
(3) замкнутый маршрут не может проходить через шарнир
Номер 3
Ответ:
Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?
Ответ:
(1) 1
(2) 2
(3) 3
(4) 4