What is a Graph? · Basic Graphs

Lesson 10

Nikolai Chukhin · Alexander S. Kulikov

In many applications, one deals with rooted trees. A rooted tree is just a tree with one node designated as the root. Then, for each node, one can measure its distance to the root. This, in turn, allows us to draw a tree in a layered manner: the root goes on top, its neighbors are located on the next layer below the root, and so on. In such a drawing, the neighbors of a node \(v\) that are located below it are called the children of \(v\) whereas its only neighbor above \(v\) is called the parent of \(v\) (hence, the root node has no parent).

To give an example, consider the following tree.

Now, let's make it rooted by designating the node \(3\) as the root. We draw the tree from top to bottom starting from the root. To do that, imagine that the nodes are balls and the edges are threads and we hang up the tree by its root node.

In this rooted tree,
  • \(3\) is the root;

  • the children of \(1\) are \(\{4, 2, 6\}\);

  • the parent of \(7\) is \(6\);

  • \(\{14, 11, 12, 4, 2, 9, 10\}\) are leaves.

The following code shows that one can also use orbits (rather than horizontal lines) as levels. 

from networkx import balanced_tree, nx_agraph

tree = balanced_tree(2, 5)
for layout in ('dot', 'twopi'):
    nx_agraph.to_agraph(tree).draw(f'b_{layout}.png', prog=layout)