bomen

Onderwerp:
Diagrammen

boom

Een samenhangende graaf zonder cykels noemen we een boom, zoals in onderstaande applet. Test: Probeer met het groene punt uit of je meer dan één pad kunt vinden tussen b.v. de knopen A en D. Klik op de resetknop en creëer zelf andere bomen.

In een boom is er maar één pad tussen twee knopen. Waar of niet?

Vink alles aan wat van toepassing is
  • A
  • B
Controleer mijn antwoord (3)

minimaal opspannende boom

Een bekende toepassing van bomen is het bepalen van de minimaal opspannende boom. Aan bogen kan je een gewicht toekennen. Dat kan gewoon de lengte zijn, maar je kunt ook andere parameters inbrengen afhankelijk van de situatie. De minimaal opspannende boom is de graaf met het minimale totale gewicht waarin zonder cykels alle knopen verbonden zijn. Je leert er meer over in het GeoGebraboek Minimaal opspannende boom.