Graphentheorie: Anzahl Graphen mit best. Eigenschaften |
| 05.11.2014, 16:06 | R'lyeh | Auf diesen Beitrag antworten » |
| Graphentheorie: Anzahl Graphen mit best. Eigenschaften Zeige: Die Anzahl der bis auf Isomorphie verschiedenen, ungerichteten, 2-regulären Graphen mit n Knoten ist Meine Ideen: Hallo, Jungs und Mädels! Dies ist die komplette Aufgabenstellung. Mein Problem ist - was ist das P mit den zwei Indizes? Eine Matrix? Ich kenne das P nur aus dem Zusammenhang mit dem Warshall-Algorithmus (Berechnung der transitiven Hülle eines Graphen), aber dieser wird ja auf einen konkreten Graphen angewandt, nicht auf eine Anzahl von Graphen. Weiß jemand Rat? An sich habe ich mir schon überlegt, dass die genannten Graphen (bis auf Isomorphie verschieden, ungerichtet, 2-regulär) ja immer Kreise sind bzw. aus mehreren Kreis-Komponenten bestehen. D.h., Graphen mit 1 oder 2 Knoten existieren in der Form nicht, da sich kein Kreis bilden lässt. Graphen mit 3, 4 und 5 Knoten lassen sich nur als Graphen mit einer Komponente darstellen. Graphen mit 6, 7 und 8 Knoten lassen sich entweder als eine Komponente oder als zwei (3+3, 3+4, 4+4 Knoten) Komponenten darstellen, und so weiter. Die oben genannte Formel wäre also (meines, zugegebenermaßen flüchtigen, Erachtens) schon für erfüllt. Leider weiß ich nicht, wie ich meine Beweisführung fortsetzen soll, wenn ich die Bedeutung des Ps nicht kenne 
Vielleicht hat ja jemand ne Idee. Danke im Voraus! |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
