Minimaal opspannende boom

De minimaal opspannende boom van een verbonden, gewogen graaf is de verbonden subgraaf daarvan met het kleinste totale gewicht. Deze kleinste subgraaf is altijd een boom, dat wil zeggen een graaf zonder cycli.

De minimaal opspannende boom van een graaf. Ieder zijde heeft een gewicht, in dit geval vrijwel gelijk aan de lengte ervan.

Een graaf kan verschillende minimaal opspannende bomen hebben. De twee bomen onder de graaf zijn beide minimaal.

Een algoritme om de minimaal opspannende boom te vinden is het algoritme van Prim:

• kies een willekeurige knoop, de eerste bezochte knoop
• kies de zijde met de laagste waarde verbonden met deze knoop
• neem de knoop aan de andere zijde van de zijde op in de verzameling bezochte knopen
• kies de zijde met de laagste waarde uit deze verzameling naar een knoop die nog niet is bezocht en voeg deze zijde aan de minimaal opspannende boom toe
• neem de nieuwe bereikte knoop op in je verzameling
• ga door tot alle knopen van de graaf bezocht zijn

Hier een ander algoritme voor is Kruskals algoritme, maar er zijn er meer.

Een gegeven graaf kan in het algemeen verschillende minimaal opspannende bomen hebben. Alleen wanneer alle zijden van de graaf een verschillend gewicht hebben is er een unieke, minimaal opspannende boom.

Stelling van Frieze

Alan Frieze bewees in 1985 dat de verwachte waarde $\mathbb {E} (L_{n})$ van het gewicht van de minimaal opspannende boom van een volledige graaf $K_{n}$ met $n$ knopen, waarin het gewicht van elke zijde een onafhankelijk willekeurig gekozen getal uit het eenheidsinterval [0,1] is, volgens een uniforme verdeling, naar een constante waarde neigt wanneer het aantal knopen $n$ naar oneindig gaat. Deze constante is de waarde van de Riemann-zèta-functie van 3:

$\lim _{n\to \infty }{\mathbb {E} (L_{n})}=\zeta (3)=\sum _{k=1}^{\infty }{\frac {1}{k^{3}}}=1,202\dots$

Dit is een opmerkelijk resultaat aangezien elke opspannende boom van $K_{n},(n-1)$ zijden heeft en de verwachte waarde van een willekeurige opspannende boom in dit geval gelijk is aan $(n-1)/2$, die naar oneindig gaat als het aantal knopen naar oneindig gaat.

Steinerboomprobleem

De doelstelling is bij het Steinerboomprobleem hetzelfde, maar in plaats van de gewichten die aan de zijden is toegekend gaat het hierbij om hun lengte en wordt er hierbij toegestaan dat bijkomende knopen en zijden aan de graaf worden toegevoegd om de totale lengte van de minimaal opspannende boom ervan nog te verkleinen.

Voetnoten