Bäume Isomorphie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wieviele Bäume mit 6 Ecken gibt es bis auf Isomorphie? Zeichnen Sie die Bäume (für jeden Isomophietyp genau einen). Wie groß ist jeweils der Durchmesser? |
Hallo Leute,
ich hab mal ein bisschen nachgedacht über diese Aufgabe und da ist mir was aufgefallen: Verschieden Bäume mit derselben Anzahl en Ecken (bzw. Knoten) bedeutet ja, das sich der Grad der Ecken ändert. Aber die Summe der Gradzahlen ändert sich nicht. Beispielsweise bei 4, da haben die Knoten der Bäume folgende Gradzahlen: a) 1, 2, 2, 1, b) 3, 1, 1, 1. Das ergibt jeweils 6 zusammen. Dasselbe Spiel mit 5, da haben die Gradzahlen alle 8: a) 1, 2, 2, 2, 1, b)1, 3, 1, 2, 1, c) 3, 1, 1, 1, 1. Was auffällt, ist das man daraus eine Zahlpartition machen kann.
Also die Anzahl der Bäume mit 6 Ecken ist: [mm] P_{2 * (6 - 1), 6}
[/mm]
Allgemein: [mm] P_{2 * (n - 1), n}.
[/mm]
Was meint ihr dazu? Und was ist mit dem Durchmesser gemeint?
|
|
| |
|
> Wieviele Bäume mit 6 Ecken gibt es bis auf Isomorphie?
> Zeichnen Sie die Bäume (für jeden Isomophietyp genau
> einen). Wie groß ist jeweils der Durchmesser?
> Hallo Leute,
>
> ich hab mal ein bisschen nachgedacht über diese Aufgabe
> und da ist mir was aufgefallen: Verschieden Bäume mit
> derselben Anzahl en Ecken (bzw. Knoten) bedeutet ja, das
> sich der Grad der Ecken ändert. Aber die Summe der
> Gradzahlen ändert sich nicht. Beispielsweise bei 4, da
> haben die Knoten der Bäume folgende Gradzahlen: a) 1, 2,
> 2, 1, b) 3, 1, 1, 1. Das ergibt jeweils 6 zusammen.
> Dasselbe Spiel mit 5, da haben die Gradzahlen alle 8: a) 1,
> 2, 2, 2, 1, b)1, 3, 1, 2, 1, c) 3, 1, 1, 1, 1. Was
> auffällt, ist das man daraus eine Zahlpartition machen
> kann.
>
> Also die Anzahl der Bäume mit 6 Ecken ist: [mm]P_{2 * (6 - 1), 6}[/mm]
>
> Allgemein: [mm]P_{2 * (n - 1), n}.[/mm]
>
> Was meint ihr dazu? Und was ist mit dem Durchmesser
> gemeint?
Hallo bluepeople12,
die Idee mit den Zahlpartitionen (wie sie den einzelnen
Isomorphieklassen zugeordnet werden sollen) ist mir
nicht recht klar. Das solltest du am besten an einem
Beispiel (dem vorliegenden mit 6 Ecken) zeigen.
Ich verstehe auch nicht, was genau du mit [mm] P_{k,n}
[/mm]
bezeichnest. Es kann wohl nicht dasselbe sein wie da:
![[]](/images/popup.gif) Partitionsfunktion
Mit dem Durchmesser eines Baums ist bestimmt die Länge
(Anzahl Kanten) des längsten möglichen Pfades im Baum
gemeint. Der Durchmesser eines Baumes mit 6 Knoten
kann die Werte von 2 bis 5 annehmen.
LG Al-Chw.
|
|
|
| |
|
Nein, die Zahlpartition [mm] P_{n, k} [/mm] teilt eine Zahl n in k Summanden.
Beispielsweise ich hab 6 Ecken. Die Summe aller Grade ist 10. Wie z.B. in diesem Bild hier im Anhang.
10 = 1 + 2 + 2 + 2 + 2 + 1
Man kann aber die 6 Summanden auch anders aufteilen:
10 = 1 + 3 + 1 + 2 + 2 + 1
10 = 1 + 3 + 1 + 3 + 1 + 1
10 = 1 + 4 + 1 + 2 + 1 + 1
10 = 1 + 5 + 1 + 1 + 1 + 1
Die Summanden sind dann nur die Grade der Ecken im Baum.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
Ich muss da einen Fehler gemacht haben beim Denken über die Aufgabe, denn ich habe nur fünf verschieden Möglichkeiten gefunden, einen Baum mit 6 Knoten zu zeichnen, laut Definition der Zahlpartition
[mm] P_{n,k} [/mm] = [mm] \summe_{j=1}^{k}P_{n-k,j}
[/mm]
und meinem Vorschlag die Zahlpartitionen anzuwenden wären es 12.
|
|
|
| |
|
> Ich muss da einen Fehler gemacht haben beim Denken über
> die Aufgabe, denn ich habe nur fünf verschieden
> Möglichkeiten gefunden, einen Baum mit 6 Knoten zu
> zeichnen, laut Definition der Zahlpartition
>
> [mm]P_{n,k}[/mm] = [mm]\summe_{j=1}^{k}P_{n-k,j}[/mm]
>
> und meinem Vorschlag die Zahlpartitionen anzuwenden wären
> es 12.
Hallo,
für 6 Knoten habe ich insgesamt 6 untereinander nicht
isomorphe Bäume gefunden:
[Dateianhang nicht öffentlich]
LG Al-Chw.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
> Nein, die Zahlpartition [mm]P_{n, k}[/mm] teilt eine Zahl n in k
> Summanden.
>
> Beispielsweise ich hab 6 Ecken. Die Summe aller Grade ist
> 10. Wie z.B. in diesem Bild hier im Anhang.
>
> 10 = 1 + 2 + 2 + 2 + 2 + 1
>
> Man kann aber die 6 Summanden auch anders aufteilen:
>
> 10 = 1 + 3 + 1 + 2 + 2 + 1
> 10 = 1 + 3 + 1 + 3 + 1 + 1
> 10 = 1 + 4 + 1 + 2 + 1 + 1
> 10 = 1 + 5 + 1 + 1 + 1 + 1
>
> Die Summanden sind dann nur die Grade der Ecken im Baum.
Was du mit [mm] P_{n,k} [/mm] genau meinst, ist nach wie vor unklar.
Kannst du [mm] P_{n,k} [/mm] rechnerisch definieren ?
LG
|
|
|
|
