Найдите наибольшее паросочетание с помощью потокового алгоритма.

Вариант 5

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

·

·

·

·

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

· Существует геодезическое дерево, содержащее ребро .

· Каждое геодезическое дерево содержит ребро .

· Существует геодезическое дерево, содержащее оба ребра .

· Если ребра и не имеют общей вершины, то существует геодезическое дерево, содержащее оба ребра .

 

9.5. Найдите максимальный поток.

 

 

10.5. Построить дерево кратчайших путей (геодезическое дерево) с корнем в вершине а с

помощью алгоритма Дейкстры.