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

Правильный ответ:

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

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

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

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

• # Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
• # Чему равны хроматические индексы графов K3,3 и C7 ?
• # В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
• # Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
• # В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее