Главная /
Графы и их применение /
Как из связного графа получить каркас?
Как из связного графа получить каркас?
вопросПравильный ответ:
известно, что в связном графе
G
удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
в связном графе
G
удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
чтобы получить из графа
G
каркас, нужно удалить все мосты
чтобы получить из графа
G
каркас, нужно соединить все его компоненты мостами Сложность вопроса
81
Сложность курса: Графы и их применение
81
Оценить вопрос
Комментарии:
Аноним
Если бы не данные подсказки - я бы сломался c этими тестами intuit.
01 июл 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.