|
|||||||||||||||
| De Chinese Postbode. | |||||||||||||||
Een postbode haalt de post op bij het postkantoor, en gaat die daarna bezorgen. Hij moet alle straten zijn gebied minstens één keer langsgaan en wil dat graag doen door door een zo klein mogelijke totale afstand af te leggen. De graaf die hierbij hoort is een gewogen graaf (het gewicht van een straat is de lengte ervan). Als het een Eulergraaf is, dan is uiteraard de beste route gewoon een Eulerroute, want daarin wordt elke verbindingslijn precies één keer gebruikt. Korter kan niet. Met het Fleury-algoritme vind je snel zo'n route. |
 |
||||||||||||||
| Maar als de graaf
géén Eulergraaf is, dan zul je sommige verbindingslijnen twee keer
moeten langslopen. Je voegt eigenlijk verbindingslijnen toe:
de straten die dubbel gelopen gaan worden teken je als twee
verbindingslijnen tussen de betreffende knooppunten. Dat heet het
Euleriseren van de graaf. De vraag is natuurlijk: |
|||||||||||||||
|
|
|||||||||||||||
| Dat is geen
eenvoudige vraag...... Daarom eerst maar een versimpeling: De graaf heeft precies twee knooppunten met oneven graad. |
|||||||||||||||
| Stel dat we de
verbindingslijnen V* gaan toevoegen (= dubbel gaan lopen).
Dan vormen al die verbindingslijnen samen een pad tussen beide
knooppunten met oneven graad. Maar we weten al hoe we zo'n minimaal pad moeten vinden: Dijkstra's algoritme natuurlijk! |
|||||||||||||||
|
|||||||||||||||
| De graaf heeft meer dan twee knooppunten met oneven graad. | |||||||||||||||
| Edmonds en Johnson
hebben hier in 1973 een goed algoritme voor gevonden. Daar hebben we eerst de theorie van stromen in een graaf voor nodig, dus je moet even geduld hebben tot later..... |
|||||||||||||||
| OPGAVEN | |||||||||||||||
|
|||||||||||||||
|
© h.hofstede (h.hofstede@hogeland.nl) |
|||||||||||||||
