Tree, Multitree oder DAG linearisiert hinschreiben

#1

Gegeben sei folgender (Multi-)tree:

      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?

#2

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.
1 Like
#3

Geeenial :clap: :raised_hands: :+1:

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 :smile: )

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 :smile: ), weiß ich das selbstverständlich auch nicht mehr… () für einen leeren Tree akzeptabel?

#4

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.

#5

Was bedeutet das?

#6

Das ein Element etwa den Aufbau (Bezeichner(…)) hat, wobei (…) nur dann geschrieben wird, wenn das Element Kindelemente hat.

#7

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

(a,b), (a,c), (a,d), (b,j), (j,k), (c,e), (c,f), (d,g), (d,h), (d,i)
umgekehrt
(b,a), (c,a), (d,a), …                                         (i,d)

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.

#8

Es sei ein DAG mit genau einem Wurzelelement gemeint… Also ein Tree.

Augf keinen Fall, in die Höhle des Löwen begebe ich mich nicht. :wink:

#9
  /---> 1 
 /        \
0          \
 \          v
  \--> 2 --> 3 --> 4

Eine “Wurzel”, ein DAG, aber kein Baum…

#10

Streicht das Wort DAG… Zack DAG… schon geschehen :wink: 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. :slight_smile:

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.)

#11

Gut, DAG ist gestrichen und wir bleiben beim Tree. Es gibt noch

Beispiel wäre ein 3-ary tree, dass es auch noch in den Varianten full, perfect und complete gäbe.

Zur Schreibweise sei noch hierauf verwiesen

Somit sieht die Variante im OP korrekt aus. a wäre nicht in Klammern zu setzen.

Wie hier unter Nested parentheses verlinkt sollte man auch das Newick Format beachten, dass noch verschiedene Variationen bereitstellt.