Notizen
Summary of Chapter 4
Inhalt der Notizen (1)
Seite 1
1 A graph is traversable if it is possible to traverse (travel along) every arc just once without taking your pen from the paper.
2 A graph is traversable if all the valencies are even.
3 A graph is semi-traversable if it has precisely two odd valencies. In this case, the start and finish point will be the two vertices with odd valencies.
4 A graph is not traversable if it has more than two odd valencies.
5 The route inspection algorithm can be used to find the shortest route that traverses every arc at least once and returns to the starting point.
6 If there are only two odd valencies, repeat the shortest path between them and add it to the network.
7 If there are more than two odd valencies, consider all possible complete pairings, select the one that gives the smallest total, then add this pairing to the network.
Page 1
Informationen
- Beschreibung
- Decision (Chapter 4: Route inspection (Chinese postman problem)) Notiz am Summary of Chapter 4, erstellt von jakubburger am 11/04/2013.
- Erstellt von
- jakubburger · Apr 2013
- Aktualisiert
- 16 Aug 2016
- Aufrufe
- 85
- Tags
- Bewertung
Mehr zu Graph Paths, Cycles and Route Problems