Найдите наибольшее паросочетание с помощью потокового алгоритма.
Вариант 5
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно весаa, bи c. Какое из следующих соотношений обязательно выполняются для этих чисел?
· 
· 
· 
· 
Пусть
и 
– ребра с наименьшими весами в некотором взвешенном графе, причем 
. Какие из следующих утверждений верны для любого графа и любой весовой функции?
· Существует геодезическое дерево, содержащее ребро .
· Каждое геодезическое дерево содержит ребро .
· Существует геодезическое дерево, содержащее оба ребра 
.
· Если ребра и не имеют общей вершины, то существует геодезическое дерево, содержащее оба ребра .
9.5. Найдите максимальный поток.
10.5. Построить дерево кратчайших путей (геодезическое дерево) с корнем в вершине а с
помощью алгоритма Дейкстры.
