Graphs

GRAPHS
A graph G consist of
 Set of vertices V (called nodes), (V = {v 1 , v 2 , v 3 , v 4 ...
… }) and
 Set of edges E (i.e., E {e 1 , e 2 , e 3 ......cm}
 A graph can be represents as G = (V, E), where V is a finite
and non empty set of vertices and E is a set of pairs of
vertices called edges.
Cont.
Cont.

Consider a graph, G in previous figure Then the vertex V and
edge E can be represented as:

V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } and E = {e 1 , e 2 , e 3 , e 4 ,
e 5 , e 6 } E = {(v 1 , v 2 ) (v 2 , v 3 ) (v 1 , v 3 ) (v 3 , v 4 ),(v 3 ,
v 5 ) (v 5 , v 6 )}.

There are six edges and vertex in the graph.
Sample Graph

graph
A D
B C E
BASIC TERMINOLOGIES

A directed graph can be represented geometrically as a set of
marked points (called vertices) V with a set of arrows (called
edges) E between pairs of points (or vertex or nodes) so that
there is at most one arrow from one vertex to another vertex.

For example, the previous figure shows a directed graph, where
G ={a, b, c, d }, {(a, b), (a, d), (d, b), (d, d), (c, c)}
Cont.

We can also say that the edge (a, b) is incident from a to b.

The vertex a is called the initial vertex and the vertex b is called
the terminal vertex of the edge (a, b).

If an edge that is incident from and into the same vertex, say (d,
d) of (c, c) in previous figure , is called a loop.
Cont.

Two vertices are said to be adjacent if they are joined by an edge.

Consider edge (a, b), the vertex a is said to be adjacent to the
vertex b, and the vertex b is said to be adjacent from the vertex a.

A vertex is said to be an isolated vertex if there is no edge
incident with it. In previous figure vertex E is an isolated vertex.
Cont.

An undirected graph G is defined abstractly as an ordered pair
(V, E), where V is a set of vertices and the E is a set at edges.

An undirected graph can be represented geometrically as a set of
marked points (called vertices) V with a set at lines (called
edges) E between the points.
Cont.
Cont.

Two graphs are said to be isomorphic if there is a one-to-one
correspondence between their vertices and between their edges
such that incidence are prevented.

The next figure shows an isomorphic undirected graph.
Cont.
Cont.

The number of edges incident on a vertex is its degree.

The degree of vertex a, is written as degree (a).

If the degree of vertex a is zero, then vertex a is called isolated
vertex.

For example the degree of the vertex a in previous figure is 3.
Cont.

A graph G is said to be weighted graph if every edge and/or
vertices in the graph is assigned with some weight or value.

A weighted graph can be defined as G = (V, E, W e , W v ) where
V is the set of vertices, E is the set at edges and W e is a weights
of the edges whose domain is E and W v is a weight to the
vertices whose domain is V.
Cont.
REPRESENTATION OF GRAPH
There are two standard ways of maintaining a graph G in the

memory of a computer.
1. Sequential representation of a graph using adjacent
2. Linked representation of a graph using linked list
ADJACENCY MATRIX REPRESENTATION

In this section let us see how a directed graph can be represented
using adjacency matrix.

Considered a directed graph in next figure where all the vertices
are numbered, (1, 2, 3, 4...... etc.)
Directed graph
Cont.
The adjacency matrix A of a directed graph G = (V, E) can be

represented with the following conditions:

A ij = 1 {if there is an edge from V i to V j or if the edge (i, j) is
member of E.}

A ij = 0 {if there is no edge from V i to V j }
Cont.
undirected graph
The adjacency matrix A of an undirected graph G = (V, E) can be

represented with the following conditions

A ij = 1 {if there is an edge from V i to V j or if the edge (i, j) is
member of E}

A ij = 0 {if there is no edge from V i to V j or the edge i, j, is not
a member of E}
Cont.
Cont.
directed weighted graph

The adjacency matrix A for a directed weighted graph G = (V, E,
W e ) can be represented as

A ij = W ij { if there is an edge from V i to V j then represent its
weight W ij .}

A ij = – 1 { if there is no edge from V i to V j }
Cont.
Cont.
LINKED LIST REPRESENTATION

In this representation (also called adjacency list representation),
we store a graph as a linked structure.

First we store all the vertices of the graph in a list and then each
adjacent vertices will be represented using linked list node.
Directed graph
Cont.
Directed weighted graph.
Cont.

Graphs

Uploaded by

Copyright:

Available Formats

Graphs

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Graphs

Uploaded by

Copyright:

Available Formats

GRAPHS

There are two standard ways of maintaining a graph G in the

The adjacency matrix A of a directed graph G = (V, E) can be

The adjacency matrix A of an undirected graph G = (V, E) can be

You might also like