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.
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.
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.
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 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.
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.
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.