Application of graph theory in Computer Science

Question

i am a CS student, we did graph theory in class and i found it interesting. i wanted to know what the real applications of graph theory in the computer science field. For an example i found that some theories in the graph can be used to designing networks, what are other similar applications ?

thank you

Answer 1

This is in no way a definitive answer, and I do not intend it as such.

Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).

However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.

Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.

Answer 2

Modelling networks are done using graphs. For example if you need to study broadcasting or multicasting in certain types of network topologies you would use graphs to model the networks. For example:

• hypergraphs
• complete graphs
• star graphs
• meshes

When you model networks using graphs you can use all the power of graph theory to analyse the network.

This is just one fo many applications of graph theory in computer science.

Answer 3

Graph Theory has a variety of applications. My favorite ones are the applications in:

• Large Scale Networks
• Social Computing
• Bio-informatics

Answer 4

Applications of graph theory are abundant within computer science and in every day life:

• Finding shortest routes in car navigation systems
• Search engines use ranking algorithms based on graph theory
• Optimizing time tables for schools or universities
• Analysis of social networks
• Optimizing utilization of railway systems
• Compilers use coloring algorithms to assign registers to variables
• Path planning in robotics

Answer 5

The directory structure is a tree structure(with root nodes and child nodes. In networks it's used to find the shortest route using the minimum spanning tree,Dijkstra's algorithm.

Answer 6

I once applied graph theory in a ladder diagram editor and compiler.