I'm trying to get more acquainted with problems that require Graphs to be solved (are are best solved by graphs).
If someone has an old ACM Programming Competition problem that utilized graphs, or have another problem that they found particularly enlightening as they worked it out I would appreciate it. I want to familiarize myself with graphs, identifying graph-type problems easily and be able to utilize basic graph traversal algorithmns.
Anyone have a sweet problem they can send my way?
To get a better grasp of operations on graph, you might want to just implement some known Graph algorithms.
Try implementing a Nurikabe solver or generator. It would need quite a bit of classical graph operations.
You don't say what language you are using (thinking of using). If I may, I'd suggest Lisp or Python. They're both good for easy graph manipulation. If you want to be really fancy, you might want to create a pretty output using PyGame.
As for problem, have a look at a simple program and convert it into a graph. Tip, each token is a node. Assuming that you have some loops and equations, then you could traverse the graph and identify what could be moved outside of the loop. Equations could be rearranged to be more "efficient".
My rationale for this problem is that it will help you as a programmer by seeing the sort of processes that might be going on inside the optimisation phases of a compiler.
BTW, if you give the above a go, have a look at Plex, it will save you a lot of time with parsers.
http://codekata.pragprog.com/2007/01/kata_nineteen_w.html
Hint: a DAWG is a pretty good method.
You should be familiar with the Konigsberg Bridge Problem. You should also get really familiar with the types of data structures that often come up in graph theory problems.
Graphs can literally be used to model almost any problem. Topcoder.com Marathon Matches often lend themselves to graph-based solutions.
You might checkout some of these problems - and there are more where they came from.
I found this book to be extremely useful (Amazon Link): Programming Challenges
Not only does it give a pretty indepth explanation of graphs, trees, basic data structures it gives a handful of programming challenges involving each type! This document is more useful to me than my textbook!
Here are some of the Graph Problems in it:
Problems involving Graph Traversal:
Problems involving Graph Algorithms (Dijkstra's, Min Spanning Tree, etc):