Mathematik online lernen im Mathe-Forum. Nachhilfe online
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

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Piepo

Piepo aktiv_icon

11:41 Uhr, 05.10.2021

Antworten
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."
Antwort
pwmeyer

pwmeyer aktiv_icon

11:50 Uhr, 05.10.2021

Antworten
Hallo,

fang einfach mal an, einen solchen Baum zu zeichnen.

Nimm mal den Fall, dass eine Ecke, sagen wir die Ecke 1, den Grad 5 hat. Welche Möglichkeiten bleiben dann noch?

DAnn probier das mal mit einer Ecke, den den Grad 4 hat ...

Gruß pwm
Piepo

Piepo aktiv_icon

12:07 Uhr, 05.10.2021

Antworten
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

Unbenannt
Antwort
pwmeyer

pwmeyer aktiv_icon

12:15 Uhr, 05.10.2021

Antworten
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 10 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 1, sie hat 4 verschiedene Nachbarn, sagen wir 2,3,4,5. An einer muss die Ecke 6 hängen. Also ist also fixiert (bis auf Um-Nummerierung)

Gruß pwm
Frage beantwortet
Piepo

Piepo aktiv_icon

12:48 Uhr, 05.10.2021

Antworten
Vielen Dank für die gute Hilfe!
Antwort
HAL9000

HAL9000 aktiv_icon

13:35 Uhr, 05.10.2021

Antworten
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.