Problems on Graphs
What kind of problems do we want to solve on/via graphs?
- is the graph fully-connected?
- can we remove an edge and keep it fully-connected?
- which vertices are reachable from v? (transitive closure)
- is there a cycle that passes through all vertices? (circuit)
- what is the cheapest cost path from v to w?
- is there a tree that links all vertices? (spanning tree)
- what is the minimum spanning tree?
- what is the maximal flow through a graph?
- …
- can a graph be drawn in a plane with no crossing edges? (planar graphs)
- are two graphs "equivalent"? (isomorphism)
- …
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}