TREE GRAPHS
A graph T is called a tree if T is connected and T has no cycles (Figs. (a) and (b)).
A forest G is a graph with no cycles (connected or not connected); hence the connected
components of a forest G are trees.
A graph without cycles is said to be cycle-free.
The tree consisting of a single vertex with no edges is called the degenerate tree.
Theorem: Let G be a graph with n > 1 vertices. Then the following are equivalent:
(i) G is a tree.
(ii) G is a cycle-free and has n − 1 edges.
(iii) G is connected and has n − 1 edges.
This theorem also tells us that a finite tree T with n vertices must have n−1 edges.
For example, the tree in (a) has 9 vertices and 8 edges, and the tree in Fig. (b) has 13 vertices and
12 edges.
Spanning Trees
A subgraph T of a connected graph G is called a spanning tree of G if T is a tree and T includes all
the vertices of G.
Figure shows a connected graph G and spanning trees T1, T2, and T3 of G.
Minimum Spanning Trees
• Suppose G is a connected weighted graph. That is, each edge of G is assigned a nonnegative
number called the weight of the edge.
• Then any spanning tree T of G is assigned a total weight obtained by adding the weights of
the edges in T.
• A minimal spanning tree of G is a spanning tree whose total weight is as small as possible.
KRUSKAL ALGORITHM:
INPUT: connected weighted graph G with n vertices.
Step 1. Arrange the edges of G in order of increasing weights.
Step 2. Draw only the vertices of G.
Step 3. Proceed sequentially as in step 1, add each edge which does not result in a cycle until n-1
edges are added.
Step 4: Stop if a tree is formed.
EXAMPLE: Find a minimal spanning tree of the weighted graph Q in Fig.
Solution: Note that Q has six vertices (n=6), so a minimal spanning tree will have five edges.
1. Order the edges by increasing weights.
2. Successively add edges without forming any
cycles until five edges are included.
This yields the following data:
Edges : BD AE DF BF CE AC AF BE BC
Weight: 3 4 4 5 6 7 7 7 8
Edges BD AE DF BF CE AC AF BE BC
Weight 3 4 4 5 6 7 7 7 8
ADD? YES YES YES NO YES NO YES NO NO
Thus the minimal spanning tree of Q which is obtained contains
the edges
BD, AE, DF, CE, AF
It has weight 24.
EXAMPLE: Find a minimal spanning tree of the weighted graph Q in Fig.
Solution:
A rooted tree is a tree in which one vertex has been designated as the root and
every edge is directed away from the root.
If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting
of a and its descendants and all edges incident to these descendants.
EXAMPLE: Subtree with g as root
For a rooted tree,
If v is a vertex in T other than the root, the parent of v is the
unique vertex u such that there is a directed edge from u to v.
EXAMPLE: b is parent of f and g.
When u is the parent of v, v is called a child of u.
EXAMPLE: f is child of b.
Vertices with the same parent are called siblings.
EXAMPLE: f and g are siblings.
The ancestors of a vertex are the vertices in the path from the
root to this vertex, excluding the vertex itself and including the
root. EXAMPLE: Ancestors of g: b and a.
The descendants of a vertex v are those vertices that have v
as an ancestor. EXAMPLE: Descendants of a: b,c,d,e,f,g.
A vertex of a rooted tree is called a leaf if it has no children.
EXAMPLE: f, g, e, d are leaves.
Vertices that have children are called internal vertices.
EXAMPLE: a,b,c.
A rooted tree is called an m-ary tree if every internal vertex has no more than m
children.
The tree is called a full m-ary tree if every internal vertex has exactly m children.
An m-ary tree with m = 2 is called a binary tree.
• Each node in a binary tree T is assigned
a level number, as follows.
• The root R of the tree T is assigned the
level number 0, and every other node is
assigned a level number which is 1 more
than the level number of its parent.
• The depth (or height) of a tree T is the
maximum number of nodes in the
longest branch of T .
TRAVERSING BINARY TREES
There are three standard ways of traversing a binary tree T with root R. These
three algorithms, called preorder, inorder, and postorder, are as follows:
Preorder: (1) Process the root R.
(2) Traverse the left subtree of R in preorder.
(3) Traverse the right subtree of R in preorder.
TRAVERSING BINARY TREES
Inorder: (1) Traverse the left subtree of R in inorder.
(2) Process the root R.
(3) Traverse the right subtree of R in inorder.
TRAVERSING BINARY TREES
Postorder: (1) Traverse the left subtree of R in postorder.
(2) Traverse the right subtree of R in postorder.
(3) Process the root R.
Linked Representation of Graphs
This table may also be presented in the compact form
G = [A:B,D; B:A,C,D; C:B; D:A,B; E:∅]
where a colon “:” separates a vertex from its list of neighbors, and a semicolon “;”
separates the different lists.
1
6 3 1 6 8 3 8 6
Example:
(a) List the vertices in the order they appear in memory.
(a) D, B, F, A, E, C
(b) Find the adjacency list adj(v) of each vertex v of G.
(b) G = [A:B,D; B:A,D; C:E; D:A,B,E; E:C,D, F; F:E]
LINKED REPRESENTATION OF DIRECTED GRAPHS
GRAPH
ADJACENCY LIST
EXAMPLE:
Let G be the graph presented by the following table:
G = [X : Y,Z,W; Y : X, Y,W; Z : Z,W; W : Z]
(a) Find the number of vertices and edges in G.
The compact table tells us that there are four vertices, X, Y, Z,W and 9 edges.
(b) Draw the graph of G.
(c) Are there any sources or sinks?
No vertex has zero outdegree, so there are no sinks. Also, no vertex has zero
indegree, that is, each vertex is a successor; hence there are no sources.
Draw Linked representation of the following graph.
Draw Linked representation of the following graph.
(a) Find the depth d of T .
(b) Traverse T using the preorder algorithm.
(c) Traverse T using the inorder algorithm.
(d) Traverse T using the postorder algorithm.
SOLUTION: (a) The depth d is the number of nodes in a longest branch of T ; hence d = 4.
(b) The preorder traversal of T is a recursive NLR algorithm, that is, it first processes a node N,
then its left subtree L, and finally its right subtree R.
The tree T is traversed as follows:
F −A−K−C−D−H−G−B−E
(c) The inorder traversal of T is a recursive LNR algorithm, that is, it first processes a left subtree
L, then its node N, and finally its right subtree R. Thus T is traversed as follows:
A−K−C−F −H−D−B−G−E
(d) The postorder traversal of T is a recursive LRN algorithm, that is, it first processes a left
subtree L, then its right subtree R, and finally its node N. Thus T is traversed as follows:
C−K−A−H−B−E−G−D−F
