Finden isomorpher Bäume < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man zeige, dass es bis auf Isomorphie genau 11 Bäume mit 7 Knoten gibt. („Bis auf Isomorphie“ heißt in diesem Zusammenhang, dass zwischen Bäumen, die durch eine bloße Umbezeichnung der Knoten ineinander übergeführt werden können, nicht unterschieden wird.)
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. |
Hallo Leute,
grundsätzlich ist mir klar, wie ein Aufzählung nicht-isomorpher Bäum aussieht. Ich habe im Internet auch bereits alle nicht-isomoprhen Bäume von 7 Knoten gefunden. Meine Frage ist, wie ich auf diese nicht-isomorphen Bäume komme. Gibt es hier eine Regel? Oder hilft nur ausprobieren und die Grafiken zu vergleichen, um festzustellen, ob dieser Baum bereits vorhanden ist oder nicht.
Danke im Voraus und lg
Christoph
Anmerkung:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:13 Mi 11.04.2012 | | Autor: | Stoecki |
> Man zeige, dass es bis auf Isomorphie genau 11 Bäume mit 7
> Knoten gibt. („Bis auf Isomorphie“ heißt in diesem
> Zusammenhang, dass zwischen Bäumen, die durch eine bloße
> Umbezeichnung der Knoten ineinander übergeführt werden
> können, nicht unterschieden wird.)
> 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.
> Hallo Leute,
>
> grundsätzlich ist mir klar, wie ein Aufzählung
> nicht-isomorpher Bäum aussieht. Ich habe im Internet auch
> bereits alle nicht-isomoprhen Bäume von 7 Knoten gefunden.
> Meine Frage ist, wie ich auf diese nicht-isomorphen Bäume
> komme. Gibt es hier eine Regel? Oder hilft nur ausprobieren
> und die Grafiken zu vergleichen, um festzustellen, ob
> dieser Baum bereits vorhanden ist oder nicht.
>
die aufgabe lautet "zeigen sie...". es muss also bewiesen werden. du hast in der aufgabenstellung einen tipp bekommen, wie man das machen kann, nämlich indem du dir die knotengrade anschaust und dir überlegst wie viele möglichkeiten es gibt die knotengrade anzuordnen, damit die gesamtsumme genau 12 ist. abzüglich der isomorphen solltest du dann das ergebnis bekommen
> Danke im Voraus und lg
> Christoph
>
> Anmerkung:
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
gruß bernhard
|
|
|
|
