Bäume in der Graphentheorie

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ein Baum hat sieben Definitionen, und alle meinen dasselbe

Bitten Sie drei Menschen, einen Baum zu definieren, und Sie bekommen drei Antworten. Eine sagt, er sei ein zusammenhängender Graph ohne Kreise. Eine andere sagt, er sei ein Graph mit genau einem Pfad zwischen je zwei Knoten. Eine dritte sagt, er sei ein zusammenhängender Graph mit n - 1 Kanten. Alle drei haben recht, und vier weitere Definitionen ebenso, denn diese Bedingungen sind äquivalent: Jeder Graph, der eine davon erfüllt, erfüllt alle.

Das ist ungewöhnlich, und es ist der Grund, warum Bäume der nützlichste Spezialfall des Fachgebiets sind. Eine Struktur mit sieben äquivalenten Charakterisierungen liefert sieben verschiedene Wege, etwas über sie zu beweisen, und in der Praxis wählt man diejenige, die den Beweis am kürzesten macht.

Beginnen wir mit der Standarddefinition, der bei Diestel und bei Bondy und Murty:

Ein Baum ist ein zusammenhängender kreisfreier Graph. Ein Graph, dessen Komponenten alle Bäume sind, ist ein Wald. Ein Knoten vom Grad 1 in einem Baum ist ein Blatt.

Alles Folgende betrifft einen endlichen, einfachen, ungerichteten Graphen, den Standardfall. Ein Baum kann ohnehin weder eine Schleife noch eine parallele Kante haben, denn beides ist ein Kreis.

Ausgeschrieben lautet das durchgehende Beispiel

V = {1, 2, 3, 4, 5, 6, 7, 8}
E = { {1,3}, {2,3}, {3,4}, {4,5}, {5,6}, {5,7}, {7,8} }

Grade     1:1   2:1   3:3   4:2   5:3   6:1   7:2   8:1
n = 8     m = 7 = n - 1      Gradsumme = 14 = 2m      Blätter: 1, 2, 6, 8

2. Der Äquivalenzsatz und wie sein Beweis funktioniert

Hier ist das Ergebnis vollständig. Es findet sich in im Wesentlichen dieser Form bei West, bei Bondy und Murty und bei Diestel, und es lohnt sich, es auswendig zu kennen, denn jede Zeile ist ein Werkzeug.

Satz. Für einen Graphen G mit n Knoten sind folgende Aussagen äquivalent:
(1) G ist ein Baum, also zusammenhängend und kreisfrei.
(2) Je zwei Knoten von G sind durch genau einen Pfad verbunden.
(3) G ist zusammenhängend und hat n - 1 Kanten.
(4) G ist kreisfrei und hat n - 1 Kanten.
(5) G ist zusammenhängend, und das Entfernen einer beliebigen einzelnen Kante zerlegt ihn (minimal zusammenhängend).
(6) G ist kreisfrei, und das Hinzufügen einer beliebigen einzelnen Kante erzeugt einen Kreis (maximal kreisfrei).
(7) G ist zusammenhängend, und jede Kante ist eine Brücke.

Der Beweis ist kein einzelnes Argument, sondern ein Kreis von Implikationen, jede davon kurz. Es lohnt sich, die Form zu sehen, denn sie erklärt, warum sich die Bedingungen so verschieden anfühlen und doch dasselbe Objekt beschreiben.

Zwei davon verdienen Hervorhebung, weil man sie tatsächlich benutzt.

„Zusammenhängend und n - 1 Kanten“ ist der billigste Test. Kanten zu zählen kostet O(m) und eine Zusammenhangsprüfung O(n + m), Sie können also in linearer Zeit entscheiden, ob ein Baum vorliegt, ohne je nach einem Kreis zu suchen. Beachten Sie, dass keine Hälfte allein genügt: Ein Dreieck plus ein isolierter Knoten hat 4 Knoten und 3 Kanten, ist aber kein Baum, und ein 4-Kreis, zusammenhängend mit 4 Kanten, ist es ebenfalls nicht.

„Minimal zusammenhängend“ und „maximal kreisfrei“ sind dasselbe Objekt aus zwei Richtungen gesehen. Ein Baum liegt genau auf der Grenze: Er hat so wenige Kanten, wie der Zusammenhang erlaubt, und so viele, wie die Kreisfreiheit erlaubt. Deshalb tauchen Bäume immer dann auf, wenn ein Problem nach einer billigsten verbindenden Struktur fragt, und genau das ist das Problem des minimalen Spannbaums .

Alle sieben Bedingungen gelten für das durchgehende Beispiel, und jede wurde direkt geprüft: Es ist zusammenhängend, kreisfrei, hat 7 Kanten bei 8 Knoten, genau einen Pfad zwischen jedem der 28 Knotenpaare, jede seiner 7 Kanten ist eine Brücke, und jede der 21 fehlenden Kanten schließt beim Hinzufügen einen Kreis.

3. Das Blattlemma

Ein kleines Ergebnis trägt die meisten Induktionsbeweise des Fachgebiets.

Blattlemma. Jeder endliche Baum mit mindestens zwei Knoten hat mindestens zwei Blätter.

Der Beweis ist beliebt, weil er nichts als die Definition verwendet. Nehmen Sie einen längsten Pfad P im Baum, etwa von u nach v. Ein solcher Pfad existiert, weil der Baum endlich ist. Betrachten Sie nun u. Hätte u einen Nachbarn w außerhalb von P, so ließe sich P um diese Kante verlängern, im Widerspruch zur Maximalität. Hätte u einen zweiten Nachbarn auf P, so entstünde ein Kreis, im Widerspruch zur Kreisfreiheit. Also hat u genau einen Nachbarn und ist ein Blatt, und dasselbe Argument gilt für v.

Zwei Folgerungen ergeben sich unmittelbar, und beide werden ständig verwendet:

• Eine Induktion über Bäume hat immer einen Basisfall zum Entfernen. Entfernen Sie ein Blatt aus einem Baum, und übrig bleibt ein Baum mit einem Knoten weniger. Dieser eine Schritt ist der Motor des Beweises, dass ein Baum n - 1 Kanten hat, der Prüfer-Kodierung in Abschnitt 7und des Algorithmus zur Bestimmung des Zentrums in Abschnitt 10.
• Die Schranke ist scharf. Ein Pfad hat genau zwei Blätter, „mindestens zwei“ lässt sich also allgemein nicht verbessern. Am anderen Extrem hat der Stern K1,n-1 genau n - 1 Blätter.

Das durchgehende Beispiel hat vier Blätter, 1, 2, 6 und 8, bequem mehr als die garantierten zwei. Eine nützliche Plausibilitätsprüfung beim Debuggen von Baumcode: Wenn Ihre Struktur behauptet, ein Baum zu sein, und weniger als zwei Blätter meldet, stimmt etwas nicht, und der übliche Schuldige ist ein versehentlicher Kreis.

Genau dieses Lemma versagt auch bei unendlichen Graphen. Der einseitig unendliche Pfad hat ein einziges Blatt und der beidseitig unendliche Pfad gar keines, eine der klarsten Illustrationen dessen, was die Endlichkeit leistet, behandelt im Leitfaden zu endlichen und unendlichen Graphen.

4. Wälder und Komponenten gratis zählen

Ein Wald ist ein kreisfreier Graph, zusammenhängend oder nicht. Jede Komponente eines Waldes ist ein Baum, und daraus folgt eine Zählidentität, die man auswendig kennen sollte:

Ein Wald mit n Knoten und k Komponenten hat genau n - k Kanten.

Der Beweis ist eine Zeile: Jede Komponente ist ein Baum, eine Komponente mit ni Knoten trägt also ni - 1 Kanten bei, und die Summe über die k Komponenten ergibt n - k. Setzt man k = 1 , erhält man den Baumfall zurück.

Rückwärts gelesen wird die Identität vom Fakt zum Werkzeug:

k = n - m        die Anzahl der Komponenten eines Waldes,
                 allein aus seiner Größe berechnet, ganz ohne Traversierung

Das ist wirklich nützlich. Wenn Sie wissen, dass ein Graph kreisfrei ist, verrät Ihnen das Zählen seiner Knoten und Kanten, aus wie vielen Teilen er besteht, ohne eine Suche auszuführen. Diese Identität steckt auch hinter der üblichen Union-Find -Invariante: Jede erfolgreiche Vereinigung verschmilzt zwei Komponenten und fügt eine Kante hinzu, also ist der laufende Zähler n - (bisherige Vereinigungen) zu jedem Zeitpunkt die Anzahl der Komponenten.

Eine Warnung. Die Identität setzt Kreisfreiheit voraus. Für einen allgemeinen Graphen gilt stets m ≥ n - k , mit Gleichheit genau dann, wenn der Graph ein Wald ist, ein Graph mit mehr als n - k Kanten enthält also zwangsläufig einen Kreis. Diese Ungleichung ist der schnellste Weg, zu beweisen, dass ein Graph einen Kreis hat, ohne ihn zu finden: Gilt m ≥ n, gibt es irgendwo einen Kreis.

5. Spannbäume

Ein Spannbaum eines zusammenhängenden Graphen G ist ein Teilgraph, der ein Baum ist und jeden Knoten von Genthält. Er ist das minimale Gerüst, das den Graphen in einem Stück hält.

Jeder zusammenhängende endliche Graph hat einen, und der konstruktive Beweis lohnt sich, weil er zugleich ein Algorithmus ist: Solange ein Kreis existiert, entfernen Sie irgendeine seiner Kanten. Das Entfernen einer Kreiskante kann den Graphen nicht zerlegen, da der Rest des Kreises ihre Endpunkte weiterhin verbindet, und das Verfahren endet, weil jeder Schritt eine Kante entfernt. Was übrig bleibt, ist zusammenhängend und kreisfrei. Gleichwertig und praktischer: Der Baum der Entdeckungskanten jeder BFS- oder DFS -Traversierung ist bereits ein Spannbaum, gefunden in O(n + m).

Drei Tatsachen über Spannbäume, die immer wieder auftauchen:

• Jeder Spannbaum hat genau n - 1 Kanten, egal wie der Graph aussah. Auf einem ungewichteten Graphen sind also alle Spannbäume gleichwertig, und das Problem des minimalen Spannbaums wird erst interessant, wenn Kanten Gewichtetragen.
• Die Anzahl der Spannbäume kann enorm sein. Der vollständige Graph Kn hat nn-2 davon, und das ist wieder Cayleys Formel , von der Seite der Spannbäume aus gesehen.
• Ein Baum ist sein eigener einziger Spannbaum. Offensichtlich, sobald man es ausspricht, und ein nützlicher Grenzfall zum Testen von Code: Jeder Spannbaumzähler sollte auf einem Baum genau 1 liefern, was die Matrix-Baum-Rechnung in Abschnitt 8 für das durchgehende Beispiel bestätigt.

Für unendliche Graphen ist die Aussage „jeder zusammenhängende Graph hat einen Spannbaum“ weiterhin wahr, braucht aber das Auswahlaxiom und ist sogar äquivalent dazu. Diese Grenze wird im Leitfaden zu endlichen und unendlichen Graphen behandelt.

6. Beschriftete Bäume zählen: Cayleys Formel

Wie viele verschiedene Bäume lassen sich auf einer festen Menge von n beschrifteten Knoten bauen? Die Antwort ist eines der zitierfähigsten Ergebnisse der Kombinatorik, 1889 von Arthur Cayley veröffentlicht.

Cayleys Formel. Die Anzahl der beschrifteten Bäume mit n Knoten ist nn-2.

Die ersten Werte wachsen schnell, und es lohnt sich, sie anzusehen, denn die kleinsten lassen sich von Hand prüfen:

Die Werte für n = 4 und n = 5 oben sind nicht aus einem Buch zitiert; sie entstanden durch Aufzählen jeder Teilmenge von n - 1 Kanten aus den C(n, 2) Kandidaten und Behalten der zusammenhängenden, was genau 16 und 125 ergibt.

Ein Wort dazu, was „beschriftet“ bedeutet, denn die Unterscheidung ist das ganze Thema von Abschnitt 9. Cayley zählt Bäume, deren Knoten unterscheidbar sind, also sind der Pfad 1 - 2 - 3 und der Pfad 2 - 1 - 3 verschiedene Bäume, obwohl sie dieselbe Form haben. Entfernt man die Beschriftungen, gibt es auf drei Knoten nur eine Baumform.

Es gibt mehrere Beweise der Formel, darunter ein Argument durch doppeltes Abzählen auf gewurzelten Wäldern und ein Determinantenargument über den Matrix-Baum-Satz. Am erhellendsten ist eine Bijektion, und sie ist kurz genug, um sie vollständig durchzurechnen.

7. Die Prüfer-Bijektion, vollständig durchgerechnet

Heinz Prüfer gab 1918 einen Beweis von Cayleys Formel, indem er eine explizite Bijektion zwischen beschrifteten Bäumen mit n Knoten und Folgen der Länge n - 2 über {1, …, n}konstruierte. Da es genau nn-2 solche Folgen gibt, folgt die Formel sofort.

Kodierung. Solange mehr als zwei Knoten übrig sind, suchen Sie das Blatt mit der kleinsten Beschriftung, notieren die Beschriftung seines einzigen Nachbarn und entfernen das Blatt. Hören Sie auf, wenn zwei Knoten übrig sind. Am durchgehenden Beispiel ergibt das Schritt für Schritt:

Blatt 1 entfernen  →  3 notieren      übrig: 2,3,4,5,6,7,8
Blatt 2 entfernen  →  3 notieren      übrig: 3,4,5,6,7,8
Blatt 3 entfernen  →  4 notieren      übrig: 4,5,6,7,8
Blatt 4 entfernen  →  5 notieren      übrig: 5,6,7,8
Blatt 6 entfernen  →  5 notieren      übrig: 5,7,8
Blatt 5 entfernen  →  7 notieren      übrig: 7,8

Prüfer-Folge:  (3, 3, 4, 5, 5, 7)        Länge 6 = n - 2

Dekodierung. Die Umkehrung führt dieselbe Idee rückwärts aus. Geben Sie jedem Knoten einen Zähler, der eins plus der Anzahl seiner Vorkommen in der Folge entspricht; das wird sein Grad. Nehmen Sie dann wiederholt den kleinsten noch unbenutzten Knoten mit Zähler 1, verbinden ihn mit dem ersten verbleibenden Eintrag der Folge und verringern beide Zähler. Ist die Folge aufgebraucht, verbinden Sie die beiden Knoten, die noch einen Zähler von 1 haben. Wendet man das auf (3, 3, 4, 5, 5, 7) an, erhält man genau die ursprüngliche Kantenmenge zurück, und das macht die Zuordnung zu einer Bijektion statt bloß zu einer Zusammenfassung.

Die mit Abstand nützlichste Eigenschaft der Kodierung ist diese:

Knoten v kommt in der Prüfer-Folge genau deg(v) - 1 -mal vor. Insbesondere sind die Blätter genau die Beschriftungen, die nie vorkommen.

Prüfen Sie es am durchgehenden Beispiel. Knoten 3 hat Grad 3 und kommt zweimal vor; Knoten 5 hat Grad 3 und kommt zweimal vor; die Knoten 4 und 7 haben Grad 2 und kommen je einmal vor; und die Blätter 1, 2, 6 und 8 kommen gar nicht vor. Diese Entsprechung verwandelt Fragen über Gradfolgen in Fragen darüber, wie oft Symbole in einer Zeichenkette vorkommen, und deshalb sind Prüfer-Folgen das Standardwerkzeug, um Bäume mit vorgegebenen Graden zu zählen und einen beschrifteten Baum gleichverteilt zufällig zu ziehen: Erzeugen Sie eine zufällige Folge der Länge n - 2 und dekodieren Sie sie.

8. Der Matrix-Baum-Satz

Cayleys Formel zählt die Spannbäume des vollständigen Graphen. Kirchhoffs Matrix-Baum-Satz, der ihr um vier Jahrzehnte vorausgeht und 1847 aus seiner Arbeit über elektrische Netzwerke hervorging, zählt die Spannbäume jedes Graphen.

Bilden Sie die Laplace -Matrix L = D - A, wobei D die Diagonalmatrix der Grade und A die Adjazenzmatrix ist. Dann gilt:

Matrix-Baum-Satz. Streichen Sie eine beliebige Zeile und die zugehörige Spalte aus L. Die Determinante der verbleibenden (n-1) × (n-1) -Matrix ist die Anzahl der Spannbäume des Graphen. Welche Zeile und Spalte man streicht, spielt keine Rolle.

Drei Rechnungen machen den Satz greifbar, und alle drei wurden durchgeführt statt zitiert:

Den Kreisfall sollte man als Intuition festhalten: Ein Kreis mit k Knoten hat genau k Spannbäume, einen für jede Kante, die man weglässt. Der Satz erklärt auch eine Bemerkung aus dem Leitfaden zu Multigraphen: Parallele Kanten verändern die Anzahl der Spannbäume tatsächlich, weil sie als Vielfachheiten außerhalb der Diagonale in die Laplace-Matrix eingehen, zwei durch zwei parallele Kanten verbundene Knoten haben also zwei Spannbäume statt einem.

9. Unbeschriftete Bäume: eine viel schwerere Frage

Cayleys Formel ist sauber, weil Beschriftungen Bäume leicht unterscheidbar machen. Fragen Sie stattdessen, wie viele Bäume es bis auf Isomorphiegibt, also wie viele verschiedene Formen existieren, und das Problem wird wirklich schwer.

Die beiden Spalten erzählen völlig verschiedene Geschichten. Die beschriftete Anzahl hat eine einzeilige geschlossene Form, die unbeschriftete keine. Es ist keine Formel für die Anzahl der Bäume mit n Knoten bis auf Isomorphie bekannt, nur eine Behandlung über erzeugende Funktionen und ein asymptotisches Ergebnis von Richard Otter aus dem Jahr 1948, das zeigt, dass die Anzahl wie C · αn n-5/2 wächst, mit numerisch bestimmten Konstanten.

Der Grund für die Lücke ist Symmetrie. Die beschriftete Anzahl durch n! zu teilen, wäre nur richtig, wenn jeder Baum eine triviale Automorphismengruppe hätte, und die meisten haben das nicht: Ein Pfad lässt sich spiegeln, die Blätter eines Sterns lassen sich beliebig permutieren, und jede Symmetrie bedeutet, dass mehrere Beschriftungen auf dieselbe Form zusammenfallen. Bahnen unter der symmetrischen Gruppe zu zählen, ist genau der schwierige Teil, und deshalb braucht das Problem Pólyas Abzähltheorie statt einer Formel.

Für Praktiker ist die praktische Form dieser Unterscheidung der Isomorphietest für Bäume: die Entscheidung, ob zwei Bäume dieselbe Form haben. Anders als allgemeine Graphisomorphie ist das in linearer Zeit lösbar, indem man jeden Teilbaum von den Blättern aufwärts kanonisch hasht und die Ergebnisse am Zentrum vergleicht. Dass das allgemeine Problem schwer und der Baumfall leicht ist, ist ein weiteres Beispiel für das Muster, das sich durch diesen ganzen Artikel zieht.

10. Zentrum, Radius und Durchmesser

Die Exzentrizität eines Knotens ist sein größter Abstand zu irgendeinem anderen Knoten. Der Radius ist die kleinste Exzentrizität im Graphen, der Durchmesser die größte, und das Zentrum ist die Menge der Knoten, die den Radius annehmen. Bei Bäumen verhalten sich diese Größen ungewöhnlich sauber, zuerst von Camille Jordan 1869 herausgearbeitet.

Satz von Jordan. Das Zentrum eines Baums besteht entweder aus einem Knoten oder aus zwei benachbarten Knoten.

Nie aus drei, nie aus zwei nicht benachbarten. Vergleichen Sie das mit einem Kreis, bei dem jeder Knoten im Zentrum liegt, und die Schärfe des Baumfalls wird deutlich.

Der Beweis ist zugleich der Algorithmus. Entfernen Sie wiederholt alle aktuellen Blätter gleichzeitig. Jede solche Runde verringert die Exzentrizität jedes verbleibenden Knotens um genau 1, erhält also, welche Knoten minimal sind, und das Verfahren endet mit einem oder zwei übrigen Knoten. Am durchgehenden Beispiel:

Start                    1 2 3 4 5 6 7 8
Blätter 1, 2, 6, 8 abschälen   →   übrig  3 4 5 7
Blätter 3, 7 abschälen         →   übrig  4 5      ← das Zentrum

Exzentrizitäten   1:5  2:5  3:4  4:3  5:3  6:4  7:4  8:5
Radius 3     Durchmesser 5     Zentrum {4, 5}, benachbart, wie Jordan verlangt

Das Ergebnis des Blattabschälens wurde mit einer direkten Berechnung aller acht Exzentrizitäten abgeglichen, und beide stimmen genau überein: Die Knoten minimaler Exzentrizität sind genau 4 und 5. Der Algorithmus läuft in O(n), und deshalb ist er der übliche Weg, einen Baum „in der Mitte“ zu wurzeln, etwa vor dem kanonischen Hashen beim Isomorphietest.

Eine weitere Identität gilt in Bäumen und ist es wert, sie sich zu merken:

Radius = ⌈Durchmesser / 2⌉        hier: 3 = ⌈5 / 2⌉

Sie folgt, weil der Durchmesser eines Baums durch einen eindeutigen Pfad realisiert wird und das Zentrum in der Mitte dieses Pfades liegt. In einem allgemeinen Graphen gilt nur die schwächere Ungleichung radius ≤ diameter ≤ 2 · radius .

11. Abstände in Bäumen und der Doppel-BFS-Trick

Weil es zwischen je zwei Knoten genau einen Pfad gibt, sind Abstände in einem Baum einfacher als in jeder anderen Graphenklasse. Es gibt nichts zu optimieren: Der eindeutige Pfad ist der kürzeste Pfad, man braucht also keine Gewichte, keine Prioritätswarteschlange und kein Dijkstra, um ihn zu finden.

Diese Eindeutigkeit liefert einen eleganten und weit verbreiteten Algorithmus für den Durchmesser:

Doppel-BFS. Starten Sie eine Breitensuche von einem beliebigen Knoten, und sei a ein am weitesten entfernter gefundener Knoten. Starten Sie eine zweite Suche von a aus, und sei b ein von dort am weitesten entfernter Knoten. Dann ist der Pfad von a nach b ein Durchmesser, und dist(a, b) ist die Länge des Durchmessers.

Zwei lineare Durchläufe, keine Gewichte, keine Raffinesse. Am durchgehenden Beispiel erreicht die Suche ab Knoten 1 den Knoten 8 als am weitesten entfernten Knoten, und eine zweite Suche ab 8 liefert Knoten 1 im Abstand 5, was mit dem wahren Durchmesser übereinstimmt, der als Maximum über alle Exzentrizitäten berechnet wurde.

Warum das funktioniert, sollte man klar sagen, denn der Trick versagt auf allgemeinen Graphen, und trotzdem wird er dorthin übertragen. Die entscheidende Behauptung ist, dass ein am weitesten entfernter Knoten von jedem Startpunkt aus stets ein Endpunkt eines Durchmessers ist. In einem Baum gilt das, weil die eindeutigen Pfade den am weitesten entfernten Knoten an das Ende des längsten Pfades zwingen; in einem Graphen mit Kreisen ist die Behauptung schlicht falsch, und das Zwei-Durchlauf-Verfahren kann einen zu kleinen Wert liefern. Auf einem allgemeinen Graphen braucht die Durchmesserberechnung die Abstände zwischen allen Paaren.

Einige weitere Abstandstatsachen, die in Bäumen gelten und im Allgemeinen nirgends sonst:

• Das Entfernen einer beliebigen Kante zerlegt den Baum in genau zwei Komponenten, da jede Kante eine Brücke ist. Genau das lässt Teile-und-herrsche-Verfahren auf Bäumen, etwa die Centroid-Zerlegung, so sauber funktionieren.
• Der Pfad zwischen zwei Knoten lässt sich allein aus Elternzeigern rekonstruieren, sobald der Baum gewurzelt ist, in einer Zeit proportional zur Pfadlänge, und darauf beruhen die Techniken für den tiefsten gemeinsamen Vorfahren.
• Abstände erfüllen die Vier-Punkte-Bedingung, eine metrische Identität, die genau die Abstandsmatrizen charakterisiert, die von Bäumen stammen, und die Grundlage der Rekonstruktion phylogenetischer Bäume aus genetischen Abstandsdaten ist.

12. Freie, gewurzelte und geordnete Bäume

Bisher ging es um freie Bäume: zusammenhängende kreisfreie Graphen ohne ausgezeichneten Knoten und ohne Reihenfolge unter den Nachbarn eines Knotens. Die Informatik arbeitet fast immer mit etwas Strukturierterem, und Knuths The Art of Computer Programming trennt die drei Ebenen sorgfältig, denn die Anzahlen unterscheiden sich auf jeder.

Das Wurzeln ist keine Änderung am Graphen, sondern eine Änderung der Fragestellung. Die zugrunde liegende Kantenmenge ist identisch; was eine Wurzel hinzufügt, ist eine Richtung und damit das ganze Vokabular von Elternknoten, Kind, Vorfahr, Nachfahr, Tiefe und Höhe, das der begleitende Leitfaden zu gewurzelten Bäumen zusammen mit den Standard-Traversierungen ausführlich behandelt.

Der Unterschied bei den Anzahlen ist der deutlichste Beleg dafür, dass es wirklich verschiedene Objekte sind. Geordnete Binärbäume mit n Knoten werden durch die Catalan-Zahlen gezählt, was 1, 1, 2, 5, 14, 42 für n = 0 bis 5 ergibt, während freie Bäume mit derselben Knotenzahl weit weniger sind. Jedes zusätzliche Stück Struktur, auf dem man besteht, vervielfacht die Anzahl verschiedener Objekte.

Ein praktischer Hinweis, der aus Abschnitt 10folgt: Wenn ein Algorithmus eine Wurzel braucht und keine vorgegeben ist, ist das Wurzeln am Zentrum meist der richtige Standard. Es minimiert die Höhe, und die begrenzt die Tiefe jeder Rekursion, die Sie über den Baum laufen lassen.

13. Wo Bäume in der Informatik vorkommen

Bäume sind die häufigste Struktur in der Informatik, die wirklich ein Graph ist, und es lohnt sich, die Fälle, in denen der Baum die Daten sind, von denen zu trennen, in denen er ein Zertifikat ist, das ein Algorithmus erzeugt.

Bäume als Daten. Die Hierarchie ist der Zweck:

• Dateisysteme. Verzeichnisse und Dateien bilden einen gewurzelten Baum, zumindest bis symbolische und harte Links erlaubt sind; dann wird daraus ein allgemeiner Graph, und die Garantie eines eindeutigen Pfades geht verloren. Genau deshalb bringen Link-Schleifen naive Verzeichnisdurchläufe zum Absturz.
• Syntaxbäume und abstrakte Syntaxbäume. Jedes Compiler-Frontend erzeugt einen. Dass es ein Baum ist, macht die rekursive Auswertung wohlfundiert: Ein Teilausdruck kann sich nicht selbst enthalten.
• Das DOM. Ein HTML-Dokument ist ein geordneter gewurzelter Baum, und CSS-Selektoren sind Abfragen über Vorfahren- und Geschwisterbeziehungen darin.
• Suchbäume, Tries und Heaps. Binäre Suchbäume, B-Bäume und Tries sind Bäume, deren Form beschränkt wird, um die Tiefe zu begrenzen, und die ist genau die Höhe des gewurzelten Baums.
• Entscheidungsbäume. Jeder innere Knoten prüft ein Merkmal, und jedes Blatt trägt eine Vorhersage; der eindeutige Pfad von der Wurzel zum Blatt ist die Erklärung der Modellausgabe.

Bäume als Zertifikate. Hier ist der Baum die Ausgabe eines Algorithmus und kodiert einen Beweis:

• BFS- und DFS-Bäume. Jede Traversierung eines zusammenhängenden Graphen erzeugt einen Spannbaum aus Entdeckungskanten. Der BFS-Baum bescheinigt zusätzlich kürzeste Abstände in einem ungewichteten Graphen, und die Rückwärtskanten des DFS-Baums sind es, mit denen man Kreise erkennt und Brücken findet.
• Kürzeste-Wege-Bäume. Der Dijkstra-Algorithmus liefert einen: einen Spannbaum, in dem der Pfad von der Quelle zu jedem Knoten ein kürzester Pfad ist. Beachten Sie, dass er im Allgemeinen kein minimaler Spannbaum ist, und die beiden zu verwechseln, ist ein klassischer Fehler.
• Minimale Spannbäume. Kruskal, Prim und Borůvka bescheinigen jeweils den billigsten verbindenden Teilgraphen, behandelt im MST-Leitfaden.
• Union-Find-Wälder. Die Datenstruktur für disjunkte Mengen ist buchstäblich ein Wald, und Pfadkompression ist eine Operation, die seine Bäume abflacht, um die Höhe nahezu konstant zu halten.
• Merkle-Bäume. Hash-Bäume in Versionsverwaltung und verteilten Systemen nutzen die Eigenschaft des eindeutigen Pfades, sodass sich die Änderung eines einzigen Blatts entlang genau eines Pfades bis zur Wurzel fortpflanzt, was die Verifikation logarithmisch macht.

Eine Klarstellung lohnt sich, weil die Terminologie in die Irre führt: Eine Git-Commit-Historie ist kein Baum. Ein Merge-Commit hat zwei Eltern, die Historie ist also ein gerichteter azyklischer Graph. Gits „tree“-Objekte sind etwas völlig anderes, nämlich die Verzeichnisschnappschüsse. Der Unterschied zwischen einem DAG und einem Baum ist genau der, dass ein Baum einen eindeutigen Pfad zwischen je zwei Knoten hat, und ein Merge zerstört das.

14. Häufige Fehler

• Nur eine Hälfte der Definition prüfen. „Zusammenhängend“ allein lässt Kreise zu; „n - 1 Kanten“ allein lässt ein Dreieck plus einen isolierten Knoten zu. Sie brauchen ein Paar von Bedingungen aus dem Satz in Abschnitt 2, und zusammenhängend plus n - 1 Kanten ist das billigste.
• Annehmen, ein Kürzeste-Wege-Baum sei ein minimaler Spannbaum. Sie optimieren Verschiedenes: Der eine minimiert jeden Abstand von der Quelle, der andere das Gesamtgewicht der Kanten. Sie unterscheiden sich häufig.
• Den Doppel-BFS-Trick für den Durchmesser auf einem Graphen mit Kreisen verwenden. Er gilt nur auf Bäumen, wo die Eigenschaft des eindeutigen Pfades einen am weitesten entfernten Knoten zum Endpunkt eines Durchmessers macht. Auf allgemeinen Graphen kann er stillschweigend zu klein schätzen.
• Beschriftete und unbeschriftete Anzahlen verwechseln. Es gibt 125 beschriftete Bäume mit 5 Knoten und nur 3 Formen. Die Division durch n! rechnet nicht zwischen ihnen um, weil Bäume Symmetrien haben.
• Vergessen, dass das Wurzeln strukturell nichts ändert. Eine Wurzel fügt eine Frage hinzu, keine Kante. Der zugrunde liegende freie Baum bleibt unverändert, jede für freie Bäume bewiesene strukturelle Tatsache gilt also weiterhin.
• Das Blattlemma bei unendlichen Bäumen erwarten. Der beidseitig unendliche Pfad ist kreisfrei und zusammenhängend und hat überhaupt kein Blatt.
• Einen DAG wie einen Baum behandeln. Ein DAG kann mehrere Pfade zwischen zwei Knoten haben; ein Baum nicht. Jeder Algorithmus, der sich auf die Eindeutigkeit von Pfaden verlässt, einschließlich naiver Memoisierung mit einem Knoten als Schlüssel, verhält sich dann falsch.
• Einen „Baum“ bauen, der einen Kreis enthält. Die schnellste Laufzeitprüfung ist die Kantenzahl: Wenn ein angeblicher Baum mit n Knoten nicht genau n - 1 Kanten hat, halten Sie an und suchen Sie den Fehler.

15. Glossar

17. Quellen

Quellen für die Definitionen, Sätze und Zuschreibungen oben, zusammen mit den Standardwerken, in denen dieses Material entwickelt wird, in chronologischer Reihenfolge aufgeführt.

1. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 bis 508. Der Matrix-Baum-Satz.
2. Jordan, C. (1869). "Sur les assemblages de lignes." Journal für die reine und angewandte Mathematik 70, 185 bis 190. Das Zentrum eines Baums ist ein Knoten oder zwei benachbarte Knoten.
3. Cayley, A. (1889). "A Theorem on Trees." Quarterly Journal of Pure and Applied Mathematics 23, 376 bis 378.
4. Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen." Archiv der Mathematik und Physik 27, 142 bis 144. Die Bijektion aus Abschnitt 7.
5. Borůvka, O. (1926). "O jistém problému minimálním." Práce Moravské Přírodovědecké Společnosti 3, 37 bis 58.
6. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
7. Otter, R. (1948). "The Number of Trees." Annals of Mathematics 49(3), 583 bis 599. Asymptotik für unbeschriftete Bäume.
8. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1), 48 bis 50.
9. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6), 1389 bis 1401.
10. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley.
11. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3. Auflage, Abschnitt 2.3. Reading, Massachusetts: Addison-Wesley. Die Unterscheidung zwischen freien, gewurzelten und geordneten Bäumen.
12. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall. Kapitel 2 entwickelt Bäume und Abstände.
13. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press.
15. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Abschnitt 1.5 behandelt Bäume und Wälder.