Can we have an undirected tree?

user_1826912 0
Viewed 29

I've read in many places that a tree is a special case of a directed acyclic graph where each vertex has only one predecessor. This implies a tree must be directed. But then there are other definitions that say: "A tree is a type of connected graph. An directed graph is a tree if it is connected, has no cycles and all vertices have at most one parent. An undirected graph is considered a tree if it is connected, has $|V|-1$ edges and is acyclic (a graph that satisfies any two of these properties satisfies all three)." (from here: https://en.wikibooks.org/wiki/Graph_Theory/Trees).

This seems to suggest a tree can be undirected as well. I thought the catch was that a graph that is acyclic has to be directed. Otherwise, a single edge of an undirected graph becomes a cycle since you can traverse that edge and back, ending up at the same vertex.

But then, I came across problem 22.4-3 that says "Give an algorithm that determines weather or not an undirected graph G contains a cycle".

Now I'm confused. If a tree is a special case of a DAG, it must be directed. But other definitions suggest there can be undirected trees as well. And why doesn't a single edge of an undirected graph make it cyclic?

cycle tree graph
1 Answers

There are different definitions of tree, depending on context:

A tree in graph theory is defined as

an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

A tree in computer science is defined as

a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent.

This article continues with explaining the difference:

Viewed as a whole, a tree data structure is an ordered tree, generally with values attached to each node. Concretely, it is (if required to be non-empty):

  • A rooted tree with the "away from root" direction (a more narrow term is an "arborescence"), meaning:
    • A directed graph,
    • whose underlying undirected graph is a tree (any two vertices are connected by exactly one simple path),
    • with a distinguished root (one vertex is designated as the root),
    • which determines the direction on the edges (arrows point away from the root; given an edge, the node that the edge points from is called the parent and the node that the edge points to is called the child), together with:
  • an ordering on the child nodes of a given node, and
  • a value (of some data type) at each node.

An undirected edge is not considered a cycle. According to Wikipedia the definition of a cycle is:

a non-empty trail in which only the first and last vertices are equal.

And a property of a trail is that it

...is a walk in which all edges are distinct.

user_54598390
Related