Finden nicht-isomorpher Bäume |
09.04.2012, 09:58 | ChrisL1988 | Auf diesen Beitrag antworten » | ||||||
Finden nicht-isomorpher Bäume 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 |
||||||||
09.04.2012, 10:44 | 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... |
||||||||
09.04.2012, 10:51 | ChrisL1988 | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume
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 |
||||||||
09.04.2012, 10:56 | ChrisL1988 | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume Sorry, Doppelpost |
||||||||
09.04.2012, 11:01 | 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... Edit: Sorry, hat sich mit deinem Edit überkreuzt... Ja, jetzt stimmt's... |
||||||||
09.04.2012, 11:07 | ChrisL1988 | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume
Man sollte nicht zuviel editieren, wenn man gleichzeitig online ist 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 Danke im Voraus |
||||||||
Anzeige | ||||||||
|
||||||||
09.04.2012, 11:15 | Mystic | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume
Hm, irgendwie hast du diesen Satz
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!) ... |
||||||||
09.04.2012, 11:42 | ChrisL1988 | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume
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 |
||||||||
09.04.2012, 11:58 | Mystic | Auf diesen Beitrag antworten » | ||||||
RE: Finden nicht-isomorpher Bäume Ja, hab's jetzt nur überflogen, aber dürfte stimmen... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |