Блог

Я ссылаюсь на определение односвязного графа из Введения в algorithms CLRS 3rd edition, гл.22, упражнение 22.3-13, как A directed graph G = (V,E) is singly connected if G contains at most one simple path from u to v for all vertices u, v belongs to V . Я заметил, что циклы на графике не обязательно означают, что граф не является односвязным, поскольку пути, включающие циклы, не считаются простым путем. Простой цикл в ориентированном графе может быть представлен однозначно набором соответствующих ребер. Давайте рассмотрим некоторый ориентированный граф, удовлетворяющий следующим двум свойствам:
(1) он имеет только дерево и обратные ребра в своем лесу DFS и (2) все множества, представляющие каждый простой цикл в графе, не пересекаются (т. Е. у них нет общего ребра). Теперь мой вопрос: верно ли, что каждый ориентированный граф, удовлетворяющий вышеуказанным двум условиям, должен быть односвязным графом? Или просто условие 1 достаточно для того, чтобы граф был односвязным?Я не могу найти ни одного контрпримера

Я нашел контрпример. Предположим, что этот ориентированный граф G имеет 5 узлов (0, 1, 2, 3, 4) и 6 ребер (0,1), (1,2), (2,0), (2,3), (3,4), (4,0). Если мы запустим DFS на любом узле из набора (3, 4), у нас будут только дерево и обратные ребра. Очевидно, что он удовлетворяет условию 1, но не 2, и это не односвязный граф, поскольку существует два простых пути от узла 1 к 0 ( 1->2->3->4->0 и 1->2->0 ). Удивительно, но если мы запустим DFS с любого другого узла (т. Е. с 0, 1, 2), его лес DFS будет содержать по крайней мере одно переднее ребро. Наблюдается, что наборы ребер, представляющих простые циклы в этом графике, являются {(0,1), (1,2), (2,0)} и {(0,1), (1,2), (2,3), (3,4), (4,0)} который разделяет ребра (0,1) и (1,2). Леса DFS, полученные путем выбора начального узла из любого из узлов в пределах ребер, общих для обоих наборов (т. Е. Из 0, 1, 2), приводят по крайней мере к одному переднему краю, тогда как выбор начального узла из любого из оставшихся узлов (т. Е. Из 3, 4) приводит только к дереву и обратным ребрам в их лесах DFS. Это доказывает, что условия 1 недостаточно для односвязности ориентированного графа.