Last Updated on
A graph(G) consists of two sets Vertices and Edges ‘V’ is finite, nonempty set of vertices which are called edges. V(G) and E(G) represent a set of vertices and edges of the graph ‘G’.We can also denote a Graph as G=(V, E) or G(V, E)
Types of graphs
- Directed graph
- Undirected graph
In a directed graph each edge is represented by <u,v> where u is tail and ‘V’ is head of the edge.therefore <u,v> and <v,u> are different edges in a directional graph
In undirected graph no specific direction is given in this <u,v> and <v,u> are same edges
Applications of graphs
graph-theory mostly used in mathematics that deals with problems and applications such as
- shortest path problem
- scheduling algorithms
- network analysis and topology
- to resolve the connection problems
- to use in nodes and puzzles
Degree of a node/Vertex: no of edges coming into the vertex and going out from the vertex is said to be a degree of a node.
- a number of edges coming into the vertex and going out from the vertex is said to be a degree of a node.
- a number of edges of outgoing edges are said to be out degree of the vertex.
Representation of graphs
- Adjacency Matrices
- Adjacency lists
- Adjacency Multi lists
If a graph G=(V, E) has n vertices then the adjacency matrix shall contain ‘n’ rows and ‘n’ columns
If there exists an edge between the vertices Vi and Vj then the matrix shall represent by 1 in the ith row and jth column. Rest of the positions is marked by ‘0’
The adjacency matrix for the undirected graph is symmetric because if there is an edge from a to b then we also have an edge from b to a
The adjacency matrix for the directed graph is not symmetric.
In this representation of the graph, the n-rows of adjacency matrix are replaced by n-linked lists nodes for each vertex of the graph .the node of the linked lists
If the graph has ‘n’ vertices and ‘E’ number of edges then we need ‘n’ head nodes and 2E list nodes
Adjacency multi lists
In order to reduce the duplicate entries of the edges between two vertices Vi and Vj we have adjacency multi-list representation
For each edge, there is exactly one node but this node is an adjacency list of both the vertices represent in the head node.
This representation has two parts:-
- Head node containing all the vertices information
- set of linked for list edges information