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

Solution 1:

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!

Solution 2:

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.

Solution 3:

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 $i$-th flight should be during the time interval ($a_i$, $b_i$). 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

Solution 4:

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.

Solution 5:

Alexander Schrijver, A Course in Combinatorial Optimization includes multiple applications (just search for "Application" in the text). The parts that appear to get used the most are shortest paths, maximum flows, maximum matchings and arc-disjoint paths. Of course, it is usually the algorithms that get applied rather than the existence theorems, but this is common to almost all applications of mathematics, and most of the theorems have algorithmic proofs (which, in some cases, are the standard proofs).

Alexander Schrijver, On the history of the transportation and maximum flow problems focusses on the history of the maximum-flow/minimum-cut theorem. I won't spoil the punchline, but let me just mention that both the maximum-flow and the minimum-cut problem appeared in the middle of the 20th century out of non-mathematical considerations, and both were intended to be applied to the same network.

I generally have the impression is that you don't often see "mere" graphs in the applied world (i.e., graphs with no extra structure on the vertices and edges), because there is usually more information available and it is stupid to ignore it. So you will often see networks, matrices and various other models instead. Note that what is commonly called a "sparse matrix" is essentially a graph with numbers on its edges; so every sparse matrix algorithm that is used in the real world is an application of graph theory.