Module 3
Trees – properties, pendant vertex, Distance and centres in a tree - Rooted and
binary trees, counting trees, spanning trees.
Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut
Vertices, Fundamental circuits. (8 hours) (RBT Levels: L1, L2 and L3)
TREE:
● A tree is a connected graph without any circuits.
●
Trees with one,
two, three, and four vertices are shown in Fig. 3-2.
PROPERTIES OF TREES
1. There is one and only one path between every pair of vertices in a tree, T.
Proof: Since T is a connected graph, there must exist at least one path between
every pair of vertices in T. Now suppose that between two vertices a and b of T
there are two distinct paths. The union of these two paths will contain a circuit
and T cannot be a tree.
2. If in a graph G there is one and only one path between every pair of
vertices, G is a tree.
Proof: Existence of a path between every pair of vertices assures that G is
connected. A circuit in a graph (with two or more vertices) implies that there is at
least one pair of vertices a, b such that there are two distinct paths between a
and b. Since G has one and only one path between every pair of vertices, G can
have no circuit. Therefore, G is a tree.
3. A tree with n vertices has n − 1 edges.
4. Any connected graph with n vertices and n − 1 edges is a tree.
5. A graph is a tree if and only if it is minimally connected.
A graph G with n vertices is called a tree if
1. G is connected and is circuitless, or
2. G is connected and has n − 1 edges, or
3. G is circuitless and has n − 1 edges, or
4. There is exactly one path between every pair of vertices in G, or
5. G is a minimally connected graph.
PENDANT VERTICES IN A TREE
THEOREM 3-7
In any tree (with two or more vertices), there are at least two pendant vertices.
● Pendant vertices are those with degree 1.
● A tree with n vertices have n-1 edges and hence the total degree would be
2(n-1).
Now this sum has to be distributed among n vertices and none of them can
have degree 0 as the graph is connected. So there should atleast 2 vertices of
degree 1 as otherwise the degree sum would exceed 2(n-1).
● Hence in any tree (with two or more vertices) there are atleast 2 pendant
vertices.
An Application: The following problem is used in teaching computer
programming. Given a sequence of integers, no two of which are the same, find
the largest monotonically increasing subsequence in it.
Suppose that the sequence given to us is 4, 1, 13, 7, 0, 2, 8, 11, 3; it can be
represented by a tree in which the vertices (except the start vertex) represent
individual numbers in the sequence, and the path from the start vertex to a
particular vertex v describes the monotonically increasing subsequence
terminating in v.
As shown in Fig. 3-6, this sequence contains four longest monotonically
increasing subsequences, that is (1, 7, 8, 11) , (4, 7, 8, 11),) (1, 2, 8, 11) and (0, 2,
8, 11).
Each is of length four. Such a tree used in representing data is referred to as a
data tree by computer programmers.
DISTANCE AND CENTERS IN A TREE
Distance in a graph
In a connected graph G, the distance d(vi, vj) between two of its vertices vi and vj
is the length of the shortest path (i.e., the number of edges in the shortest path)
between them.
In the above graph G, consider the vertices v1 and v2. Some of the paths
between v1 and v2 are (a, e), (a, c, f), (b, c, e), (b, f), (b, g, h), and (b, g, i, k). etc.
Here there are two shortest paths (a,e), (b,f), both having length 2. Hence
d(v1,v2)=2
In a tree since there is exactly one path between any 2 vertices, determination of
distances is much easier eg: In a tree t, d(a,b)=1, d(a,c)=2, d(c,b)=1
Distance in a graph as a Metric
A metric is a function of two variables defined on a set with the following
properties
1. Non negativity: f(x, y) ≥ 0, and f(x, y) = 0 if and only if x = y.
2. Symmetry: f(x, y) = f(y, x).
3. Triangle inequality: f(x, y) ≤ f(x, z) + f(z, y) for any z.
THEOREM 3-8
The distance between vertices of a connected graph is a metric.
As the distance between any 2 vertices is the length of the shortest path
between them, the first two conditions follow. Since d(vi,vj) is the length of the
shortest path between the vertices vi and vj, this path cannot be longer than any
other path between vi and vj which goes through a specific vertex vk. Hence
d(vi,vj)<=d(vi,vk)+d(vk,vj)
Eccentricity of the vertex
● Eccentricity (also referred to as associated number or separation) of a vertex
in a graph.
● The eccentricity E(v) of a vertex v in a graph G is the distance from v to the
vertex farthest from v in G; that is,
● A vertex with minimum eccentricity in graph G is called a center of G.
A graph in general can have many centres. In a circuit, every vertex is a center.
THEOREM 3-9
Every tree has either one or two centers.
Proof: The maximum distance, max d(v, vi), from a given vertex v to any other
vertex vi occurs only when vi is a pendant vertex. With this observation, let us
start with a tree T having more than two vertices. Tree T must have two or more
pendant vertices (Theorem 3-7). Delete all the pendant vertices from T. The
resulting graph T′ is still a tree. What about the eccentricities of the vertices in T′?
A little deliberation will reveal that removal of all pendant vertices from T
uniformly reduced the eccentricities of the remaining vertices (i.e., vertices in T′)
by one. Therefore, all vertices that T had as centers will still remain centers in T′.
From T′ we can again remove all pendant vertices and get another tree T″. We
continue this process (which is illustrated in Fig. 3-10) until there is left either a
vertex (which is the center of T) or an edge (whose end vertices are the two
centers of T). Thus the theorem.
MORE ON CENTERS:
● If a tree has two centers, then they must be adjacent.
● The eccentricity of a center (which is the distance from the center of the tree
to the farthest vertex) in a tree is defined as the radius of the tree.
● The diameter of a tree T, on the other hand, is defined as the length of the
longest path in [Link] other words it is the maximum eccentricity
● Radius in a tree is not necessarily half its diameter
