# Graphs introduction

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

### Directed 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

### undirected 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

### Adjacency matrices

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.

### Adjacency Lists

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