игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 16

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

Упражнение 1:
Номер 1
Дано непустое конечное множество math и семейство его подмножеств math . В каких из перечисленных ниже случаев пара math является матроидом?

Ответ:

 (1) math состоит из всех непустых подмножеств множества math 

 (2) math состоит из всех подмножеств множества math 

 (3) math 

 (4) math состоит из всех подмножеств мощности не более k(k задано) 


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

Ответ:

 (1) mathсостоит из всех множеств ребер остовных подграфов графа math 

 (2) mathсостоит из всех множеств ребер остовных лесов графа math 

 (3) mathсостоит из всех паросочетаний графа math 

 (4) mathсостоит из всех реберных покрытий графа math 


Номер 3
Дан граф math с множеством вершин math, math - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара math является матроидом,?

Ответ:

 (1) для любого графа math 

 (2) для любого двудольного графа math 

 (3) для полного графа math 

 (4) для любого графа math, в котором каждая компонента компонента связности является полным графом 


Упражнение 2:
Номер 1
Что произойдет, если алгоритм СПО применить к матроиду,  на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса). 

Ответ:

 (1) при любой весовой функции будет найдено независимое множество матроида, имеющее наибольший вес  

 (2) может быть найдено независимое множество не наибольшего веса 

 (3) результатом работы алгоритма может быть множество, не являющееся независимым 

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


Номер 2
Пусть math - матроид и на множестве math задана весовая функция math с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества math упорядочиваются не по убыванию, а по возрастанию весов?

Ответ:

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

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

 (3) если все веса отрицательны, то будет найдено независимое множество наименьшего веса 

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


Упражнение 3:
Номер 1
В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
 В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Ответ:

 (1) 10 

 (2) 13 

 (3) 16 

 (4) 19 


Номер 3
В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 4:
Номер 1
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса  a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


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

Ответ:

 (1) существует геодезическое дерево, содержащее ребро math  

 (2) каждое геодезическое дерево содержит ребро math 

 (3) существует геодезическое дерево, содержащее оба ребра math  

 (4) если ребра math и math не имеют общей вершины, то существует геодезическое дерево, содержащее оба ребра math 


Упражнение 5:
Номер 1
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро math, math,  имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро math, math, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

Ответ:

 (1)

 (2) 10 

 (3) 15 

 (4) 20 


Упражнение 6:
Номер 1
Пусть каждая из функций math и math является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math для каждого ребра math 




Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы / Тест 16