Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
this could be an awfully long list. I'm thinking CW ? –  Suresh Venkat Feb 14 '11 at 6:24
3  
This seems a little too general even for a CW. Graph theory is ubiquitous in TCS. –  Huck Bennett Feb 14 '11 at 7:05
25  
Asking for topics in CS that do not use graphs might have yielded the shorter list. –  Raphael Feb 14 '11 at 7:14
1  
@peedarpk: If you're following a class on graph theory in a CS cursus, why don't you ask the professor? –  Anthony Labarre Feb 14 '11 at 9:03
2  
Really, can we close this now? The answer to this question is on wikipedia (en.wikipedia.org/wiki/Graph_theory#Applications) or in any introductory undergraduate textbook. –  RJK Feb 16 '11 at 14:25
show 3 more comments

6 Answers 6

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.

share|improve this answer
    
Great answer to what the OP was unlikely to have been asking! But topically, why don't we forget the original (bad) version of the question and pretend we're playing Jeopardy: "What is the intuition behind the ubiquity of graphs in nearly all sub-disciplines of theoretical computer science?" –  RJK Feb 16 '11 at 18:01
    
@RJK: Perhaps I should have read the question more carefully, but I thought this might at least be interesting to the person asking the question. –  Joe Fitzsimons Feb 16 '11 at 18:06
add comment

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.

share|improve this answer
add comment

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

  • Large Scale Networks
  • Social Computing
  • Bio-informatics
share|improve this answer
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.