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

<<- Назад к вопросам

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

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

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

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

через любые три вершины проходит простой цикл

через любые два ребра проходит простой цикл(Верный ответ)

через любые две вершины проходит простой цикл(Верный ответ)

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

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

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

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

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

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

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

Пусть h - высота BFS-дерева, построенного для графа 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 )$ . Какие из следующих утверждений верны для любого графа и любой весовой функции?