Applications of Graph Theory in Real Life
Sharathkumar.A,
Final year, Dept of CSE,
Anna University, Villupuram
Email: kingsharath92@gmail.com
Ph. No: 9789045956

Abstract
Graph theory is becoming increasingly significant as it is applied to other areas of mathematics, science and technology. It is being actively used in fields as varied as biochemistry (genomics), electrical engineering (communication networks and coding theory), computer science (algorithms and computation) and operations research
(scheduling). The powerful combinatorial methods found in graph theory have also been used to prove fundamental results in other areas of pure mathematics. We discuss about computer network security (worm propagation) using minimum …show more content…
The teaching requirement matrix p = [ pij ] is given below in figure 6.1.

p

y1

y2

y3

y4

y5

x1

2

0

1

1

0

x2

0

1

0

1

0

x3

0

1

1

1

0

x4

0

0

0

1

1

Figure 6.1. The teaching requirement matrix

We

first

construct

the

bipartite

multigraph G shown

below

in

figure

6.2.

Figure 6.2. The bipartite multigraph G

Next, we construct the line graph L(G). The adjacency matrix of L(G) is given below.

0

1

1

1

0

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

0

1

1

0

1

0

0

0

1

0

0

0

1

1

1

0

0

1

0

0

1

1

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

1

1

0

0

0

1

1

0

0

0

0

0

1

0

0

1

1

0

0

0

0

1

0

0

0

1

0

1

0

0

0

0

0

1

0

1

1

1

0

1

0

0

0

0

1

0

1

0

0

1

0

1

0

0

0

0

0

0

0

0

0

1

0

Figure. The adjacency matrix of L(G)

Now, we use the vertex coloring algorithm [7] to find a minimum proper 4-coloring of the vertices of L(G).

Figure 6.3. A minimum proper 4-coloring of the vertices of L(G)

Vertex Coloring: (1, green), (2, red), (3, blue), (4, yellow),