Do you think IIT Guwahati certified course can help you in your career?
Introduction
Graphs are a non-linear Data Structure that is widely used in the field of computer science to solve many real-world problems. When we have many entities connected to each other somehow, our priority is to model this structure as a graph and then proceed towards a solution. Graphs are also used in social networks like Facebook and LinkedIn.
If graphs are so useful, then why not explore the subject graph theory a bit more.
In this article, we are going to study the basic properties of graphs. The properties of graphs are used to characterise them based on their structures.
Let’s see the mathematical definition of a graph before discussing about the properties of graphs -
A graph is a set of vertices and edges G = {V, E}.
Example -
G = {V,E} where,
V = {a,b,c,d}
E = {ab,bc,cd,da}
Following are the important properties of graph:
Distance between two vertices
The distance between two vertices U and V is defined as the number of edges present in the shortest path between U and V.
Notation - d(U,V)
We consider the shortest path between two vertices since there may exist many paths from one vertex to another.
Why not see some examples to understand -
Consider this graph:
There are many paths between vertices d and f. Some of them are as follows:
da → ae → ef (length = 2)
dc → cg → gf (length = 2)
df (length = 1)
da → ab → bc → cg → gf (length = 4)
dc → cb → ba → ae → ef (length=4)
Out of these, the shortest path is d → f.
So, the distance between d and f is 1.
Eccentricity of a vertex
Eccentricity of a vertex is defined as the maximum distance between a vertex to all the other vertices.
Notation - e(V) [eccentricity of vertex V]
In the above graph, consider the vertex ‘a’.
Distances of all the vertices from vertex a are as follows -
d(a,b)
1
d(a,c)
2
d(a,d)
1
d(a,e)
1
d(a,f)
2
d(a,g)
3
Since the maximum distance among all is 3, which is the distance between g and a, hence, the eccentricity of a is 3.
Similarly, the eccentricities of all the other vertices are as follows:
Vertex
Eccentricity
b
3
c
3
d
2
e
3
f
3
g
3
Radius of connected Graph
Radius of a connected graph is equal to the minimum eccentricity among all the vertices.
Notation - r(G)
For the above graph, we see that the vertex d has eccentricity=2, which is the minimum among all the eccentricities of other vertices. Hence, the radius of the graph = 2.
Diameter of a Graph
The diameter of a graph is equal to the maximum eccentricity among all the vertices.
Notation - d(G)
For the graph above, the maximum value of eccentricity is 3. So, the diameter of the graph = 3.
Central point
The vertex whose eccentricity is equal to the radius of the connected graph is called the central point of the graph.
If r(G) = e(V), then vertex V is called the central point of the graph.
Follow up question -
Can you tell whether a graph can have more than one central point from the above definition?
If you figured it out, then well done!! Let’s see the answer -
So, yes, there can be more than one central point in a graph because there can be two or more vertices having the same minimum eccentricity.
Centre
The set of all the central points of a graph is called the centre of the graph.
Example - For the graph, we considered above, since only one vertex(vertex d) has the minimum eccentricity(here 2), so the set {‘d’} is the centre of the graph.
Circumference
The circumference of a graph is said to be equal to the total number of edges in the longest cycle present in the graph.
In the above graph, the longest cycle is abcgfea, and the total number of edges is 6. So, the circumference of the graph is 6.
Girth
Girth is equal to the number of edges in the shortest cycle present in the graph.
Notation - g(G)
For the above graph, the shortest cycle has 4 edges. The shortest cycles are - abcd, eadf and fdcg. So, the girth of the graph is 4.
What is a graph? A graph is a non-linear data structure consisting of nodes and edges.
What do you mean by the order of a graph? The order of a graph is equal to the number of vertices present in the graph.
What is the size of a graph? The size of a graph is equal to the number of edges present in the graph.
What is the degree of a vertex? The degree of a vertex is equal to the number of edges incident on the vertex.
What do you mean by a connected graph? The graph is said to be connected if there exists a path between every pair of vertices.
What is a loop in a graph? The edge which connects a vertex to itself is called a loop.
Key Takeaways
In this article, we discussed a topic of graph theory, i.e. basic properties of graphs. Basically, we got to know important terminologies in graphs and how they are calculated. We also saw examples to clearly understand the properties of graphs. Properties of graphs play a key role to characterise graphs and use them for different use cases. Check out this problem - No of Spanning Trees in a Graph
If you would like to learn about graphs completely, then consider reading Graphs.
84+ registered