Everything About Graph – Graph, Types of Graph, Representation of Graph
What is Graph?
In computer science, a graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from the field of graph theory within mathematics.
A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Elements of Graph
- Vertices: Also known as node. The point where edges connect.
- Edge: The line which connects Nodes.
- Weight: Length of edge.
- Direction: Tells about an edge where it is from and where to.
Types of Graph
Types of Graphs Respective to Direction of Edge
- Directed Graph
- Undirected Graph
What is Directed Graph?
A directed graph is a graph where each edge is directed. In a directed graph every edge has a starting a ending. Every edge is known as from a source and to a destination. For example in the below directed graph there is edge form 1 to 4.
What is Undirected Graph?
An undirected graph is that where the edges are not directed specifically. If there is an edge in an undirected graph from A to B then that can be said also there is a edge from B to A.
Types of Graph Respective to Weight of Edge
- Weighted Graph
- Unweighted Graph
What is Weighted Graph?
A graph is said to be weighted if each edge of the graph has a value which represents the distance from the starting node to ending node. We can find shortest path as well as a strongly connected graph in weighted graph.
What is Unweighted Graph?
A graph is said to be unweighted if edges are not specified with a weight. These type of graph tells us only that is a node connected to other or not. We can find strongly connected graph from an unweighted graph but not a shortest path.
Other Types of Graph
What is Bipartite Graph?
A graph G is said to be bipartite if its vertices V can be partitioned into two subsets M and N such that each edge of G connects a vertex of M to a vertex of N.
What is Multigraph?
In graph theory, a multigraph is a graph which is permitted to have multiple edges (also called parallel edges), that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge.
What is Complete Graph?
In graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.
A graph is said to be complete if each node have exactly one edge to each of the other nodes. The complete graph with 3 edges is known as K3, with 4 edges is known as K4 and so on.
What is Planner Graph?
A graph or multigraph which can be drawn in the plane so that its edges do not cross is said to be planar graph. K2, K3, K4 are common example of planner graph.
There are two question about K4 graph.
Is K4 a Planner Graph?
Why K4 is a Planner Graph?
The answer is simple. In normal sense it may be assumed that two edge crosses one other. But it is wrong. They are completely in different way. That is seems for your drawing. We can put an edge which is crossing another by a bypass way. See the three graphs below.
What is Homeomorphic Graph?
Two graphs G and G* are said to homeomorphic if they can be obtained from the same graph or isomorphic graphs by dividing an edge of G with additional vertices. For Example H and H’.
What is Isomorphic Graph?
Graphs G(V,E) and G*(V*,E*) are said to be isomorphic if there exists a one-to-one correspondence f : V → V* such that {u, v} is an edge of G if and only if {f (u), f (v)} is an edge of G*. For Example, G and G’.
Special Terms in Graph
Distance of Two Node
The distance between vertices u and v in G, written d(u, v), is the length of the shortest path between u and v. For example in the graph below d(A,D)=2.
Diameter of Two Node
The diameter of G, written diam(G), is the maximum distance between any two points in G. For example in the graph below diam(A,D)=3.
Adjacent Nodes
If e = (u, v) where u and v are endpoints of an edge e then u and v are called Adjacent Nodes. In the below graph A and B are adjacent nodes.
Cycle
A cycle is a closed simple path with length 3 or more. In the below graph A>B>C or C>B>A is a cycle.
Degree of Node
The degree of a node is the number of connections that it has to other nodes in the network. In a social network if you have 100 friends then the node that represents you has a degree of 100. In the below example the degree of node 1, 2, 3 and 4 is 2, 0, 2, 1 respectively.
Isolated Node
A node u is said to be isolated if there is no edge from u to anywhere. These nodes can be considered as the end of the graph. In the below graph node 2 is an isolated node. There is no edge from node 2.
Path
A path from a node u to a node v is the set of all edges need to fetch to travel from u to v. A path P of length n from a node u to a node v is defined as a sequence of n+1 nodes. In the below node a path from 4 to 2 is 4>3>2.
Representation of Graph
- Linked Representation
- Matrix Representation
Linked Representation
In which representation a graph is represented by a list of it’s nodes and the neighbor nodes to which there is an edge from current node is known as linked representation.
In the table bellow shows each node in a graph G followed by its adjacency list, which is its adjacency nodes.
| Node | Adjacency |
| A | E, G |
| B | C |
| C | F |
| D | C |
| E | H |
| F | A, B |
| G | B, C, E |
| H | D |
Drawing a Graph from Linked Representation
For the above representation the graph will be:
Matrix Representation
In which representation a graph is represented by a matrix where an element of row m and column n represent the edge from node m to node n. If the value is 0 that means there is no edge. If it’s non-zero then there is a edge. For adjacency matrix these values are 1 in path matrix these values are the length of the path.
Drawing a Graph from Matrix Representation
For the above representation the graph will be:
