 |
 |
 |
 |
 |
 |
Startseite » Forum » Bäume mit Eckenmenge und min Grad Ecken
Bäume mit Eckenmenge und min Grad Ecken
Universität / Fachhochschule
Graphentheorie
Tags: Baum, Graphentheorie
 
|
  |
|---|
|
Moin, ich habe heute folgende Frage zu Bäumen: Wieviele Bäume mit Eckenmenge {1, 2, 3, 4, 5, 6} gibt es, die eine Ecke vom Grad mindestens 4 haben? (Ergebnis in Dezimaldarstellung angeben.) Meine Idee wäre gewesen die Klassen der Isomorphen Bäume mit Ecken von mind. Grad 4 zu zählen. Da ich das Prinzip Isomorphieklassen aufzustellen und zu zählen noch nicht ganz verinnerlicht habe, wäre ich für ein bisschen Hilfe sehr dankbar. Es kann natürlich auch sein, dass meine Idee Schwachsinn ist. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, fang einfach mal an, einen solchen Baum zu zeichnen. Nimm mal den Fall, dass eine Ecke, sagen wir die Ecke den Grad 5 hat. Welche Möglichkeiten bleiben dann noch? DAnn probier das mal mit einer Ecke, den den Grad 4 hat . Gruß pwm |
 |
|
Erst mal danke für die Hilfe. Besonders viele Möglichkeiten sind es ja nicht... aber muss ich die 6 Möglichkeiten meine Ecke von Grad 5 aufzuteilen alle zählen oder ist das eine Möglichkeit, weil es der selbe Baum ist? Und wenn ich Ecke 1 als Grad 4 wähle und z.B. eine Kante zwischen 1 und 2 ziehe und Ecke 6 an 2 anhänge, bzw das Selbe mit Ecke 3, sind es dann die selben Bäume? (Siehe Bild) Danke  |
|
|
|
Hallo, es ist jeweils (bis auf Isomorphie) nur ein Graph. Du weißt, dass ein Baum mit 6 Ecken 5 Kanten hat und die Summe der Eckengerade ist. Daraus folgt zum Beispiel, dass es höchstens eine Ecke mit Grad 4 geben kann (ist natürlich auch aus der Skizze klar). Also nennen wir diese Ecke sie hat 4 verschiedene Nachbarn, sagen wir . An einer muss die Ecke 6 hängen. Also ist also fixiert (bis auf Um-Nummerierung) Gruß pwm |
 |
|
Vielen Dank für die gute Hilfe! |
|
|
|
Die Aufgabenstellung würde ich aber schon so deuten, dass wirklich alle Bäume zu zählen sind, also nicht nur "bis auf Isomorphie" heruntergebrochen. Und da kommt man dann schon auf 6+120 = 126 Bäume. |
1542118
1542105