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