Главная / Алгоритмы и дискретные структуры /
Графы и алгоритмы / Тест 16
Графы и алгоритмы - тест 16
Упражнение 1:
Номер 1
Дано непустое конечное множество и семейство его подмножеств . В каких из перечисленных ниже случаев пара является матроидом?
Ответ:
 
(1) состоит из всех непустых подмножеств множества
 
 
(2) состоит из всех подмножеств множества
 
 
(3)  
 
(4) состоит из всех подмножеств мощности не более k(k задано) 
Номер 2
Дан граф с множеством ребер . Для каких из перечисленных ниже семейств подмножеств множества пара является матроидом для любого графа ?
Ответ:
 
(1) состоит из всех множеств ребер остовных подграфов графа
 
 
(2) состоит из всех множеств ребер остовных лесов графа
 
 
(3) состоит из всех паросочетаний графа
 
 
(4) состоит из всех реберных покрытий графа
 
Номер 3
Дан граф с множеством вершин , - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара является матроидом,?
Ответ:
 
(1) для любого графа
 
 
(2) для любого двудольного графа
 
 
(3) для полного графа
 
 
(4) для любого графа
, в котором каждая компонента компонента связности является полным графом 
Упражнение 2:
Номер 1
Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
Ответ:
 (1) при любой весовой функции будет найдено независимое множество матроида, имеющее наибольший вес  
 (2) может быть найдено независимое множество не наибольшего веса 
 (3) результатом работы алгоритма может быть множество, не являющееся независимым 
 (4) при любой весовой функции будет найдена база матроида, имеющая наибольший вес 
Номер 2
Пусть - матроид и на множестве задана весовая функция с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества упорядочиваются не по убыванию, а по возрастанию весов?
Ответ:
 
(1) при любой функции
будет найдено независимое множество матроида, имеющее наименьший вес  
 
(2) результатом работы алгоритма может быть множество, не принадлежащее
 
 (3) если все веса отрицательны, то будет найдено независимое множество наименьшего веса 
 
(4) при любой функции
будет найдена база матроида, имеющая наименьший вес 
Упражнение 3:
Номер 1
В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Ответ:
 (1) 1 
 (2) 2 
 (3) 3 
 (4) 4 
Номер 2
В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Ответ:
 (1) 10 
 (2) 13 
 (3) 16 
 (4) 19 
Номер 3
В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Ответ:
 (1) 1 
 (2) 2 
 (3) 3 
 (4) 4 
Упражнение 4:
Номер 1
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4)  
Номер 2
Пусть и - ребра с наименьшими весами в некотором взвешенном графе, причем . Какие из следующих утверждений верны для любого графа и любой весовой функции?
Ответ:
 
(1) существует геодезическое дерево, содержащее ребро
 
 
(2) каждое геодезическое дерево содержит ребро
 
 
(3) существует геодезическое дерево, содержащее оба ребра
 
 
(4) если ребра
и
не имеют общей вершины, то существует геодезическое дерево, содержащее оба ребра
 
Упражнение 5:
Номер 1
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
Ответ:
 (1) 4 
 (2) 5 
 (3) 6 
 (4) 7 
Номер 2
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
Ответ:
 (1) 5 
 (2) 6 
 (3) 7 
 (4) 8 
Номер 3
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
Ответ:
 (1) 5 
 (2) 10 
 (3) 15 
 (4) 20 
Упражнение 6:
Номер 1
Пусть каждая из функций и является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?
Ответ:
 
(1)  
 
(2)  
 
(3)  
 
(4) для каждого ребра