Trees¶
Definition: An undirected tree is graph in which there is one, and only one, path between any pairs of nodes. These graphs do not have loops
Definition: A directed tree is a graph such that there exists a single node, called the root, which has no parents, and all other nodes have one parent.
Proposition¶
Any directed tree can be transformed into an undirected tree and vice versa
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
%config InlineBackend.figure_format = "retina"
Directed Tree as an Undirected Tree¶
Since the transformation from a directed tree to an undirected tree is achived through moralization (add extra links between all pairs of parent nodes) then, by definition, every node in the directed tree will have only one parent, except for the root node. Hence, we transform a directed graph to an undirected graph by simply removing the direction of the arrows.
Undirected Tree as a Directed Tree¶
For every maximal clique, if any two pair of cliques share the same node, we create a directed connection from the common node to each of the remaining nodes. To see this, consider the following two examples:
A first example¶
# The undirected graph
G0 = nx.Graph()
G0.add_edges_from([("x1", "x5"), ("x2", "x5"), ("x3", "x5"), ("x4", "x5")])
# The directed graph
G1 = nx.DiGraph()
G1.add_edges_from([("x5", "x1"), ("x5", "x2"), ("x5", "x3"), ("x5", "x4")])
fig, ax = plt.subplots(1, 2, figsize=(12, 3))
nx.draw(G0, labels={node:node for node in G0.nodes}, ax=ax[0])
nx.draw(G1, labels={node:node for node in G1.nodes}, ax=ax[1])
A second example¶
# The undirected graph
G0 = nx.Graph()
G0.add_edges_from([("x1", "x2"), ("x1", "x3"), ("x2", "x4"),
("x2", "x5"), ("x3", "x6"), ("x3", "x7")])
G1 = nx.DiGraph()
G1.add_edges_from([("x1", "x2"), ("x1", "x3"), ("x2", "x4"),
("x2", "x5"), ("x3", "x6"), ("x3", "x7")])
fig, ax = plt.subplots(1, 2, figsize=(12, 3))
nx.draw(G0, labels={node:node for node in G0.nodes}, ax=ax[0])
nx.draw(G1, labels={node:node for node in G1.nodes}, ax=ax[1])
