Home Data Structures Distance, Diameter, Eccentricity, Radius and Center of a Graph

Distance, Diameter, Eccentricity, Radius and Center of a Graph

A graph is defined as a set of Vertices and lines joining these vertices known as Edges.  Today we will learn about various properties of a graph such as –  Distance, Diameter, Eccentricity, Radius, Center and Grith of a graph.

1. Distance between Two Vertices

The distance between two vertices of a graph is defined as the number of edges in the shortest path from them. There can be more than one shortest path possible between two vertices. It is generally denoted as d(u, v), where u and v are two vertices.

Distance Diameter Eccentricity Radius Center Grith of a Graph
Distance between Two Vertices

The distance between the vertex a and d is 2.
a->c->d

2. Eccentricity of a Vertex

The eccentricity in a connected graph is the maximum distance between a vertex v and any other vertex u of a graph. It is denoted as e(v). In the case of a disconnected graph, the eccentricity of each vertex is infinity.

Distance Diameter Eccentricity Radius Center Grith of a Graph
Eccentricity of a Vertex

Eccentricity for various vertices are - 
e(a) = 2 (a->c->b)
e(b) = 3 (b->c->a->f)
e(c) = 2 (c->a->f)
e(d) = 3 (d->e->a->f)
e(e) = 2 (e->a->f),(e->c->b) 
e(f) = 3 (f->a->c->b)

Maximum eccentricity for above graph is 3. 
Minimum eccentricity for above graph is 2.

3. Radius of a Graph

The radius of a graph is defined as the minimum eccentricity of any graph vertex. Among all the eccentricities possible in a graph G, the radius of the connected graph is the minimum of all those eccentricities. It is represented as r(G).

Since the eccentricity of every vertex in a disconnected graph is infinity, hence the radius of a disconnected graph will be infinity.

Distance Diameter Eccentricity Radius Center Grith of a Graph
Radius of a Graph G

Raidus of above graph is 2, because the minimun eccentricity
for above graph is 2.

4. Diameter of a Graph

The maximum eccentricity of any vertex in a graph G is known as the Diameter of a graph. It can also be defined as the maximum of all possible distances between any two pairs of vertices. It is denoted as the d(G).

The diameter of a disconnected graph is infinity.

Diameter of a Graph G
Diameter of a Graph G

Diameter of the above graph is 3, because maximum eccentricity
for above garaph is 3.

5. Center of a Graph

The Center of a graph( Jordan Center) is a set of all vertices with minimum eccentricity. Equivalently it is the set of vertices with eccentricity equal to the graph radius. The vertices lying at the center of a graph minimizes the distance from all other vetices in a graph.

The center can be found using the Floyd–Warshall algorithm.

Center of a Graph G
Center of a Graph G

Vertex a, c, e are the center of above graph,
because vertex a,c,e has the minimum eccentricity.

6. Grith of a Graph

The length of the shortest cycle of a graph is known as the Grith of a Graph. For an acyclic graph, the girth is infinity.

The odd girth and even girth of a graph are the lengths of the shortest odd cycle and shortest even cycle respectively.

Grith of a Graph G
Grith of a Graph G

The grith of above graph G is 3. 

The graph contains 2 cycle of same length.
Length of cycle a->c->e->a = 3
Length of cycle e->c->d->e = 3

This is how we define Distance, Diameter, Eccentricity, Radius, Center, and Grith of a graph.

Thank you for reading. If you like our content consider subscribing to our mailing list for such awesome content and if you find anything wrong, please comment.

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promise, we won't spam
Even we hate spam as much as you hate them

LEAVE A REPLY

Please enter your comment!
Please enter your name here