Определение того, является ли ориентированный или неориентированный граф деревом

Я хотел бы узнать о быстром алгоритме, чтобы определить, является ли ориентированный или неориентированный граф деревом.

Это сообщение, похоже, касается это, но не очень понятно; по этой ссылке, если граф ациклический, то это дерево. Но если вы рассмотрите ниже ориентированный и неориентированный графы: на мой взгляд, только графы 1 и 4 являются деревьями. Полагаю, 3 не является ни циклическим, ни деревом.

введите описание изображения здесь

Что необходимо проверить, чтобы эффективно определить, является ли ориентированный или неориентированный граф деревом? И сделаем еще один шаг вперед: если дерево существует, то это двоичное дерево или нет?


graph algorithm tree cyclic
person brain storm    schedule 13.12.2013    source источник
comment
Небольшое примечание: связанный вопрос действительно касается только неориентированного случая. Насколько я понимаю, вы хотели разобраться с направленным делом? В направленном случае есть и другие случаи, о которых следует беспокоиться (A -> B <- C дерево?).   -  person Dennis Meng    schedule 13.12.2013

Ответы (3)


arrow_upward
39
arrow_downward

Для ориентированного графа:

  • Найти вершину без входящих ребер (если таких вершин больше одной или нет, не получится).

  • Сделайте в ширину или поиск в глубину из этой вершины. Если вы встретите уже посещенную вершину, это не дерево.

  • Если вы закончили и остались неисследованные вершины, это не дерево - граф не связан.

  • В противном случае это дерево.

  • Чтобы проверить двоичное дерево, дополнительно проверьте, имеет ли каждая вершина не более 2 исходящих ребер.

Для неориентированного графа:

  • Проверьте цикл с помощью простого поиска в глубину (начиная с любой вершины) - "Если неисследованное ребро ведет к узлу, который был посещен ранее, тогда граф содержит цикл ». Если есть цикл, это не дерево.

  • Если описанный выше процесс оставляет некоторые вершины неисследованными, это не дерево, потому что оно не связано.

  • В противном случае это дерево.

  • Чтобы проверить бинарное дерево, если граф имеет более одной вершины, дополнительно проверьте, что все вершины имеют 1-3 ребра (1 для родительского и 2 для дочерних).

    Проверять наличие корня, то есть, содержит ли одна вершина 1-2 ребра, не требуется, поскольку в ациклическом связном неориентированном графе должны быть вершины с 1-2 ребрами.

    Обратите внимание, что определение корня в общем случае невозможно (это может быть возможно в особых случаях), поскольку во многих неориентированных графах более одного узла можно сделать корнем, если мы сделаем его двоичным деревом.

person Bernhard Barker    schedule 13.12.2013
comment
Что касается пункта 1: я мог бы иметь частное поле массива OutgoingEdge в классе Vertex, чтобы при добавлении каждого ребра в граф я мог обновить это поле. для каждой вершины я проверяю, равна ли длина этого массива ›1. если да, то это не дерево .. - person brain storm; 13.12.2013
comment
Что касается пункта 2: это не что иное, как обнаружение цикла, верно? любая конкретная причина для BFS по DFS - person brain storm; 13.12.2013
comment
относительно пункта 3: я могу получить эту информацию из поля массива outgoingEdge, если его длина ‹= 2 - person brain storm; 13.12.2013
comment
как вы упомянули, проверка корня в неориентированном ациклическом связном графе не является существенной, потому что существует возможность нескольких узлов, которые могут действовать как корни? - person brain storm; 13.12.2013
comment
#1 Имеет смысл, обычно так работают списки смежности, которые в основном используются в реализациях графов. #2 Да, я считаю, что вы также можете использовать DFS, нет особых причин для выбора BFS. #3 Да. Да, во многих случаях несколько узлов могут действовать как корень. - person Bernhard Barker; 13.12.2013
comment
Еще один момент: мы должны учитывать, связан ли граф или нет. Если он не связан, даже если у него n - 1 ребро и нет цикла, это еще не означает, что граф является деревом и может быть лесом. Просто хотел упомянуть, что иногда нам может потребоваться проверить количество связанных компонентов в графе, чтобы убедиться, что граф связан. - person Pedram; 06.11.2017
comment
@Pedram: Должен поправиться, ..... даже без цикла, это не обязательно означает, что график - это дерево, а может быть лес ..... - person Pedram; 06.11.2017
comment
@Pedram Отредактировано. - person Bernhard Barker; 06.11.2017
comment
Для ориентированного графа 1: я бы сказал, нет входящих ребер; так как тривиальное дерево с одним узлом вообще не имеет ребер. В этом случае менее четко видны только исходящие ребра. - person Hans Olsson; 07.05.2020

arrow_upward
0
arrow_downward

Если данный неориентированный граф является деревом:

  • граф связан
  • количество ребер равно количеству узлов - 1.
person weiyixie    schedule 25.01.2020

arrow_upward
0
arrow_downward

Неориентированный граф - это дерево, когда выполняются следующие два условия:

  1. Граф представляет собой связный граф.
  2. На графике нет цикла.

Ориентированный граф - это дерево, когда выполняются следующие три условия:

  1. Граф представляет собой связный граф.
  2. На графике нет цикла.
  3. У каждого узла, кроме корневого, должен быть ровно один родитель.
person Joe    schedule 06.05.2020