Graph Terminology: What is an ancestral path?

332 Views Asked by At

Shortest ancestral path: An ancestral path between two vertices v and w in a digraph is a directed path from v to a common ancestor x, together with a directed path from w to the same ancestor x. A shortest ancestral path is an ancestral path of minimum total length. We refer to the common ancestor in a shortest ancestral path as a shortest common ancestor. Note also that an ancestral path is a path, but not a directed path.

enter image description here

I am quite confused by this description for two reasons.

First, what does the sentence - "An ancestral path between two vertices v and w in a digraph is a directed path from v to a common ancestor x, together with a directed path from w to the same ancestor x" - mean because there is no directed path from v to w since the path to the ancestor from v is in the "opposite direction" of the path to the ancestor from w. What I mean is in the picture to the left, it's claimed that the shortest ancestral path is 3-1-5-9-10 but this doesn't make sense because we can't do 1-5 since that direction doesn't exist. It seems that they combined the directed path from v to the ancestor with the directed path from w to the ancestor in the opposite direction, essentially treating the path as undirected.

Second, and relatedly, the first sentence says that an ancestral path is a "directed path" but the last sentence says "Note also that an ancestral path is a path, but not a directed path."

Can someone clarify?

1

There are 1 best solutions below

1
On BEST ANSWER

The sentence

An ancestral path between two vertices $v$ and $w$ in a digraph is a directed path from $v$ to a common ancestor $x$, together with a directed path from $w$ to the same ancestor $x$.

is not saying that an ancestral path is a directed path. It's saying that an ancestral path is made up of two pieces. One piece is a directed path from $v$ to $x$. The other piece is a directed path from $w$ to $x$.

If we ignore the orientations, and allow our paths to backtrack, then we can combine the first directed path with the reverse of the second, and get an undirected path. This is what the sentence

Note also that an ancestral path is a path, but not a directed path.

is saying.

Not everyone's definitions allow a path to repeat edges (or vertices), but maybe the source you're consulting does. In any case, when we take a shortest ancestral path, there will be no repetition, so this will be a path (undirected path) by anyone's definition.