Module VI
Trees, Fundamental circuits, cut sets
Trees – properties of trees – distance and centres in tree – Spanning trees
– Spanning tree algorithms- Tree traversals- Fundamental circuits and
cut-sets
Recall!
• A path that begins and ends at the same node is called a cycle.
Example:
• Two vertices are connected if there is a path between them.
• A graph is connected if every pair of its vertices is connected.
• A graph is acyclic if it doesn’t have any cycle.
Tree
• A graph is called a tree if it is connected and acyclic.
Not Tree and not Forest Tree and Not forest
Not Tree and forest
Some Properties of Trees
Distance
In a connected graph 𝐺, the distance 𝑑(𝑣𝑖 , 𝑣𝑗 ) between two of its vertices
𝑣𝑖 and 𝑣𝑗 is the length of the shortest path.
Metric property
1. Nonnegativity 𝑑 𝑥, 𝑦 ≥ 0 and 𝑑 𝑥, 𝑦 = 0 if and only if 𝑥 = 𝑦
2. 𝑆𝑦𝑚𝑚𝑒try: 𝑑 𝑥, 𝑦 = 𝑑 𝑦, 𝑥
3. Triangle inequality: 𝑑 𝑥, 𝑧 = 𝑑 𝑥, 𝑦 + 𝑑 𝑦, 𝑧 for any 𝑧
Example
Eccentricity
Definition: Let 𝑣 be a point in a connected graph 𝐺. The
eccentricity 𝑒 (𝑣) is defined by
𝑒 (𝑣) = 𝑚𝑎𝑥 { 𝑑(𝑢, 𝑣) / 𝑢 ∊ 𝑉(𝐺)}
The radius 𝑟(𝐺) is defined by 𝑟(𝐺 ) = 𝑚𝑖𝑛{ 𝑒 (𝑣) / 𝑣 ∊ 𝑉(𝐺)}.
Center of a Tree.
A vertex with minimum eccentricity value is called as center of a
Tree.
𝑣 is called a central point if 𝑒 (𝑣) = 𝑟(𝐺 ) and the set of all central points
is called the centre of 𝐺
Two centers
Example:
Find the eccentricity, radius and centre for the given graph.
Example:
Find the eccentricity, radius and centre for the given graph.
The eccentricity are:
𝑒 𝑣1 = 4 ; 𝑒 𝑣4 = 3, 𝑒 𝑣2 = 3 ; 𝑒 (𝑣5 ) = 3, 𝑒 (𝑣3 ) = 2 ; 𝑒 (𝑣6 ) = 4
The radius 𝑟 𝐺 = 𝑚𝑖𝑛 𝑒 𝑣 /𝑣 ∊ 𝑉 𝐺 = 2.
Centre of G if 𝑒 𝑣 = 𝑟 𝐺 = 2
Example 1
𝐸 𝑑 = 2, 𝐸 𝑏 = 1, 𝐸 𝑎 = 2, & 𝐸 𝑐 = 2
Eccentricity of graph is 2
SPANNING TREES
Definition
If the subgraph 𝑇 of a connected graph 𝐺 is a tree containing all the vertices of
𝐺, then 𝑇 is called a spanning tree of 𝐺.
SPANNING TREES
Definition
If the subgraph 𝑇 of a connected graph 𝐺 is a tree containing all the vertices of
𝐺, then 𝑇 is called a spanning tree of 𝐺.
Spanning Trees
Example: Draw all the spanning trees of the graph G as given below:
Example: Draw all the spanning trees of the graph
G as given below
Spanning trees are:
MINIMUM SPANNING TREE
If 𝐺 is a connected weighted graph, the spanning tree of 𝐺 with the smallest total
weight (viz., the sum of the weights of its edges) is called the minimum spanning
tree of 𝐺.
Two popular algorithms for constructing minimum spanning trees are given as
follows.
❖ Prim's Algorithm
❖ Kruskal's Algorithm
❖ Kruskal's Algorithm
Example. Find the minimum spanning tree for the weighted graph shown
in Fig., by using Kruskal’s algorithm.
Example. Use Kruskal’s algorithm to find a minimum spanning tree for the weighted
graph shown in Fig.
❖Prim's Algorithm
1. Use Prim's algorithm to find a minimum spanning tree for the weighted graph as follows
1. Use Prim's algorithm to find a minimum spanning tree for the weighted graph as follows
The minimum spanning tree with weight is 6
2. Use Prim's algorithm to find a minimum spanning tree for the weighted graph as follows
Solution hint: The total weight of the minimum spanning tree = 24.
2. Use Prim's algorithm to find a minimum spanning tree for the weighted graph as follows
The total weight of the
minimum spanning tree = 5 +
1 + 3 + 6 + 2 + 7 = 24.
Fundamental Circuit
Let 𝐺 be connected graph and T be it’s spanning tree.
A circuit formed by adding a chord to spanning tree T is called as fundamental
circuit.
Branch or Branch set {𝑎, 𝑐, 𝑑, 𝑔}
Chord set {𝑏, 𝑒, 𝑓, ℎ}
G Spanning tree T
Fundamental Circuits are
(c)
(a)
(b)
(d)
Fundamental Cut-sets
Let 𝐺 be connected graph and T be it’s spanning tree.
A edge cut of the graph G containing exactly one branch of the spanning tree T,
is called a fundamental cutset.
Branch or Branch set {𝑎, 𝑐, 𝑑, 𝑔}
Chord set {𝑏, 𝑒, 𝑓, ℎ}
G Spanning tree T
A Rooted Tree
► 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.
► Different choice of root produce different rooted tree
Properties of Rooted Trees
Properties of Rooted Trees
TREE TRAVERSAL
One of the most common operations performed on tree graphs is that of
traversal. A traversal a tree is a process to traverse (walk along) a tree in a
systematic manner so that each vertex is visited and processed exactly once.
There are three methods of traversal of a binary tree, namely, preorder,
inorder and post order traversals.
BINARY TREE: A special class of rooted trees, called binary trees,
is of importance in applications of computer science.
Definition: If every internal vertex of a rooted tree has exactly/at most 2 children,
the tree is called a full binary tree/a binary tree.
In other words, a full binary tree is a tree in which there is exactly one vertex
(root) of degree 2 and each of the remaining vertices is of degree 1 or 3.
Binary Tree Full binary Tree
This is NOT A Binary Tree
A
B C
D E F G
This is a graph H
because A, B, E, H, F and C
form a circuit
This is NOT A Binary Tree
A
B C
D E F G H
This is a general tree because C has three child nodes
Preoder, Inorder, Postorder
Let 𝑇1 , 𝑇2 , … , 𝑇𝑛 be the subtrees of the given binary tree at the
root R from left to right.
Preorder Traversal:
1. Visit the root R
2. Process 𝑇1 in preorder
3. Process 𝑇2 , 𝑇3 , … in preorder Inorder Traversal:
1. Process left subtree 𝑇1 in in-order.
2. Visit the root R.
3. Process right subtrees 𝑇2 , 𝑇3 , …
Postorder Traversal: from left to right in inorder.
1. Process 𝑇1 , 𝑇2 , … in pre-order
from left to right.
2. Visit the root R.
41
Example 1 A Preorder ABC
Inorder BAC
Postorder BCA
Preorder Traversal:
1. Visit the root C
B
2. Traverse left subtree
3. Traverse right subtree
Example 2
Inorder Traversal: A
1. Traverse left subtree Preorder A BDE CF
2. Visit the root Inorder DBE A CF
3. Traverse right subtree C Postorder DEB FC A
B
Postorder Traversal:
1. Traverse left subtree F
2. Traverse right subtree
3. Visit the root
D E
Tree Traversals: An Example
A
B C
D E F
G
Tree Traversals: An Example
A
B C
D E F
Preorder: ABDECFG
In Order: DBEAFGC G
Postorder: DEBGFCA
Tree Traversals: Another Example
A
B C
D E
G
H I
Tree Traversals: Another Example
A
B C
D E
G
F
Preorder: ABDFHIECG
Postorder: HIFDEBGCA
H I In Order: DHFIBEACG
Example: List the order in which the vertices of the tree given in Fig. are
processed using preorder, inorder and postorder traversal.
1. Construct the binary tree whose inorder, preorder traversals are
respectively 𝑬𝑨𝑪𝑰𝑭𝑯𝑫𝑩𝑮 and 𝑭𝑨𝑬𝑰𝑪𝑫𝑯𝑮𝑩
2. Construct the binary tree whose inorder and postorder traversals are
respectively HDIBJEKAFCG and HIDJKEBFGCA.
In binary tree representation of expressions, the terminal vertices (leaves) are labeled with numbers or variables,
while the internal vertices are labeled with the operation such as addition (+), subtraction (−), multiplication (∗),
division (/) and exponentiation (↑).
The operation at each internal vertex operates on its left and right subtrees from left to right.
*
Infix Notation
The standard way of representing an expression in which the operator is
placed between its operands is
called the infix form of the expression.
Prefix Notation
The prefix from of an algebraic expression represented by a binary tree corresponds
to the pre-order traversal of the tree.
Postfix Notation
The postfix from of an algebraic expression represented by binary tree corresponds to the postorder
traversal of the tree.
(1)
(1)
(2)
(3)
(4)
Prefix form
Postfix from
Find the value of
Prefix: Operands from right to left Postfix: Operands from left to right
