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

<<- Назад к вопросам

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

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

$\frac{{f_1 + f_2 }}{2}$ (Верный ответ)

$f(e) = \max \{ f_1 (e),f_2 (e)\}$ для каждого ребра

(Верный ответ)

$\frac{1}{3}f_1 + \frac{2}{3}f_2$ (Верный ответ)

Похожие вопросы

Пусть

- ребра с наименьшими весами в некотором взвешенном графе, причем $w(e_1 ) \le w(e_2 )$ . Какие из следующих утверждений верны для любого графа и любой весовой функции?

Дан граф

с множеством ребер

. Для каких из перечисленных ниже семейств $\Phi$ подмножеств множества

пара $(E,\Phi )$ является матроидом для любого графа

Пусть $(E,\Phi )$ - матроид и на множестве

задана весовая функция

с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества

упорядочиваются не по убыванию, а по возрастанию весов?

Дан граф

с множеством вершин

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

В графе с весовой функцией

строится каркас с помощью алгоритма Крускала. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

В графе с весовой функцией

строится каркас с помощью алгоритма Прима. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

Для некоторого графа построено BFS-дерево с корнем