AANSLUITINGSPROJECT TUE - VO
startpagina ] omhoog ] [ opdracht uit kortste weg ] gedeelte kortste weg ] kortste weg downloaden ]

 

opdrachten in 
Kun je me de kortste weg vertellen?

2.3  Opgaven

  1. Teken alle verschillende kortste bomen bij voorbeeld 2.1.
  2. In de volgende tabel zie je de afstanden (in mijlen) tussen zes plaatsen in Ierland. Teken een graaf en gebruik het "Greedy" Algoritme om een kortste boom te vinden die deze plaatsen verbindt.

      Athlone Dublin Galway Limerick Sligo Wexford
    Athlone - 78 56 73 71 114
    Dublin 78 - 132 121 135 96
    Galway 56 132 - 64 85 154
    Limerick 73 121 64 - 144 116
    Sligo 71 135 85 144 - 185
    Wexford 114 96 154 116 185 -

  3. Een inbraakalarm is weergegeven in de vorm van een graaf waarvan de kanten gemaakt zijn van zeer kostbaar koperdraad. Elke kant heeft een verschillende waarde (=lengte). Het alarm gaat af als de graaf niet verbonden is. Een inbreker wil zoveel mogelijk van het kostbare koperdraad stelen. Welke kanten moet hij weghalen om een maximale buit binnen te krijgen?
  4. Laat zien hoe je het "Greedy" Algoritme moet aanpassen om een langste opspannende boom te creŽren.
  5. Maak bij de volgende tabellen een graaf en zoek hierbij een kortste en een langste opspannende boom.

 

  Berlijn Londen Madrid Moscou Parijs Rome
Berlijn - 7 15 11 7 10
Londen 7 - 11 18 3 12
Madrid 15 11 - 27 8 13
Moscou 11 18 27 - 18 20
Parijs 7 3 8 18 - 9
Rome 10 12 13 20 9 -

  Aberd. Edinb. F.W. Glasg. Inv. Perth
Aberdeen - 120 147 142 104 81
Edinburgh 120 - 132 42 157 45
Fort William 147 132 - 102 66 105
Glasgow 142 42 102 - 168 61
Inverness 104 157 66 168 - 112
Perth 81 45 105 61 112 -