# Graph Theory Applications?

What are the areas where graph theory can be applied?

Cause I wonder what applications this have on the real world.

Does it solve certain problems and stuff?

Areas such as communication networks and coding in IT, genomics, computation, and scheduling in operations research

-
You may find something useful at math.stackexchange.com/questions/130980/… – Gerry Myerson Jan 25 '13 at 3:45
Graphs arise most obviously in computer science, I think, but they arise in many other places as well. I know linking to the Wikipedia article isn't doing much but in this case it really does answer this question pretty well. – lamb_da_calculus Jan 25 '13 at 3:46
Perhaps mathoverflow.net/questions/2556/… will be helpful. – dinoboy Jan 25 '13 at 6:14
When people ask about "real world applications" I am always disheartened at their failure to see the curiousness and wonder and enormous potential of mathematics as a thing itself. It's like asking what a baby is good for. It's like the King of England at the world's fair asking Faraday what his "electric motor" is good for. (Faraday's answer was that some day His Majesty will be able to tax it.) The question tacitly denies the reality and potential of mathematics itself. – George Frank Jan 25 '13 at 11:52
@GeorgeFrank: How do you react when someone says, "I love graph theory for itself, but I'm curious --- what applications does it have?" Still disheartened? Still intending to reply with babies and motors? – Gerry Myerson Jan 25 '13 at 11:56

Graph theory is rapidly moving into the mainstream of mathematics mainly because of its applications in diverse fields which include biochemistry (genomics), electrical engineering (communications networks and coding theory), computer science (algorithms and computations) and operations research (scheduling),including social networks. Aircraft scheduling: Assuming that there are k aircrafts and they have to be assigned n flights. The ith flight should be during the time interval (ai, bi). If two flights overlap, then the same aircraft cannot be assigned to both the flights. This problem is modeled as a graph as follows. The vertices of the graph correspond to the flights. Two vertices will be connected, if the corresponding time intervals overlap. Therefore, the graph is an interval graph that can be colored optimally in polynomial time

-
Perhaps elaborate on these applications? At least one or two concrete examples? Right now this is more suited for being a comment than an answer; but if you add some references, and some concrete examples of applications, then it can be a very good answer. – Asaf Karagila Mar 19 '14 at 0:40

If you've ever used Google, you're looking at the world's most (financially) valuable graph theory application. At the heart of their search engine technology is an algorithm called PageRank, which uses numerous graph theory concepts — including cliques and a lot of connectivity information — to determine how important a given web page is. It does this, in essence, by starting with a rough notion of each page's importance and then repeatedly refining its estimates by 'flowing' importance values from page to page; for more specific details you can check the Wikipedia page linked above, or just search the web for further information on the algorithm.

-
Amusingly, PageRank is not a rank given to a page, but rather a ranking method invented by Page. One of the founders of Google. – Asaf Karagila Mar 19 '14 at 1:50

This is an answer from an amateur. I've had similar problems in the past. My fellow students who had not come across Graph Theory threatened to drop the subject saying, "what is this a newspaper puzzle class??"

Firstly you must read the first few pages of Frank Harary's book where he gives a lovely exposition of the basic applications of the subject and a brief introduction to its origins which also came about due to a real world problem.

I have not progressed in the subject far enough to see it properly applied to real world problems. But this is what I have understood. Graph Theory is the study of relationships. Given a set of nodes - which can be used to abstract anything from cities to computer data - Graph Theory studies the relationship between them in a very deep manner and provides answers to many arrangement, networking, optimisation, matching and operational problems. And the strength of it is the the power to be used to abstract such a vast array of real problems. Graph Theory should be renamed Network Theory or something. Because to me that is what it is. It is the study of inter-object relationships where the objects can be pretty much anything. And this study of relationships is useful pretty much everywhere.

For an idea of how powerful Graph Theory actually is, check out this question where it was used to answer a Real Analysis problem!

-

They can model many problems that involve state transitions nicely. For example, imagine you have a pulse going through a wall made up of several layers. The signal is attenuated (reduced) by travelling through each material, and partially reflected/transmitted at each boundary. What is the total energy that you receive back at the transceiver? If you try doing the sum you get a very difficult problem. But you can rephrase the problem in terms of a directed weighted graph and make things much easier:

Have vertices representing the start node, each intermediate layer (which gets two: one per direction of travel), and one outgoing node for the signals that are simply lost on the other side. The edges are weighted according to how much the signal is attenuated when going from one state to the other (material attenuation and reflection/transmission combined). Now the result you want can be calculated by performing a simple calculation on the weighted adjacency matrix.

The point is that graphs model "I have stuff, and it's connected to/interacting with other stuff". This is an absurdly general concept, and so applications of graph theory will pop up in all kinds of neat places.

-

Graph theory, like many fields of mathematics, can provide a more precise way of describing what people in the real world are already doing. For example, a colleague and I are investigating how library catalogers over the years have, at least since the mid 19th century, created graph structures within library catalogs - in their book, index card, and database record forms. Fascinating questions - both abstract and practical - arise. Graph theory combined with key bits from the history of science helps formulate and answer even more fascinating questions: http://ejournals.bc.edu/ojs/index.php/ital/article/view/1868/0

-