Алгоритмы: построение и анализ

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

Какими свойствами обладает высотная фунция h?

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

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

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

она равна расстоянию от вершины до стока

если $(u,v) \in V_f$ , то $h(u) \leq h(v)+1$ (Верный ответ)

если $(u,v) \in V_f$ , то $h(v) \leq h(u)+1$

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

Какими свойствами обладает фунция предпотока?

Пусть h - правильная высотная функция, а ребро (u,v) круто идет вниз. Какие утверждения тогда верны?

Какими свойствами обладает функция потока $f:V\times V \rightarrow R_+$ ?

Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?

Пусть величину d протолкнули на шаге PUSH по ребру (u,v). Какой код тогда отвечает за изменение потоков и излишков?

Пусть явная вершина v соответствует суффиксу abc, тогда reference pair для суффикса abcde это

Сколько вершин в графе иры Ним для начальной позиции {2,2}? (начальную {2,2} и конечную {0,0} тоже считать)

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

Пусть A и B два максимальных покрывающих дерева в графе G. Какое утверждение верно?