IV. GRAPH APPLICATIONS In computer

IV. GRAPH APPLICATIONS
In computer science, graphs are used to
represent networks of communication, data
organization, computational devices, the flow of
computation, etc. One practical example is the link
structure of a website could be represented by a
directed graph. The vertices are the web pages
available at the website and a directed edge from
page A to page B exists if and only if A contains a
link to B.
Graph-theoretic methods, in various forms, have
proven particularly useful in linguistics, since
natural language often lends itself well to discrete
structure. Traditionally, syntax and compositional
semantics follow tree-based structures, whose
expressive power lies in the Principle of
Compositionality, modelled in a hierarchical graph.
Within lexical semantics, especially as applied to
computers, modelling word meaning is easier when
a given word is understood in terms of related
words; semantic networks are therefore important
in computational linguistics. [1].
A graph structure can be extended by assigning a
weight to each edge of the graph. Graphs with
weights, or weighted graphs, are used to represent
structures in which pair wise connections have
some numerical values. For example if a graph
represents a road network, the weights could
represent the length of each road.

A. Graph Colouring
Colouring of a simple graph is the assignment
of a colour to each vertex of the graph so that no
two adjacent vertices are assigned the same colour.
Graph colouring has a variety of applications to