В неориентированном графе, для которого была выполнена DFS (чтобы сгенерировать дерево DFS и, таким образом, классифицировать каждое ребро как ребро дерева или как заднее ребро), могут быть циклы в графе, которые состоят только из задних ребер, т. Е. Нет дерева края?
Цикл в неориентированном графе без ребер дерева?
Ответы (1)
Конечно. Возьмем, к примеру, большую клику. Удаление одного дерева DFS из клики оставляет огромное количество ребер и, как следствие, множество циклов.
person
templatetypedef
schedule
11.10.2017