Графы и алгоритмы

Упражнение 1:

Номер 1

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

Ответ:

(1) 14

(2) 15

(3) 16

(4) 17

Номер 2

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

Ответ:

(1) 10

(2) 11

(3) 12

(4) 13

Номер 3

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

Ответ:

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

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

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

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

Упражнение 2:

Номер 1

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

Ответ:

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

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

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

(4) если ребра math

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

Номер 2

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

Ответ:

(1) если в графе имеется единственное ребро наибольшего веса, то оно принадлежит каждому оптимальному каркасу

(2) если в графе имеются точно два ребра наибольшего веса, то они оба принадлежат каждому оптимальному каркасу

(3) если в графе имеются точно три ребра наибольшего веса, то все они принадлежат каждому оптимальному каркасу

(4) если в графе имеются точно три ребра наибольшего веса и они не образуют цикла, то все они принадлежат каждому оптимальному каркасу

Номер 3

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

Ответ:

(1)

(2) ребро math

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

(3) ребро math

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

(4) ребро math

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

Упражнение 3:

Номер 1

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

Ответ:

(1)

(2) ребро math

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

(3) ребро math

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

(4) ребро math

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

Упражнение 4:

Номер 1

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 2

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

Ответ:

(1) 2

(2) 3

(3) 4

(4) 5

Номер 3

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

Ответ:

(1) 5

(2) 10

(3) 15

(4) 20

Упражнение 5:

Номер 1

Какие из следующих утверждений верны?

Ответ:

(1) два чередующихся пути могут иметь две общих вершины.

(2) два чередующихся пути могут иметь три общих вершины

(3) если в графе относительно некоторого паросочетания имеются два увеличивающих пути, то существует паросочетание, в котором на два ребра больше

(4) если в графе относительно некоторого паросочетания имеются два непересекающихся увеличивающих пути, то существует паросочетание, в котором на два ребра больше

Номер 2

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

Ответ:

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

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

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

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

Номер 3

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

Ответ:

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

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

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

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

Графы и алгоритмы - тест 13