Matrix Representation of Graphs:

Graph Theory

Unit II

Graph:

Let V be a finite set with v₁, v₂, v₃, ……., v_n and E be a finite set with e₁, e₂, e₃, ……., e_m as the members of E, then graph G can be defined as a mathematical system <V, E, φ > where φ is the mapping of edges e in E to ordered or unordered pairs in V.

Adjacent Nodes:

Two nodes n₁ and n₂ are said to be adjacent if there exists an edge between n₁ and n₂.

Undirected Edge:

An edge e which does not have any orientation or direction is known as undirected edge or in other words e is associated with unordered pair of

nodes.

Directed Edge:

An edge e which has orientation or direction is known as directed edge or in other words e is associated with ordered pair of nodes.

Digraph:

A graph G=<V, E> is said to be a directed graph or digraph if all edges in E are having some orientation.

Undirected Graph:

A graph G=<V, E> is said to be a undirected graph if all edges in E are not having some orientation.

Mixed Graph:

A graph in which some of the edges have orientation while some do not.

Weighted Graph:

A graph in which weights are assigned to every edge is called weighted graph.

Indegree:

It is defined as the number of edges incident on a given node.

Outdegree:

It is defined as the number of edges originating from a given node.

Parallel Edges:

Two edges e1 and e2 are known as parallel edges if they originate from one node say v₁ and terminate at another node, say v₂.

Self Loop:

An edge e is said to be a self loop if it originates and terminates at the same node.

* Self loop always constitutes one indegree and one outdegree.

Isolated Node:

A node n which is not adjacent to any other node is known as an isolated node.

Null Graph:

A graph G=<V, E> in which all the nodes are isolated is known as a null graph.

Multigraph:

A graph which contains some parallel edges is called a multigraph.

Simple Graph:

A graph G=<V, E> is said to be a simple graph if it does not contain parallel edges. e.g. For the following graph determine the indegree, outdegree and total degree.

Theorem:

The sum of the total degrees in a graph is always equivalent to twice the number of edges.

Proof:

Every edge constitutes one indegree and one outdegree.

ÞTotal degree is 2 for each edge.

ÞSum of the total degrees is equivalent to twice the number of edges.

Problem: Show that in any graph G, the number of nodes of odd degree is even.

Proof:

By theorem 1- = 2e

=> = + ^{= 2e (i = k+l)}

=> + is even

Now, sum of the degrees of even degree nodes is even.

ÞSum of the degrees of odd degree nodes is even Number of odd degree nodes is even.

Problems:

1. Determine how many nodes are necessary to construct a graph with exactly six edges in which each node is of degree 2.

2. Determine whether it is possible to construct a graph with 12 edges such that two of the nodes have degree 3 and remaining have degree 4.

Converse of a graph:

Let G=<V, E> be a directed graph.

Then the converse of G, written as , is nothing but the directional dual of G, i.e. graph obtained by simply reversing the direction of edges in G.

Complement of a Graph:

Let ^G = <^{V, E}> be a directed graph. Then the compliment of ^G written as , is the system

=<^V, > where = ^V x ^V – ^E

Problem: ^Let G=<V,E> be a graph where ^V =

{v1,v2,v3,v4} & ^E =

{<v1,v2>,<v1,v1>,<v2,v3>,<v3,v3>,<v4,v1

>, <v4,v3>} determine and sketch the graph of G and .

Path:

It is defined as a sequence of edges, in which the terminating node of one edge becomes the starting node of the other edge.

e.g. Path is from v1 to v3.

Length of the path:

The number of edges appearing in a path is designated as length of the path and it is always equal to n-1, where n is the number of nodes appearing in a path.

Elementary Path:

A path P is said to be an elementary path if the nodes are not repeated in a path. This is also known as node simple path.

Simple Path:

A path is P said to be a simple path if the edges in sequence are not repeated.

This is also known as edge simple path.

Determine as many number of paths as you can between nodes 1 and 3.

Circuit:

A circuit in a graph G is defined as a route, which begins and ends at the same node.

Euler’s Circuit:

Let G be a graph, then Euler’s circuit in G is a route that begins and ends at the same node, traversing each edge exactly once.

Necessary condition for the presence of Euler’s circuit is that each node must have an even degree.

Konigsberg’s Bridge Problem:

The Graph of Konigsberg Bridge

Problem:

Find the degree of each vertex for the graphs shown and is it possible to trace the graphs I and II without lifting your pencil from the paper beginning and ending at the same point, retracing of lines is not permitted.

Justify your answer.

Hamiltonian Circuit:

Let G be a graph, then a route that begins and ends at the same node, traversing each node exactly once is known as Hamiltonian circuit.

Generally it is used for travelling salesman problem.

Travelling Salesman Problem:-

Given a set of cities and distances

between each pair. Find the shortest route that visits each city once and returns to the initial city.

Matrix Representation of Graphs:

Two Methods are available –

1)Adjacency matrix representation

2)Incidence matrix representation

Adjacency Matrix

Let G be a graph with M number of nodes. Then this graph can be represented by a MxM matrix A = [a_ij], where a_ij = 1 if arc(x_i, x_j) G

0 if arc(x_i, x_j) G.

e.g. A = ?

Drawback of Adjacency matrix is that it does not represent the graph with parallel edges.

Path matrix can be determined by using Adjacency Matrix Method.

Feasible Flow:

A flow through a T.N. is said to be feasible if it follows the following rules –

1) ф(i, j) ≤ c(i, j)

2) Flows at source and sink must balance each other.

3) At all intermediate nodes, other than source and sink, the flows must balance each other.

Determine the

max. flow through the given TN.

Problem: For the following TN determine whether the flow is feasible or not. Also find out themax. flow.