Definition - Kanonische Wurzel (Graphentheorie)

• Generalisierungen:
  • Wurzel eines Baumes
• Hinreichende Aussagen:
  • Algorithmus zur Bestimmung des Zentrums eines Baums
• Involvierte Definitionen:
  • Baum
  • Wurzel eines Baumes
  • Exzentrizität eines Knotens
  • Zentrum eines Graphen
  • Lexikographische Totalordnung
  • Codierung eines Wurzelbaums
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Kanonische Wurzel

Sei ein Baum.

• Enthält das Zentrum genau einen Knoten , so ist die kanonische Wurzel von .

• Enthält genau zwei Knoten so konstruieren wir die Codes und und vergleichen sie anschließend lexikographisch.

  Ist , so wählen wir als kanonische Wurzel von , andernfalls wählen wir .