A graph G = (V, E) consists of a set of vertices, V, and a set of edges, E. Vertices are referred to as nodes. The arcs between the nodes are referred to as edges. Each edge is a pair (v,w), where v,w â‚¬ V. Edges are sometimes referred to as arcs.

__REPRESENTATION
OF GRAPHS:__

**Graph**

A *graph G =* (*V, E*) consists of a set of *vertices*,
*V,* and a set of *edges*, *E*. Vertices are
referred to as nodes. The arcs between the nodes are referred to as edges. Each
edge is a pair (*v,w*), where *v,w â‚¬ V*. Edges are sometimes referred to
as *arcs*.

In the
above graph V_{1}, V_{2}, V_{3}, V_{4} are the
vertices and (V_{1}, V_{2}), (V_{2}, V_{3}), (V_{3},
V_{4}), (V_{4}, V_{1}), (V_{1}, V_{3}),
(V_{2}, V_{4}) are the edges.

**Directed Graph (or) Digraph**

Directed
graph is a graph, which consists of directed edges, where each edge in E is
unidirectional. In *directed* graph,
the edges are directed or one way. it is also called as *digraphs*. If (v,w) is a directed edge, then (v,w) â‰ (w,v).

**Undirected Graph**

An
undirected graph is a graph, which consists of undirected edges. In undirected
graph, the edges are undirected or two way. If (v,w) is a undirected edge, then
(v,w) = (w,v).

**Weighted Graph**

A graph
is said to be weighted graph if every edge in the graph is assigned a weight or
value. It can be directed or undirected.

**Subgraph**

A
subgraph of a graph G = (V,E) is a graph G` = (V`, Eâ€Ÿ) such that V` V and Eâ€Ÿ E.

**Symmetric digraph**

A
symmetric digraph is a directed graph such that for every edge vw there is also
a

reverse
edge wv.

**Symmetric undirected graph**

Every undirected graph is a symmetric digraph where each undirected edge is considered as a pair of directed edges in opposite direction.

**Complete Graph**

A *complete graph* is a graph in which there
is an edge between every pair of vertices.

A
complete graph with n vertices will have n(n-1)/2.

A
complete graph is a strongly connected graph.

**Strongly connected Graph**

If there
is a path from every vertex to every other vertex in a directed graph then it
is said to be strongly connected graph. Otherwise, it is said to be weakly
connected graph.

**Path**

A *path* in a graph is defined as a sequence
of verices *w*_{1}, *w*_{2}, *w*_{3}, . . . , *w _{n}*
such that (

Path from
A to C is {A, B, C} or {A, C}

**Length**

The
length of a path in a graph is the number of edges on the path, which is equal
to Nâ€“1. Where N is the number of vertices.

Length of
the path from A to B is {A, B} = 1

Length of
the path from A to C is {A, C} = 1 & {A, B, C} = 2.

If there
is a path from a vertex to itself with no edges then the path length is 0.
Length of the path from A->A & B -> B is 0.

**Loop**

A loop in
a graph is defined as the path from a vertex to itself. If the graph contains
an edge (*v,v*) from a vertex to
itself, then the path *v*, *v* is sometimes referred to as a *loop*.

**Simple Path**

A *simple* path is a path such that all
vertices are distinct (different), except that the first and last vertexes are
same.

Simple
path for the above graph {A, B, C, D, A}. First and Last vertex are the same
ie. A

**Cycle**

A *cycle* in a graph is a path in which the
first and the last vertex are the same.

**Cyclic Graph**

A graph
which has cycles is referred to as cyclic graph. A graph is said to be cyclic,
if the edges in the graph should form a cycle.

**Acyclic Graph**

A graph
is said to be acyclic, if the edges in the graph does not form a cycle.

**Directed Acyclic Graph (DAG)**

A
directed graph is acyclic if it has no cycles, and such types of graph is
called as Directed Acyclic Graph.

**Degree**

The number of edges incident on a vertex determines its degree. The degree of the vertex V is written as degree (V).

**Indegree : **The indegree of the vertex V, is
the number of edges entering into the vertex V.

**Outdegree: **The outdegree of the vertex V, is
the number of edges exiting from the vertex V.

__Representation of Graph__

A Graph
can be represented in two ways.

i.
Adjacency Matrix

ii. Adjacency
List

__Adjacency Matrix Representation__

i.
Adjacency matrix for directed graph

ii.
Adjacency matrix for undirected graph

iii.
Adjacency matrix for weighted graph

**Adjacency matrix for directed graph**

One
simple way to represent a graph is Adjacency matrix. The adjacency matrix A for
a graph G = (V, E) with n vertices is an n x n matrix, such that

A_{ij}
= 1, if there is an edge V_{i} to V_{j} A_{ij} = 0, if
there is no edge

**Adjacency matrix for undirected graph **

**Adjacency matrix for weighted graph**

Here A_{ij}
= C_{ij} if there exists an edge from V_{i} to V_{j}.
(C_{ij} is the weight or cost). A_{ij} = 0, if there is no
edge.

If there
is no arc from i to j, C[i,j] = âˆž, where i â‰ j.

**Advantage**

^{Ã˜} Simple to implement.

**Disadvantage**

^{Ã˜ }Takes O(n^{2})
space to represents the graph.^{}

^{ }

^{Ã˜ }Takes O(n^{2})
time to solve most of the problem.^{}

__Adjacency List Representation__

In this
representation, we store the graph as a linked structure. We store all vertices
in a list and then for each vertex, we have a linked list of its adjacency
vertices.

**Adjacency List for directed unweighted graph**

**Disadvantage of Adjacency list representation**

It takes
O(n) time to determine whether there is an arc from vertex i to vertex j, since
there can be O(n) vertices on the adjacency list for vertex i.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Representation of Graphs |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.