Bäume und lexikographische Ordnung

Meine Einschätzung:

Sei ein Baum definiert als kreisloser, zusammenhängender Graph. Dann gilt:

Wenn die Zweige lexikographisch sortiert sind, dann handelt es sich um einen Baum.

Wenn die Zweige NICHT lexikographisch sortiert sind, dann handelt es sich möglicherweise, aber nicht notwendigerweise um einen Baum.

Folgende Beispiele verwenden die <-Relation auf den natürlichen Zahlen als lexikographische Ordnung.

Beispiel 1: Wurzel 42 hat genau ein Kind 1789 und dieses genau ein Kind 1066. Die Zweige sind NICHT lexikographisch sortiert, aber es handelt sich um einen Baum (kreisloser, zusammenhängender Graph).

Beispiel 2: Wurzel 42 hat genau ein Kind 1789 und dieses genau ein Kind 42. Die Zweige sind NICHT lexikographisch sortiert und es handelt sich NICHT um einen Baum, weil ein Kreis vorhanden ist.

Liebe Grüße

Nein, da gibt es nichts zu diskutieren. Ein Baum ist komplett lexikografisch sortiert, alles andere ist kein Baum, sondern ein Wurzelbaum (wenn nur die Wurzel lexikografisch nicht passt), ein gepflanzter Baum ohne jegliche lexikografische Ordnung, oder gar kein Baum. Die Aussagen von lecturio sind diesbezüglich nicht ganz korrekt. Wenn du dir die unzähligen Klausurbeispiele ansiehst, wirst du das bestätigt sehen.

kompi wrote:

Nein, da gibt es nichts zu diskutieren..

Hier sind ja auch Beweise oder Widerlegungen gefragt und keine Diskussionen.

kompi wrote:

Ein Baum ist komplett lexikografisch sortiert, alles andere ist kein Baum, sondern ein Wurzelbaum (wenn nur die Wurzel lexikografisch nicht passt), ein gepflanzter Baum ohne jegliche lexikografische Ordnung, oder gar kein Baum

Warum? Bitte beweisen. Beginne bei der Definition: "Ein Baum ist definiert als zusammehängender kreisloser Graph." Ein Wurzelbaum ist insbesondere ein Baum.

Liebe Grüße

für Definitionen brauchst du doch nur im Skript nachlesen...oder in den unzähligen anderen Quellen.

Jeder Baum ist auch ein Wurzelbaum und gepflanzter Baum. Jeder Wurzelbaum ist auch ein geplanzter Baum. Umgekehrt ist das nicht so.

Baum: vollständig lexikografisch geordnet.
Wurzelbaum: Definierte Wurzel, Rest lexikografisch geordnet.
gepflanzter Baum: wohlgeklammert, nciht sortiert, definierte Wurzel

Ein Wurzelbaum ist insbesondere ein Baum.

Nein, denn ein Wurzelbaum hat eine definierte Wurzel, ein Baum hat aber eine lexikografisch korrekte Wurzel. Wenn ein Wurzelbaum eine lexikografische Wurzel hat, ist er ein Baum und _auch_ ein Wurzelbaum und gepflanzter Baum.

Ich denke wir reden insofern aneinander vorbei, Chrissi, als dass ich bei "Baum" von einem Baumcode spreche, und du von einem kreisfreien Graphen. Irgendwie sind die Begriffe doppelt besetzt. In diesem Zusammenhang ist aber die Begrifflichkeit im Sinne eines Baumcodes gemeint. Bäume, also kreisfreie Graphen, sind es natürlich alle, das ist aber hier nicht gefragt. Ein korrekter "Baum"-code ist lexikografisch vollständig geordnet.

btw: Die Lecturio-VO's zu Algo halte ich nicht für besonders prickelnd. Gerade auch bei obiger Thematik sind sie verwirrend, tw. widersprüchlich und schlecht recherchiert.

MfG,
kompi

Danke für eure Antworten!
Da steh ich nun ich armer Thor und bin so dumm als wie zuvor ;)
Könnt ihr irgendwelche Quellen angeben, die euren Standpunkt bestätigen?
Danke und Gruß
Fini

Fini, wenn du die videos hast, dann hast du auch die folien. Schau dir den Algorithmus auf Seite 112/193 an (zur VO3).

kompi,
ja, ich habe die Folien und den Algorithmus habe ich mir auf meinen "Spickzettel" geschrieben. Mein Problem ist, dass dieser Algorithmus (scheinbar?) etlichen Musterlösungen von Klausuren widerspricht, was mich sehr verunsichert

Hmm, er entspricht eigentlich genau dem, was ich oben geschrieben habe. Vielleicht interpretierst du ihn an irgendeiner Stelle falsch? Ansonsten halte dich da dran:

Baum: vollständig lexikografisch geordnet.
Wurzelbaum: Definierte Wurzel, Rest lexikografisch geordnet.
gepflanzter Baum: wohlgeklammert, (nicht sortiert, definierte Wurzel)

kompi wrote:

Baum: vollständig lexikografisch geordnet.\

Die zweite Verzweigung im Algorithmus ist "Zweige lexikographisch geordnet?"
Wählt man hier "nein", kommt man zur Verzweigung "Richtiger Zentrumsknoten ist Wurzel?". Wählt man hier "ja", handelt es sich laut Algorithmus um einen "Baum".
Und dieser ist NICHT lexikographisch geordnet.
Was interpretiere ich hier falsch? Danke schon mal

@fini:
Ich habe den Zettel jetzt nicht zur Hand (und benutze ihn auch nicht). Wenn das da wirklich so steht, ist der Algo schlichtweg falsch.

Nochmal: Wenn die Teilbäume alle lexikografisch geordnet sind und auch der lexikografisch richtige Knoten das Zentrum bildet, ist es ein Baumcode. Ist der Code der Teilbäume lexikografisch geordnet, aber das Zentrum nicht das eigentlich lexikografisch richtige, es es ein Wurzelbaumcode. Ist gar nichts geordnet, aber der Code zumindest wohlgeklammert, ist es ein gepflanzter Baumcode.

Das alles ist zwingend abwärtskompatibel, aber nicht zwingend aufwärtskompatibel.

Danke, daran werde ich mich halten, da das auch den Musterlösungen aus den bisherigen Klausuren entspricht. Obwohl ich immer noch nicht verstehe, warum in allen anderen Quellen (div. Bücher, Internet), die ich gefunden habe, als Definition für einen Baum lediglich steht, dass es sich um einen zusammenhängenden und kreisfreien Grafen handelt...

Fini1984 wrote:

Danke, daran werde ich mich halten, da das auch den Musterlösungen aus den bisherigen Klausuren entspricht. Obwohl ich immer noch nicht verstehe, warum in allen anderen Quellen (div. Bücher, Internet), die ich gefunden habe, als Definition für einen Baum lediglich steht, dass es sich um einen zusammenhängenden und kreisfreien Grafen handelt...

...weil das ja auch so ist. Wir reden hier nicht von Baum im Sinne von kreisfreier Graph, sondern von Baumcodes zum Vergleich von Isomorphievarianten. Es ist letztlich ein Problem der Begrifflichkeiten und deren doppelter Verwendung.

Viel Glück für morgen. Ich hau jetzt den Hut drauf, irgendwann reichts auch wieder