Trees and Spanning Trees

Trees and Spanning Trees are the most important concepts in Graph Theory. When we are researching the applications of Graph Theory, Trees and Spanning Trees are unavoidable. First, we know some basic definitions on Trees and then discuss about their applications in various fields.

What is a Tree?

A tree is a connected acyclic graph. In other words, a connected graph without any circuits is said to be a tree.

What is a Forest?

An union of trees is said to be a forest. In our example, the union of two or more trees is a forest.

Minimally Connected Graph

A connected graph is said to be minimally connected if the removal of one edge from it will disconnect the graph.

The graph given in the figure is a minimally connected graph. Because the removal of one edge from it will leave the graph disconnected.

Properties of Trees

1. Every tree is a minimally connected graph.
2. Every minimally connected graph is a tree.
3. Any connected graph with n vertices and n-1 edges is a tree.
4. In a tree, there exist only one path between every pair of vertices.

Distance between Vertices

The distance between two vertices in a connected graph is the length of the shortest path between them. In other words, the distance between two vertices is the number of edges in their shortest path.

In our graph, there exist 2 paths between vertices v1 and v3 namely, v1 – v3 and v1 – v4 – v2 – v5 – v3. Clearly, v1 – v3 is the shortest path between the two vertices. So, the distance between v1 and v3 is 1.

It is denoted by d(v1, v3) = 1.

Eccentricity of a Vertex

The eccentricity of a vertex ‘v’ is the distance from v to a farthest vertex. In other words, the maximum of all the distances from ‘v’ to all other vertices in that graph. Eccentricity is denoted by e(v) and

e(v) = max{d(v, u)| u is any other vertex of the graph}

In our graph G, consider vertex v1. Let us find the distance of v1 to all other vertices of G.

d(v1, v2) = 2, the shortest path is e5 – e4.
d(v1, v3) = 1, adjacent vertices.
d(v1, v4) = 1, adjacent vertices.
d(v1, v5) = 2, the shortest path is e1 – e2

So, e(v1) = max {2, 1, 1, 2} = 2. That is, the eccentricity of v1 is 2. Similarly, we could easily find the eccentricities of other vertices.

e(v2) = 2, e(v3) = 2, e(v4) = 2 & e(v5) = 2.

Radius of a Graph

The radius of a graph G is the minimum of the eccentricities of all the vertices of G. The radius of G is denoted by rad G.

rad G = min{ e(v)| v is a vertex of G}

For graph G we already know the eccentricities of all vertices. So we easily find the radius of G.

That is, rad G = min{e(v1), e(v2), e(v3), e(v4), e(v5)} = min{2, 2, 2, 2, 2} = 2. So the radius of G is 2.

Central Vertices of a Graph

A vertex in a graph is said to be a central vertex if its eccentricity is equal to the radius of the graph.

For our graph graph G, e(v1) = 2, e(v2) = 2, e(v3) = 2, e(v4) = 2 & e(v5) = 2 and rad G = 2. Since the eccentricity of all vertices in G equals the radius of G. So, for G all five vertices are central vertices. For a graph that itself is a circuit (no vertex outside of the circuit), all of its vertices are central vertices.

Center of a Graph

The set of all central vertices of a graph is said to be its center.

For the given graph, the set of all vertices {v1, v2, v3, v4, v5} is the center because all the vertices are central vertices. This is because the graph is, itself a circuit.

For this graph, e(v1) = 3, e(v2) = 2, e(v3) = 3, e(v4) = 2, e(v5) = 3, e(v6) = 3 & e(v7) = 3. So the radius of this graph is, rad G = min{3,2,3,2,3,3,3} = 2.

Therefore, the set of vertices whose eccentricity equals rad G is the center of G. That is, the set {v2, v4} is the center of this graph.

Finding Center of a Tree

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.