a
/ | \
/ | \
b c d
| | / | \
j | g h i
| |
k e-+-f
Frage: Wie schreibt man ihn linearisiert (“richtig, eindeutig und vollständig”) in nur einer Zeile hin?
Versuch: a(b(j(k)), c(e, f), d(g, h, i))
Sind runde Klammern richtig?
Müsste a auch in Klammern stehen?
Wie ist die wissenschaftliche Schreibweise?
Gibt es vielleicht einen Trick, das hinzuschreiben?
Die Kanten sind ungewichtet, könnte man auch einen gewichteten Graphen in der Schreibweise hinschreiben?
Das sieht nach einer Möglichkeit aus, die “richtig, eindeutig und vollständig” sein könnte.
Ob runde Klammern “richtig” sind, oder a in Klammern muss, ist eine Frage der Konvention. Mach’s so, wie’s in den Beispielen ist, die ihr sicher durchgenommen habt.
Wissenschaftlich? Pffft…
Eine Alternative könnte sein
a(b((j(k)))(c((e)(f)))(d((g)(h)(i))))
Dafür ist’s einfach: Baum traversieren (in-order). Beim runtergehen eine ( hinschreiben. Beim Hochgehen eine ) hinschreiben.
Erst mal freue ich mich, dass generell eine Antwort…
Dann… Die Alternative sieht ja furchtbar aus… Dann… Ich weiß leider nicht mehr, wie es in der Übung war… Ich hab ganz geistlich abgeschaltet, als das behandelt wurde, denn ich hatte das für gänzlich irrelevant eingestuft… (das darf niemand mitbekommen )
Darf ich also meine Schreibweise in jedem Fall hinschreiben, weil damit kein Informationsverlust einhergeht?
Blöd… Ich bräuchte noch eine Darstellung für einen leeren Tree, da ich gänzlich abgeschaltet hatte (wdh. mich ), weiß ich das selbstverständlich auch nicht mehr… () für einen leeren Tree akzeptabel?
Also wenn du das Root-Element (in deinem Falle also “(a(b(j(k)), c(e, f), d(g, h, i)))”) auch noch in Klammern setzt, ist () für einen leeren Tree durchaus legitim. Die Umschliessenden Klammern eines Elements gehören dann bereits zum Element - das hat zur Folge, dass jeder Tree mit einer öffnenden Klammer beginnt und ganz sicher auch wieder mit einer schließenden endet.
Möchte jetzt keine Spaßbremse sein, Tree ist jetzt ja kein Problem, aber ein DAG ist nicht Zwangsläufig immer ein Tree.
Dreh, das anfängliche Beispiel einfach mal auf den Kopf! Dann ist das immer noch ein DAG. Wie würdest du diesen aufschreiben?
Eine Lösung die mir Einfiele wäre
Damit ließe sich dann auch jede Art von Graph notieren, bei der jeder Knoten mindestens eine Kante besitzt. Insofern würde ich mich doch nochmal erkundigen, wie das mit der Hausaufgabe gemeint war.
Streicht das Wort DAG… ZackDAG… schon geschehen Wähle Tree respektive (Multi-)tree !
Wie heißt denn ein Baum, kein Binärbaum, mit 0 (1) bis 3 ausgehenden Kanten?
Und meine Frage hat sich doch schon erledigt… Man muss einfach nur die Abstände zwischen a (b), c und d groß genug wählen, damit man die anderen Knoten dazwischen quetschen kann.
Einer Prüfung liegt ja auch immer Schmierpapier bei. (Obwohl, ja es stimmt, greift man darauf zurück (also kann man nicht sofort Lösung hinschreiben) hat man die Uhr im Nacken.)
)
Wähle Tree respektive (Multi-)tree !