title: Minimaal opspannende boom
text: 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.
  
  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  van het gewicht van de minimaal opspannende boom van een volledige graaf  met  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  naar oneindig gaat. Deze constante is de waarde van de Riemann-zèta-functie van 3:
  
  Dit is een opmerkelijk resultaat aangezien elke opspannende boom van  zijden heeft en de verwachte waarde van een willekeurige opspannende boom in dit geval gelijk is aan , 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.
  
  Grafentheorie