Algorithmus - Bestimmung des Zentrums eines Baums

• Involvierte Definitionen:
  • Baum
  • Zentrum eines Graphen
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Algorithmus: Bestimmung des Zentrums eines Baums

Sei ein Baum.

Das Zentrum können wir bestimmen, indem wir

1. Setze .
2. Streiche alle äußeren Knoten (also alle Blätter) von . Der resultierende Baum sei .
3. Setze und fahre mit 2. fort.
4. Sind nur noch oder Knoten übrig, so bilden diese das Zentrum von .

Anmerkung