This post is also available in: हिन्दी (Hindi) العربية (Arabic)
What is a Network?
In computer terminology, a network consists of two or more computers that are linked in order to share resources (such as printers and CDs), exchange files, or allow electronic communications. The computers on a network may be linked through cables, telephone lines, radio waves, satellites, or infrared light beams. Not only computers, even other communication devices such as cell phones function because of their connectivity through a network. A network is simply a collection of connected objects. We refer to the objects as nodes or vertices and usually draw them as points. We refer to the connections between the nodes as edges and usually draw them as lines between points.
What is a Graph?
Network diagrams to show interconnections between a set of entities are also known as Graphs. Each entity is represented by a node (or vertex). The connection between the nodes is represented through links (or edges).
Graphs are data structures used to study pairwise relationships between objects and entities. It is a branch of Discrete Mathematics and has found multiple applications in Computer Science, Chemistry, Linguistics, Operations Research, Sociology, etc. Formally a graph G = (V, E) consists of a set of vertices V = {V1, V2, V3, …} and set of edges E = {E1, E2, E3, …}. The set of unordered pairs of distinct vertices whose elements are called edges of the graph G such that each edge is identified with an unordered pair (Vi, Vj) of vertices.
Terminology Associated with Graph
- The vertices u and v are called the end vertices of the edge (u, v).
- If two edges have the same end vertices they are called parallel edges.
- An edge of the form (u, v) is a loop.
- A graph is simple if it has no parallel edges and loops.
- A graph is said to be empty if it has no edges.
- A graph is a null graph if it has no vertices.
- A graph with only 1 vertex is a trivial graph.
- Edges are adjacent if they have a common vertex.
- Vertices are adjacent if they have a common edge.
- The degree of the vertex v, written as d(v), is the number of edges with v as an end vertex. By convention, we count a loop twice and parallel edges contribute separately.
Applications of Graph
- Computer Science: In computer science, the graph is used to represent networks of communication, data organization, computational devices, etc.
- Physics and Chemistry: Graph theory is also used to study molecules in chemistry and physics.
- Social Science: Graph theory is also widely used in sociology.
- Mathematics: In this, graphs are useful in geometry and certain parts of topology such as knot theory.
- Biology: Graph theory is useful in biology and conservation efforts.
Graph Types Explained To Kids – Types of Graphs
Graphs are of different types and mainly can be classified as:
Null Graph
A null graph is a graph in which there are no edges between its vertices. A null graph is also called an empty graph.
In the above graph, there are four vertices but not a single edge. It’s an example of a null graph.
Trivial Graph
A trivial graph is a graph that has only one vertex.
In the above graph, there is only one vertex denoted by 1.
Simple Graph
A simple graph is an undirected graph with no parallel edges and no loops. In a simple graph that has n vertices, the degree of every vertex is at most (n – 1). In the above example, the first graph is not a simple graph because it has two edges between A and B and it also has a loop. The second graph is a simple graph because it does not contain any loop and parallel edges.
Undirected Graph
An undirected graph is a graph whose edges are not directed.
Directed Graph
A directed graph is a graph in which the edges are directed by arrows. Directed graphs are also known as digraphs.
In the above graph, each edge is directed by an arrow. A directed edge has an arrow from A to B, meaning A is related to B, but B is not related to A. (In terms of network, there is a path from A to B, but there is no path from B to A.
Complete Graph
A graph in which every pair of vertices is joined by exactly one edge is called a complete graph. It contains all possible edges. In the above example, since each vertex in the graph is connected with all the remaining vertices through exactly one edge therefore, both graphs are complete graphs.
Connected Graph
A connected graph is a graph in which we can visit any vertex from any other vertex. In a connected graph, at least one edge or path exists between every pair of vertices.
Disconnected Graph
A disconnected graph is a graph in which any path does not exist between every pair of vertices.
In the above graph there is no path between 3 and 0, 3 and 1, 3 and 2 and also between 4 and 0, 4 and 1 and 4 and 2.
Regular Graph
A regular graph is a graph in which the degree of all the vertices is the same. If the degree of all the vertices is k, then it is called a k-regular graph.
In the above graph, the degree of each vertex is 3. Hence, it’s a 3-regular graph.
Cyclic Graph
A graph with n vertices (where n >= 3) and n edges forming a cycle of n with all its edges is known as a cycle graph. And a graph containing at least one cycle in it is called a cyclic graph.
In the above graph, vertices B, C, E and D form a cycle, therefore, it’s a cyclic graph.
Acyclic Graph
A graph that does not have even one cycle is called an acyclic graph.
Bipartite Graph
A bipartite graph is a graph in which the vertex set can be partitioned into two sets that edges only go between sets, not within them. A graph G(V, E) is called a bipartite graph if its vertex set V(G) can be decomposed into two non-empty disjoint subsets V1(G) and V2(G) in such a way that each edge has its one last joint in V1(G) and the other last point in V2(G).
Star Graph
A star graph is a graph that exactly looks like a star where (n – 1) vertices are connected to a single central vertex. A star graph with n vertices is denoted by Sn.
All the above graphs are star graphs, as one vertex is connected to all the remaining vertices.
Weighted Graph
A weighted graph is a graph whose edges have been labeled with some weights or numbers. The length of a path in a weighted graph is the sum of the weights of all the edges in the path.
The above graph is a weighted graph as each edge has been labeled with a value called weight. A graph showing the cities with distances is another example of a weighted graph.
Planar Graph
A planar graph is a graph that we can draw in a plane in such a way that no two edges of it cross each other except at a vertex to which they are incident.
All the above graphs are planar graphs as none of the edges in all the graphs are crossing each other.
Non-Planar Graph
A graph that cannot be drawn without at least one pair of its crossing edges is known as a non-planar graph. In other words, a graph that is not a planar graph is called a non-planar graph.
