Anzahl der Möglichkeiten

Neue Frage »

11.12.2008, 16:55	prinzschleifer	Auf diesen Beitrag antworten »
Anzahl der Möglichkeiten Ich weiß, ich weiß, dies wird wieder eine Informatikfrage sein, dennoch bitte ich um hilfe: Ich hab die Aufgabe bekommen, alle möglichen gerichteten Bäume zu zeichnen, die genau vier Knoten haben und nicht Isomorph sind. Nun meine Frage: Über die Eigenschaft von Bäumen weiß ich nicht so viel. Sind Bäume schlingenfrei? Muss ein Baum mit einem Knoten anfangen? Muss er genau 2 "Kinder" haben? Bin auf Wikipedia auch nicht schlauer geworden.
11.12.2008, 17:46	Reksilat	Auf diesen Beitrag antworten »
RE: Anzahl der Möglichkeiten Man kann die Frage auch als Graphentheorie sehen, was ja ein Teilgebiet der Mathematik ist. Ein Baum ist natürlich schlingenfrei, genau so wird er normalerweise definiert. Ein gerichteter Baum ist dann einfach nur ein Baum, bei dem ich einen Knoten als Wurzel auszeichnen kann, so dass alle Kanten von ihm wegführen. Siehe auch: klick Die Anzahl der Kinder eines Knotens ist normalerweise nicht vorgegeben.
11.12.2008, 19:15	prinzschleifer	Auf diesen Beitrag antworten »
Also gibt es entweder Bäume die nur Weg von einen Knoten führen oder hin, also nicht beides Gleichzeitig?
11.12.2008, 20:23	prinzschleifer	Auf diesen Beitrag antworten »
Hab was in den Anhang geladen, spiegeln ist doch eine isomorphe Operation oder? Gibt es noch welche, oder seh ich mal wieder vor lauter Knoten den Graphen nicht?
11.12.2008, 20:37	Abakus	Auf diesen Beitrag antworten »
Ja, sieht gut aus . Du kannst spiegeln, es sei denn, du hast geordnete Bäume (d.h. es gibt eine definierte Reihenfolge bei den Kindern eines Knotens). Grüße Abakus
11.12.2008, 20:46	Reksilat	Auf diesen Beitrag antworten »
Kann man per Fallunterscheidung machen. Wurzel hat drei Kinder, Wurzel hat zwei Kinder, Wurzel hat ein Kind... Ja, sind dann alle. Spiegeln ist hier übrigens einfach nur die Identität, da es kein links, rechts, oben unten, was auch immer gibt. Ein Isomorphismus, bzw. Automorphismus bildet die Knotenmenge auf sich selbst ab, also müsste man die Knoten vorher bezeichnen. Der erste Graph hat sechs Automorphismen, der zweite und der vierte keinen und der dritte zwei. (Das nur so als Nebenbemerkung) Edit: Schon wieder vergessen abzusenden. Passiert mir öfter in letzter zeit :-(
Anzeige

11.12.2008, 21:00	prinzschleifer	Auf diesen Beitrag antworten »
Soweit so gut! Hier mein anliegen: wenn ich nun aber jeden Knoten eine Bezeichnung gebe, was ja nicht verkehrt ist, die Aufgabenstellung verbietet einem ja nur, dass man nie Bezeichnung nicht ändern darf! Wobei ich mir hier nicht sicher bin. Danke Reksilit und Abakus für die Hilfe. Ich bin mir aber immer noch sehr unschlüsslich wie ich die Aufgabenstellung zu interpretieren habe. Soll ich den nun alle Möglichkeiten beschreiben, also so wie bei mir im Anhang? Hier nochmal die Aufgabenstellung: Zeichnen Sie alle möglichen gerichteten Bäume mit genau vier Knoten, von denen keine zwei isomorph sind.
11.12.2008, 21:19	Reksilat	Auf diesen Beitrag antworten »
Das ist zwei mal der gleiche Graph, nur unterschiedlich numeriert. Die vier Graphen, die Du oben angegeben hast, reichen aus. Anders: Sei links der Graph A und rechts B, dann gibt es folgenden Isomorphismus $\begin{eqnarray} \varphi: A\rightarrow B \end{eqnarray}$ $\begin{eqnarray} \varphi(1_A)=1_B \end{eqnarray}$ $\begin{eqnarray} \varphi(2_A)=3_B \end{eqnarray}$ $\begin{eqnarray} \varphi(3_A)=4_B \end{eqnarray}$ $\begin{eqnarray} \varphi(4_A)=2_B \end{eqnarray}$ Also sind A und B isomorph. Gruß, Reksilat. (Mehr Scotch trinken!)
11.12.2008, 22:19	prinzschleifer	Auf diesen Beitrag antworten »
Gut, haben eine zweite Aufgabe bekommen, wo wir das ganze mit ungerichteten einem Graphen machen müssen und dieser soll 5 Knoten enhalten. Wäre dann meine Abbildung unten im Anhang isomorph? Ja, sage ich, weil man sie ja in einer Kette darstellen kann. Jede Wurzel hat maximal ein Kind. Ist das richtig so?
11.12.2008, 22:28	Reksilat	Auf diesen Beitrag antworten »
In einem ungerichteten Baum gibt es keine ausgezeichnete Wurzel, das wäre dann höchstens eine gewisse Betrachtungsweise dieses Graphen. Die beiden Graphen sind isomorph. "Jede Wurzel hat maximal ein Kind." In einem Baum kann man einen Knoten zur Wurzel machen. Das ist dann aber auch die einzige Wurzel im Baum.
11.12.2008, 22:57	prinzschleifer	Auf diesen Beitrag antworten »
Vielen, vielen dank! Also ich finde genau 3. Siehe Anhang. Also mit 5 ungerichteten Knoten. Richtig so?
11.12.2008, 23:02	Reksilat	Auf diesen Beitrag antworten »
Jo!

Neue Frage »

Antworten »

Anzahl der Möglichkeiten

Verwandte Themen