# What types of questions is graph theory best suited at answering?

I'm dealing with a particular optimization problem at work (financial scorecards), and I noticed that my dataset can be set up as a set of DAGs, where the scorecards for each customer comprise a customer-specific tree. However, I'm unsure as to whether that's a useful characterization.

To that extent, in a more broad sense, I was wondering: what types of question does graph theory best answer? I can think of a few applications, namely:

• find minimum distance between nodes (e.g., directions from point A to point B)
• optimal path for traverse entire graph and hitting all nodes while minimizing distance (e.g., traveling salesman)
• given an incomplete graph, determine whether some nodes should be connected (e.g., "find my friends" on facebook/linkedin)

Are there any other major applications?

-
Assignment problem using the Hungarian algorithm. – Shahab Apr 5 '13 at 14:50

Going from a dataset (that is not itself essentially a graph) to a graph data structure means you are losing information. Thus:

1. If the information lost is unimportant for the problem you want to solve, then this is a gain. You might still not be able to solve the problem, but solving it is, in principle, easier.

2. If the information lost is important, then either:

• If the dataset is e.g. too large too process as a whole, you might still be better off going to a graph data structure (and merely acknowledging this limitation when reporting the results), or
• you're better off working with the original data.

I was shot down the other day with this situation. I wanted to analyse term co-occurences in Twitter data using graph methods. I was asked "Why graphs? Why not just analyse the data directly?" to which I did not have a sensible answer.

I think it's hard to say what problems graph theory is best at solving (aside from saying something tautological ["it's best at solving graph theory problems"], or philosophical ["any problem solved on the graph can also be solved using the original data"]). However, there's a list of notable graph algorithms over at Wikipedia (here), perhaps becoming familiar with the algorithms there would give intuition as to what problems graph theory is best at solving.

-
Thanks, great answer. Related question: is there a concept within graph theory of each node possessing properties (e.g., in the case of twitter, it could be the sender, content, time of posting, device used to post, etc.)? Are there any algorithms that allow the use of this type of data? – eykanal Apr 5 '13 at 15:04
Depending on the type of data, these graphs might be called coloured graphs, vertex-weighted graphs, labelled graphs, but I think it's more common to simply call them graphs and explain in the text that the vertices have certain properties. – Douglas S. Stones Apr 5 '13 at 15:11
As for algorithms, they tend to be domain-specific. As a random example, Felsenstein's algorithm is an efficient method for computing the likelihoods in a phylogenetic tree using the Bayesian method and is widely used in software such as MrBayes. While of critical importance for this specific task, I suspect it's usefulness drops significantly for other tasks. – Douglas S. Stones Apr 5 '13 at 15:20