Definition of rooted graphs

723 Views Asked by At

Wiki defined a rooted graph as a graph in which one vertex has been distinguished as a root.

What do they exactly mean by a root? Is it when every other vertex is the extremity of a path coming from the root? If yes then rooted graphs should be connected, right?

2

There are 2 best solutions below

0
On

If this is Wikipedia's definition, then there is nothing more to be said: a rooted graph is, within (that page on) Wikipedia, just a graph with a distinguished node. In particular, it need not be connected.

I have personally never encountered a "root" outside of a tree, and trees are by definition connected -- presumably in practice the graphs you are interested in will be connected ones.

1
On

I've never heard anyone talk about a "root" when they weren't talking about a tree, and as such a connected graph.

And Wikipedia (as any other page) is free to define whatever they want to mean whetever they want, and then it means exactly that on that page.

But you thoughts about all other vertices being extremities is not right (or uses another definition of extremity than me). Consider the graph:

O-----O-----O-----O

We could designate any of the four nodes/vertices as the root, but there would be at least one other node not being an extremity.