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

Question

Мое сомнение мало. Если у графа задние ребра, он односвязный или нет? Под задними краями я имею в виду соединения от дочернего узла до одного из его предков под тем же корнем. Если узел связан с узлом выше него, но не с его предком, то это перекрестный узел. http://en.wikipedia.org/wiki/Polytree

обновление: эта ссылка разъясняет концепцию односвязного графа.

Answer 1

Хороший вопрос. Если у графа есть задние ребра, это не мешает ему быть односвязным. Но это может быть не связано с другими причинами. Например, если график не является ненаправленным.

Answer 2

Если я правильно понимаю ваш вопрос, вы хотите знать, может ли политровое дерево содержать задние ребра (ребра от узла до одного из его предков).

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

Answer 3

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

Однако для графов это не имеет большого значения, и термин связность чаще ассоциируется с достижимостью (т. Е .: есть ли путь от узла к другому?)