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