Es fällt mir schwer, dies richtig zu beschreiben, daher werde ich nur so viele Details wie möglich angeben und hoffentlich weiß jemand, was ich zu tun versuche = -)
Ich versuche, zwei Knotenbäume zu vergleichen, um festzustellen, wie ähnlich / unterschiedlich sie strukturell sind. In den folgenden Diagrammen haben beide Beispiele die gleiche Anzahl von Kindern, Enkelkindern usw. In Beispiel 1 hat Root ein Kind mit zwei Kindern, in Beispiel zwei jedoch nicht.
Ich könnte wahrscheinlich herausfinden, wie man rekursiv durchläuft und zählt, wie viele von jeder Ebene es gibt, und das vergleichen, um mir eine Vorstellung davon zu geben, wie ähnlich die Bäume sind in der Tat sind sie nicht.
Weiß jemand davon? Oder auch was ist der Fachbegriff für was das ist?
Bearbeiten: Dies ist auch in C # und ich verwende Listen, um diese Objekte und ihre Kinder zu speichern.
Beispiel 1
Beispiel 2
quelle
Antworten:
Was Sie suchen, ist Rooted Tree Isomorphism, eine spezielle Version des Graph Isomorphism , mit Ausnahme von Bäumen und festem Wurzelknoten.
Die Erklärung in dieser Zuweisung verwendet zwei Eigenschaften:
Arbeiten Sie sich mit diesen beiden Eigenschaften von den Blättern bis zur Wurzel vor und kennzeichnen Sie jeden Knoten mit der Anzahl der Kinder in lexikografischer Reihenfolge. Zum Beispiel wird Ihre Wurzel in Beispiel 1 mit (0, 0, (0, 1)) bezeichnet - sie hat drei Kinder, die erste / zweite hat 0 Kinder und die dritte hat 2 Kinder, die 0 bzw. 1 Kinder haben. Schließlich vergleichen Sie einfach die Stammbezeichnungen, um festzustellen, ob die Bäume gleich sind.
Ich habe diese Art von Thema nicht gemacht und ich habe dieses Papier erst vor ein paar Minuten gelesen, daher kann ich nicht für seine Richtigkeit bürgen. hoffe es hilft trotzdem.
quelle
Das Problem zu sehen, ob zwei Graphen logisch gleich sind, heißt Graph Isomorphishm .
Beachten Sie, dass das allgemeine Graph-Isomorphismus-Problem in NP besteht. Für diesen speziellen Fall gibt es jedoch möglicherweise eine Abkürzung. Ich bin mir nicht sicher, da es logisch erscheint, zu prüfen, ob die Unterschiede gleich sind, um sie zu kennen.
quelle