Graph Problems
Some well known Graph problems and their common names:
- s-t Path. Is there a path between vertices s and t?
- Connectivity. Is the graph connected, i.e. is there a path between all vertices?
- Biconnectivity. Is there a vertex whose removal disconnects the graph?
- Shortest s-t Path. What is the shortest path between vertices s and t?
- Cycle Detection. Does the graph contain any cycles?
- Euler Tour. Is there a cycle that uses every edge exactly once?
- Hamilton Tour. Is there a cycle that uses every vertex exactly once?
- Planarity. Can you draw the graph on paper with no crossing edges?
- Isomorphism. Are two graphs isomorphic (the same graph in disguise)?
Difficulty can be deceiving.
- An efficient Euler tour algorithm O(# edges) was found as early as 1873 [Link].
- Despite decades of intense study, no efficient algorithm for a Hamilton tour exists. Best algorithms are exponential time.