Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Graphs: Basic Terminologies
2.1.
Point
2.2.
Line
2.3.
Vertex
2.4.
Edge
2.5.
Graph
3.
Graph Measurements
3.1.
Length
3.2.
The Distance between two Vertices
3.3.
Diameter of Graph
3.4.
Radius of Graph
3.5.
Centre of Graph
3.6.
Eccentricity of Graph
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Graph Measurements

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Graphs have a variety of attributes that are used to classify them based on their structures. We define these characteristics of graphs using some basic terminologies. In this post, we will learn different graph measurement methods. Before we learn these methods, we will learn some basic concepts on graphs. 

Graphs: Basic Terminologies

A graph consists of a set of points called 'Vertices,' and a line connecting these points called 'Edge.' In mathematical terms, we define a graph ‘G’ as G = (N, E).

Where N = set of nodes or vertices.
E = Set of edges.

Point

A point is a specific location in one-dimensional, two-dimensional, or three-dimensional space. We use an alphabet to name a point for easier understanding. A dot represents it.

Example:

The dot, in this case, is a point called 'A.'

Line

A line is a path that connects two points. A solid line depicts it.

Example:

The points are 'A' and 'B' in this case. A line is a connection between these two points.

Vertex

vertex is a point where two or more lines intersect. It is also known as a node. An alphabet represents a vertex, just like points.

Here, a dot represents the vertex called ‘A.’

Edge

A line connecting two vertices is an edge in mathematics. A single vertex can produce a large number of edges. It cannot be produced without the involvement of a vertex. It must have a starting vertex and an ending vertex.

Example:

Here two points named ‘A’ and ‘B’ are connected by an edge.

Graph

We define a graph ‘G’ as G = (V, E), where V denotes the set of all vertices and E denotes the set of all edges in the graph.

Example:

The graph's edges are AB, BC, CD, and AD. Similarly, the graph's vertices are A, B, C, and D.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

  1. 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.
     
  2. 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.
     
  3. 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.
     
  4. 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!

Live masterclass