Finden nicht-isomorpher Bäume

Neue Frage »

ChrisL1988 Auf diesen Beitrag antworten »
Finden nicht-isomorpher Bäume
Hallo Leute,

ich hoffe der Titel des Themas ist richtig gewählt, aber ich habe die Aufgabenstellung, dass ich bis auf auf Isomorphie jene 11 Bäume mit 7 Knoten finden soll.

Die Aufgabe beinhaltet auch noch folgenden Hinweis:
Man mache eine Unterscheidung der Bäume hinsichtlich ihrer Knotengrade. Da jeder Baum mit 7 Knoten genau 6 Kanten besitzt, müssen den 7 Knoten positive Grade so zugeordnet werden, dass ihre Gesamtsumme gerade 12 ist. Jeder solchen Zuordnung entsprechen dann ein oder mehrere Bäume, z.B. der Zuordnung 6,1,1,1,1,1,1 ein „Stern“ mit dem Knoten vom Grad 6 in der Mitte.



Im Internet beweisen verschiedene Vorlesungsunterlagen tatsächlich, dass es zu n = 7 genau 11 nicht-isomorphe Bäume gibt (http://cvpr.uni-muenster.de/teaching/ss0...script/DS06.pdf - Seite 42).

Nun ist meine Frage, ob ich diese 11 Bäume durch reines "Ausprobieren" finde oder ob es eine Art Algorithmus oder Anleitung für das Finden solcher Bäume gibt. Was ist mit dem Hinweis? Kann ich an Hand der Zuordnung (wie etwa 6,1,1,1,1,1,1) des Knotengrades etwa eine Anleitung finden?

Bin für jeden Tipp oder Hinweis dankbar,
liebe Grüße
Christoph
Mystic Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Du solltest zuerst enmal alle Möglichkeiten hinschreiben, wie man 12 als Summe von 7 positiven ganzen Zahlen absteigend geordnet schreiben kann... Dein Beispiel 6+1+1+1+1+1+1=12 war schon mal eine dieser Möglichkeiten und dafür gibt es auch nur eine Realisierung, eben den "Stern"... Im allg. gibt es aber mehr als nur eine Möglichkeit für einen Baum mit den dadurch festgelegten Knotengraden...
ChrisL1988 Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Zitat:
Original von Mystic
Du solltest zuerst enmal alle Möglichkeiten hinschreiben, wie man 12 als Summe von 7 positiven ganzen Zahlen schreiben kann... Dein Beispiel 6+1+1+1+1+1+1=12 war schon mal eine dieser Möglichkeiten und dafür gibt es auch nur eine Realisierung, eben den "Stern"... Im allg. gibt es aber mehr als nur eine Möglichkeit für einen Baum mit den dadurch festgelegten Knotengraden...


Nagut dann start ich einmal damit. Und dafür gibt es genau 11 Möglichkeiten?

6+1+1+1+1+1+1

5+2+1+1+1+1+1
4+3+1+1+1+1+1

Wäre folgendes das gleiche wie letzteres?
3+4+1+1+1+1+1


4+2+2+1+1+1+1
3+2+2+2+1+1+1
2+2+2+2+2+1+1

Irgendwie verliere (zumindest) ich den Überblick. Gibt es hier keine Stütze, z.b. die nächste Stelle inkrementieren, etc.?


EDIT: Habe gesehen du hast deinen Beitrag editiert und "absteigend" hinzugefügt. Das habe ich teilweise versucht, aber geht mir nicht ganz auf.

6+1+1+1+1+1+1
5+2+1+1+1+1+1
4+2+2+1+1+1+1
3+4+2+1+1+1+1
3+3+2+1+1+1+1
3+2+2+2+1+1+1
2+2+2+2+2+1+1


Danke im Voraus und lg Christoph
ChrisL1988 Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Sorry, Doppelpost
Mystic Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Hm, eine Summendarstellung, welche mit 3+3+... beginnt, hast du tatsächlich unterwegs irgendwie verloren... Und ich dachte, das wäre der einfachste Teil der Aufgabe, wo man mit einfachem Probieren noch leicht durchkommt...

Und ja, das mit "absteigend geordnet" hab ich oben noch reineditiert, sonst gäb's ja viel mehr Summendarstellungen... Augenzwinkern

Edit: Sorry, hat sich mit deinem Edit überkreuzt... Ja, jetzt stimmt's... Freude
ChrisL1988 Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Zitat:
Original von Mystic
Hm, eine Summendarstellung, welche mit 3+3+... beginnt, hast du tatsächlich unterwegs irgendwie verloren... Und ich dachte, das wäre der einfachste Teil der Aufgabe, wo man mit einfachem Probieren noch leicht durchkommt...

Und ja, das mit "absteigend geordnet" hab ich oben noch reineditiert, sonst gäb's ja viel mehr Summendarstellungen... Augenzwinkern

Edit: Sorry, hat sich mit deinem Edit überkreuzt... Ja, jetzt stimmt's... Freude


Man sollte nicht zuviel editieren, wenn man gleichzeitig online ist Big Laugh

So, wie gesagt ich stehe bei folgendem Ergebnis:

6+1+1+1+1+1+1
5+2+1+1+1+1+1
4+2+2+1+1+1+1
3+4+1+1+1+1+1
3+3+2+1+1+1+1
3+2+2+2+1+1+1
2+2+2+2+2+1+1

Das sind jedoch lediglich 7 der 11 möglichen Bäume. Wie komme ich auf die anderen? Sind verschiedenen Anordnung der Zahlen erlaubt? Irgendwie klingt die Aufgabe nach dem Suchen total easy, ich tue mir aber seltsamerweise irrsinnig schwer unglücklich

Danke im Voraus smile
 
 
Mystic Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Zitat:
Original von ChrisL1988
Das sind jedoch lediglich 7 der 11 möglichen Bäume. Wie komme ich auf die anderen? Sind verschiedenen Anordnung der Zahlen erlaubt? Irgendwie klingt die Aufgabe nach dem Suchen total easy, ich tue mir aber seltsamerweise irrsinnig schwer unglücklich

Hm, irgendwie hast du diesen Satz

Zitat:
Original von Mystic
Im allg. gibt es aber mehr als nur eine Möglichkeit für einen Baum mit den dadurch festgelegten Knotengraden...

aus meinem allerersten Posting hier entweder überlesen oder nicht verstanden... Ja, unter diesen 7 Möglichkeiten, 12 als Summe von absteigend geordneten positiven ganzen Zahlen zu schreiben, gibt es einige mit mehr als nur einer Realisierung als Baum mit diesen Knotengraden (stets aber mindestens einer!) ...
ChrisL1988 Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Zitat:
Original von Mystic
Zitat:
Original von ChrisL1988
Das sind jedoch lediglich 7 der 11 möglichen Bäume. Wie komme ich auf die anderen? Sind verschiedenen Anordnung der Zahlen erlaubt? Irgendwie klingt die Aufgabe nach dem Suchen total easy, ich tue mir aber seltsamerweise irrsinnig schwer unglücklich

Hm, irgendwie hast du diesen Satz

Zitat:
Original von Mystic
Im allg. gibt es aber mehr als nur eine Möglichkeit für einen Baum mit den dadurch festgelegten Knotengraden...

aus meinem allerersten Posting hier entweder überlesen oder nicht verstanden... Ja, unter diesen 7 Möglichkeiten, 12 als Summe von absteigend geordneten positiven ganzen Zahlen zu schreiben, gibt es einige mit mehr als nur einer Realisierung als Baum mit diesen Knotengraden (stets aber mindestens einer!) ...


Um ehrlich zu sein, habe ich es anfangs nicht ganz verstanden.
Habe nun eine Übersicht mit 11 Bäumen unter den 7 verschiedenen Summenmöglichkeiten erstellt.

Vielleicht nimmt sich irgendwer die 5 Minuten und würde das überprüfen.
Besten Dank im Voraus und lg
Christoph
Mystic Auf diesen Beitrag antworten »
RE: Finden nicht-isomorpher Bäume
Ja, hab's jetzt nur überflogen, aber dürfte stimmen... Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »