bomen

Een boom is een samenhangende graaf zonder cykels.

figuur 29: voorbeelden bomen

Een opspannende boom van een samenhangende graaf G is een deelgraaf van G die 

- alle punten van G bevat en

- een boom is.

Zie figuur 30 voor een graaf G en figuur 31 voor 3 opspannende bomen van G.

figuur 30

figuur 31

opdracht 18

Bepaal van de graaf uit figuur 32 twee verschillende opspannende bomen, d.w.z. die minstens één lijn van elkaar verschillen.

De waarde die we een lijn geven, noemen we het gewicht van die lijn. Als we alle lijnen van een graaf G een gewicht gegeven hebben, dan noemen we G een gewogen graaf of een netwerk. Het gewicht van een deelgraaf H van G is dan de som van de gewichten van alle lijnen van H.

opdracht 19

In figuur 33 zie je een graaf uit de vorige opgave, maar nu gewogen. De punten stellen in deze graaf een aantal steden voor. Er is een lijn tussen twee steden als het mogelijk is om tussen die twee steden een spoorlijn aan te leggen. De gewichten zijn de aanlegkosten in miljoenen euro's. Bepaal de goedkoopste manier om ervoor te zorgen dat alle steden onderling via het spoor bereikbaar zijn. Wat zijn de totale kosten?

figuur 33

Een minimale opspannende boom van een samenhangende gewogen graaf G is een opspannende boom van G waarvoor het totale gewicht van alle lijnen zo klein mogelijk is.