Graph Measurements
Now that we have learned the basics of graphs, we will learn different methods available for graph measurement. So, here we will discuss one by one.
Length
The graph’s length is the number of edges in a graph.
Example:
The length of the above graph is 6.
The edges are AB, BC, CF, FE, ED, DB.
The Distance between two Vertices
The number of edges in the shortest or minimal path is the distance between two vertices in a graph. It specifies the shortest possible distance between two edges. Between two vertices, there may be more than one shortest path.
Here the shortest distance between 0 to 5 is 2. The shortest path is 0→3→5.
Point to be noted that there are other paths available between 0 to 5. Those paths are 0→1→2→4→5 and 0→2→4→5, with corresponding distances 4 and 3.
Diameter of Graph
The largest distance between two vertices is the graph's diameter. It can also be considered the maximum distance between all the vertex pairs. The best way to solve it is to locate all of the paths and then find their maximum.
The diameter of the above graph is 3, and the path followed to find this distance is AC→CH→HI. The maximum distance between any pair of vertices in the above graph does not exceed 3.
Radius of Graph
The radius of Graph G is the minimum of all the maximum distances between a vertex and all other vertices. As a result, an unconnected graph has an infinite radius. A graph's radius exists only if it has a diameter. We represent it as r(G).
The radius of the above graph is 2. And all the minimum radii are AC→CH, AC→CG, AB→BF, AB→BE, AB→BD.
Centre of Graph
It consists of all the vertices with the minimum eccentricity. The eccentricity is equal to the radius in this case. We can understand the centre as the hospital at the centre of town that will reduce the distance to travel from each corner of the town.
The red-coloured points in the graph represent the centres of the graph. The three vertices A have distance(A, B)<=3 from all vertices B.
Eccentricity of Graph
The maximum distance between a vertex to all other vertices is considered as the eccentricity of the vertex. We represent it as e(V).
In the above graph, let’s calculate the eccentricity of vertex A. So, d(A,A) = 0, d(A,B) = 1, d(A,C) = 2, d(A,D) = 1. So, eccentricity is 2, as it is the maximum value.
FAQs
-
What are some of the real-life applications of graph theory?
Graphs are used in a variety of ways in everyday life. We use graphs in circuit analysis, network analysis, planning tools. Apart from these, graphs aid in identifying people living in poverty, medical graphs aid in identifying patients, and weather graphs aid in the daily monitoring of temperature changes.
-
What is the maximum number of edges that a simple graph can have?
A simple graph is one in which no two vertices have more than one edge connecting them, and no edge begins and finishes at the same vertex. In other words, a simple graph is one without loops or numerous edges.
-
In graph theory, what is a cycle?
A cycle is a path that starts at one vertex and ends at the same vertex in graph theory.
-
What are the different measurement methods in graph theory?
The various measurement techniques involved in graph theory are:
→Distance between a pair of vertices
→The eccentricity of a vertex
→The radius of a connected graph
→Diameter of a graph
→Centre of a graph
Key Takeaways
This post has discussed basic graph theory concepts and basic terminologies involved in learning graph theory. Then we discussed different graph measurement methods such as:
→Length
→The distance between two Vertices
→Diameter of graph
→Radius of graph
→Centre of graph
→Eccentricity of graph
Graphs have a variety of attributes that are used to characterise them based on their structures. We describe these features or characteristics in terms that are peculiar to graph theory.
We hope this blog post has helped you learn graph theory basics and different graph measurement techniques to analyse the graphs. If you would like to learn more, check out our articles on “planar and non-planar graphs” and “regular and bipartite graphs.” Do upvote our blog to help other ninjas grow.
Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more.!
Happy Reading!
85+ registered