Some Concepts
Eulerian Graphs
- Eulerian graph: If it has a closed trail that tranverses every edge once and once only.
There may be more than one such trail, each of which is called Eulerian trail or Eulerian circuit.
Theorem: A connected graph is Eulerian if and only if the every node in the graph has an even degree.
Theorem: A connected digraph is directed Eulerian if and only if every node satifies d_in = d_out.
Hamiltonian Graphs
- Hamiltonian graph: If it has a closed trail that tranverses every node once and once only.
Theorem: Let G be a simple graph with N (>=3) nodes. If, for every pair of non-adjacent node v and u, their degrees always satify k(v)+k(u)>=N, then G is Hamiltonian.
Theorem: Let G be a strongly connected digraph with N nodes. If all nodes satify both d_in >= N/2 and d_out >= N/2, then G is directed Hamiltonian.
Some Problems
Solve the Shortest Path Length Problem
Dijkstra's Algorithm: Moving from A toward L and associating each intermediate node V with a number l(V) that is equal to the shortest path length from A to V.
Chinese Postman Problem
- The problem is for a postman to deliver letters in such a way that he passes every street at least once and finally returns to the starting point (the post office), traversing a shortest possible total path-length.
- Ideas :
To have a solution, the graph must be Eulerian.
To make the graph be Eulerian, some edges need to be added to nodes with odd degrees.
The postman must traverse on every added edge (otherwise, they do not need to be added).
The choice with the least total length of added edges provides an optimal solution.
Maxium Flows
- Ford-Fukerson Algorithm