Главная / Алгоритмы и дискретные структуры /
Графы и алгоритмы / Тест 9
Номер 3
Ответ:
Графы и алгоритмы - тест 9
Упражнение 1:
Номер 1
Ответ:
Номер 1
Чему равно число независимости графа Q3?
Ответ:
(1) 3
(2) 4
(3) 5
(4) 6
Номер 2
Ответ:
Чему равно кликовое число графаC9 ?
Ответ:
(1) 2
(2) 3
(3) 4
(4) 5
Чему равно число вершинного покрытия графа?
Ответ:
(1) 3
(2) 4
(3) 5
(4) 6
Упражнение 2:
Номер 1
Ответ:
Номер 1
Какие из следующих равенств выполняются для любых графов G1 и G2?
Ответ:
(1) 
(2) 
(3) 
(4) 
Номер 2
Ответ:
Какие из следующих равенств выполняются для любых графов G1 и G2?
Ответ:
(1) 
(2) 
(3) 
(4) 
Номер 3
Ответ:
Какие из следующих равенств выполняются для любых графов G1 и G2?
Ответ:
(1) 
(2) 
(3) 
(4) 
Упражнение 3:
Номер 1
Ответ:
Номер 1
Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?
Ответ:
(1) 6
(2) 9
(3) 18
(4) 27
Номер 3
Ответ:
Сколько максимальных независимых множеств имеется у графа P5?
Ответ:
(1) 1
(2) 2
(3) 3
(4) 4
Упражнение 4:
Номер 1
Ответ:
Номер 1
Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?
Ответ:
(1) 2
(2) 4
(3) 6
(4) 8
Номер 2
Ответ:
Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?
Ответ:
(1) 4
(2) 6
(3) 8
(4) граф K3,5 невозможно добавлением ребер превратить в граф, имеющий эйлеров цикл.
Номер 3
Ответ:
Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?
Ответ:
(1) будет построен маршрут, проходящий через некоторые ребра дважды
(2) будет построен маршрут, не проходящий через некоторые ребра
(3) если в качестве стартовой выбрана концевая вершина, то будет построен эйлеров путь.
(4) если в качестве стартовой выбрана не концевая вершина, то будет построена последовательность вершин, не являющаяся маршрутом
Упражнение 5:
Номер 1
Ответ:
Номер 1
В каких из следующих графов имеется гамильтонов цикл?
Ответ:
(1) K3,3
(2) K3,4
(3) 
(4) 
Номер 2
Ответ:
Сколько листьев будет в дереве путей, построенном для графа K4,4?
Ответ:
(1) 16
(2) 24
(3) 48
(4) 144