Meine Bäume sind verwurzelt und haben höchstens zwei Kinder an jedem Scheitelpunkt. Ich benötige Referenzen, die mir bei der Lösung einiger oder aller der folgenden Fragen helfen:
- Wie viele Isomorphismusklassen von Bäumen mit n Eckpunkten gibt es?
- Was sind die klassischen Algorithmen, um zu entscheiden, ob zwei gegebene Bäume isomorph sind?
- Gibt es einen schönen (berechenbaren?) Isomorphismus, der unveränderlich ist?
Natürlich können die Antworten von der Struktur abhängen, die zum Definieren der Bäume verwendet wird, aber ich denke, die richtige Wahl der Struktur ist Teil der Antwort, die ich suche.
algorithms
graph-theory
reference-request
combinatorics
trees
Rodrigo A. Pérez
quelle
quelle
Antworten:
Aufgrund von Aho, Hopcroft und Ullman gibt es einen klassischen linearen Zeitalgorithmus für den Wurzelbaumisomorphismus. Der Algorithmus verwendet tatsächlich eine einfache Isomorphismusinvariante. Siehe zum Beispiel Vorlesungsunterlagen von Vikram Sharma . Auf diese Weise können Sie den Isomorphismus unbewurzelter Bäume in linearer Zeit lösen, wie beispielsweise in Smals Folien beschrieben . Ein weiterer klassischer Algorithmus geht auf Buss zurück .
quelle