Applications ("in everyday life") of graph theory

Question

EDIT another idea someone gave me was to consider flows in a network that would not only depend on the node at the beginning and at the end of a vertex but also about the vertex itself, like a maximal flow for the vertex...

I'm currently working on a project concerning both computational science and mathematics and am looking for concrete applications of graph theory.

I more particularly want to focus myself on the notion of flaws in a graph, for instance for a start I thought about working on how to homogenize the value of the nodes of a graph to avoid great gapes between two of them - the example I had in mind here was that of a network distributing energy ( how great difference of values between nodes fosters short cuts...)

I am in the first place pretty interested by examples that can easily lead to simple models, since I will probably end up having to code on Python a bit :)

Hence my question is : do you know any original examples of applications of the graph theory, that would be relatively easy to create and study a model of? By original, I mean -if possible! It would really be a plus- not the too "obvious", used and therefore scholar ones, like transportation networks, movement of crowds, distribution of energy in a electrical network...

Thank you very much for the attention and -I hope!- the future help/support. If you have any advice, feel free to share :)

(+ edit: I have lowered the too personally-focused tone of this post so it can gather all the graphotheoristophiles)

Answer 1

Any situation in which you have a collection of tasks, some of which need to be completed prior to others (e.g. must take French I before taking French II) can be modeled as a directed acyclic graph (the graph should be acyclic because it doesn't make sense to have mutual dependencies). You can then use topological sorting to determine an appropriate order for completing these tasks. This is trivial to do for simple things, and we do it in our heads all the time (I need to get the keys to start my car, then get in the car to go to the grocery store, and then buy food so I can eat), but you can imagine situations where tasks number in the 1000s or more. If you were running a shipping company and for example, many departing trucks needed to wait for others to arrive so that packages could be transferred from one to the other.

Answer 2

Networks are coming up increasingly often in economics. I would be inclined to look into algorithmic game theory and economic networks. Strategic network formation, routing games, auctions over graphs, and social networks are all relevant here. Routing games use a lot of potential function arguments, so someone familiar with Electricity & Magnetism would feel comfortable. The author of Networks, Crowds, and Markets also has a preprint you can download from his site: http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf

Operations research deals a lot with graph theory. Many graph theoretic problems can be formulated as Linear and Integer Programs. It's a nice way to study the constraints and understand the problem, as well as solve it by using LP relaxations of some flavor (cutting plane, branch and bound, etc.).

Graph theory also comes up a lot in Chemistry. In particular, spectral graph theory is very much used in chemistry. I'm not a chemist or comfortable enough with the literature to tell you much more.

Coloring is also useful in storage. Two vertices are adjacent if they can't be stored together. Then you find the minimum coloring of the graph to determine the number of different storage units you will need.