1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory applications

  1. Sep 24, 2014 #1
    Im not entirely sure what section of PF this post should be in so I apologize in advance if this is not in the correct section.

    I dont know that much graph theory or the various fields that it can be applied to, but I do know that graph theory can be used in social media etc by using dynamic graphs that change over time and you can use it to predict outcomes etc.

    So my question is about how exactly graph theory is applied to these things. I joined a research group at my college that is finding fossils etc at different points all across the world. So my basic idea was to take these sort of data points or points on the map and use graph theory to extrapolate and predict where successive locations should be found. However, not knowing that much about graph theory I was wondering if someone that is more of an expert in the subject than I could tell me whether this is even possible or not or if I'm heading down a deadend.
  2. jcsd
  3. Sep 24, 2014 #2
    Sounds a little contrived to me. There doesn't seem to be anything particularly graph-theoretic about the problem. If you think about how fossils get to where they are, it a complicated causality chain, involving living things going about their business and then the natural processes which make the fossils lucky enough to actually be preserved. I don't see where graph theory comes in to that. You could probably find a way to use it, superficially, because graphs are such a simple structure that you can interpret almost anything in terms of graphs, but I don't know that you would gain anything by doing so. It sounds a bit like using a hammer to eat breakfast with. You could probably do it, but I'm not sure that it would make any sense to do so.

    Although I'm not an expert, it's my sense that graphs are a very useful concept to have, but I'm not sure that the deep theorems are widely useful. That's not to say that there aren't important, yet somewhat restricted niche applications out there. I know someone who has a company that uses substantial graph theory to optimize computer networks, with some level of success. Something like a social network is a place where graphs seem very fundamental because you have people and connections between people, so right on the face of it, you immediately get a big fat graph that you can try to study and answer questions about. And, just off the top of my head, and admittedly a bit contrived, you could come up with problems like sending different messages to every user, such that no two friends get the same message (graph-coloring problem: How many different messages are needed?). I'm not sure that anyone would want to do such a thing, but the existence of things like that that you might possibly want to do in real life by some strange whim do suggest the possible usefulness of studying graph-theoretic properties.
  4. Sep 24, 2014 #3
    Thanks for the detailed reply. Talked to a few different people today and that was pretty much the same conclusion we all came to that there would really be no graph theory applications. The only thing that I may be apply to apply is machine learning to possibly predict locations of where new fossils may e found. They were all found in quarries so plugging in data like temperature quarry locations etc etc might work for machine learning.
    The reason I was hoping to find some way to apply graph theory is because I've always been interested in graph theory and was hoping to get paid to do the research learn graph theory and then apply it some way.
  5. Sep 25, 2014 #4
    There is a lot of application of graph theory to computer algorithms. Pick up any good book on the subject.
  6. Sep 25, 2014 #5
    Graph theory is heavily applied in theoretical chemistry and chemical physics (matter of fact, there are a number of books that specialize on the matter). Especially to applications entailing organic compounds with extensive covalent bond networks (ie many aliphatic organic compounds and aromatic organic compounds especially those that deal with aromaticity). Thus, it's applications can aid in the physical understandings in biochemistry to molecular biology to enzymatic binding studies.
  7. Sep 26, 2014 #6


    User Avatar
    Gold Member

    Protein-protein interaction network analysis in bioinformatics/systems biology uses a lot of graph theory.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook