Рационализация переборных алгоритмов

1. Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?

Варианты

2 3 <<<< 4 5

Ответ: 3

2. Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными? Варианты

6 7 <<<< 8 9

Ответ: 7

3.Чему равно хроматическое число графа ?

Варианты

2 3 4 5 <<<<

Ответ: 5

4. Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?

Варианты

3 4 <<<< 5 6

Ответ: 4

1. К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

Варианты

2 3 4 <<<< 5

Ответ: 4

4. Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?

Варианты

а) степени вершин не превосходят 2

б) нет циклов нечетной длины

в) аждая компонента связности - цепь

г) каждая компонента связности - цикл четной длины или цепь.<<<<

Ответ: Г

2. Какое наименьшее число ребер нужно удалить из графа , чтобы превратить его в хордальный?

Варианты

2 3 4<<<< 5

Ответ: 4

1. Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?

Варианты

а) удаление ребра

б) добавление нового ребра

в) удаление вершины <<<<

г) добавление новой вершины и ребер, соединяющих ее со всеми "старыми" вершинами<<<<

Ответ: В,Г

1.Какие из следующих равенств выполняются для любых графов G1 и G2?

Варианты

а)

б)<<

в)<<<<

г)

Ответ: Б,В

1.Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?

Варианты

а) б)<<<

в) г) <<<<

Ответ: Б,Г

4. Чему равны хроматические индексы графов K3,3 и C7 ?

Варианты

а) 3 и 2 б) 3 и 3 <<<<

в) 4 и 2 г) 4 и 3

Ответ: Б

3. Что происходит с хроматическим числом графа при удалении ребра?

Варианты

а) увеличивается

б) уменьшается

в) уменьшается или не изменяется <<<<

г) может увеличиться, уменьшиться или остаться прежним

Ответ: Г

Оптимальные каркасы

1. В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?

Варианты

а) выбранные ребра образуют дерево

б) выбранные ребра образуют лес

в) некоторые из выбранных ребер могут образовать цикл <<<<

г) если веса всех ребер графа различны, то выбранные ребра образуют лес<<<

Ответ: В,Г

2. Пусть - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?

Варианты

а) существует оптимальный каркас, содержащий ребро <<<

б) существует оптимальный каркас, содержащий оба ребра <<<

в) существует оптимальный каркас, содержащий все три ребра

г) если ребра не образуют цикла, то существует оптимальный каркас, содержащий все эти ребра<<<

Ответ: А, Б, Г

3. В графе с весовой функцией строится каркас с помощью алгоритма Краскала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?

Варианты

а) <<<

б) ребро может не иметь общих вершин ни с одним из ребер <<<

в) ребро может иметь общую вершину с несколькими из ребер <<<

г) ребро имеет общую вершину ровно с одним из ребер

Ответ: А, Б, В

4. Сколько ребер нужно добавить к наибольшему паросочетанию графа , чтобы получить наименьшее реберное покрытие этого графа?

Варианты

2 3 4 <<<< 5

Ответ: 4

5. Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a.Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?

Варианты

а) если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания <<<<<

б) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания

в) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a

г) любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T

Ответ: А

1. В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?

Варианты

14 15 16 <<<< 17

Ответ: 16

4. Сколько различных наибольших паросочетаний имеется в графеK5 ?

Варианты

5 10 15 <<<< 20

Ответ: 15

3. В графе с весовой функцией строится каркас с помощью алгоритма Прима. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?

Варианты

а)

б) ребро может не иметь общих вершин ни с одним из ребер

в) ребро может иметь общую вершину с несколькими из ребер <<<

г) ребро имеет общую вершину ровно с одним из ребер

Ответ: В

5. Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?

Варианты

а) если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания <<<

б) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания

в) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a<<<

г) любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T<<<<

Ответ: А, В, Г

1. В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?

Варианты

10 11 <<<< 12 13

Ответ: 11

4. Сколько ребер нужно удалить из наименьшего реберного покрытия графа, чтобы получить наибольшее паросочетание этого графа?

Варианты

2 3 <<< 4 5

Ответ: 3