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

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

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

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

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

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