Графы и алгоритмы

Какие из следующих утверждений верны для любого взвешенного графа?

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

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

если в графе имеются точно три ребра наибольшего веса, то все они принадлежат каждому оптимальному каркасу

если в графе имеются точно два ребра наибольшего веса, то они оба принадлежат каждому оптимальному каркасу(Верный ответ)

если в графе имеются точно три ребра наибольшего веса и они не образуют цикла, то все они принадлежат каждому оптимальному каркасу(Верный ответ)

если в графе имеется единственное ребро наибольшего веса, то оно принадлежит каждому оптимальному каркасу(Верный ответ)

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

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

Пусть $e_1 ,e_2 , \ldots ,e_m$ - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?

Какие из следующих утверждений справедливы для любого двусвязного графа?

Какие из следующих утверждений верны для любого графа

и любого его подграфа

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

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

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

В графе с весовой функцией

строится каркас с помощью алгоритма Крускала. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

В графе с весовой функцией

строится каркас с помощью алгоритма Прима. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

Пусть

- ребра с наименьшими весами в некотором взвешенном графе, причем $w(e_1 ) \le w(e_2 )$ . Какие из следующих утверждений верны для любого графа и любой весовой функции?