Menge der Kreise in Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:33 Di 19.12.2006 | | Autor: | CranHead |
| Aufgabe | Die Menge der Kreise in einem vollständigen Graphen [mm] K_{n} [/mm] sei [mm] \summe_{k=3}^{n} \vektor{n \\ k}*\bruch{(k-1)!}{2}
[/mm]
Vergewissern Sie sich, dass die Formel stimmt. |
Ich wollte einfach mal damit anfangen, für die ersten vollständigen Graphen für n=3 und n=4 die Kreismenge abzuzählen. Bei n=3 war das trivial, aber bei n=4 komme ich einfach nicht auf 13. Könnte mir da jemand helfen, zum Beispiel mit den Kreisen im vollständigen Graphen für n=4? Das würde meinem Verständnis bestimmt helfen.
Vielen Dank
|
|
| |
|
Hallo,
der [mm] K_4 [/mm] hat
- [mm] \frac{3!}{2}=3 [/mm] Kreise der Länge 4 (halte Knoten 1 fest und betrachte dann alle Permutationen der
Knoten 2,3,4, allerdings liefern jeweils a,b,c und b,c,a denselben Kreis, nicht wahr ?
- [mm] \vektor{4//3}\cdot \frac{3!}{2} [/mm] Kreise der Länge 3 (Argument wie oben)
und somit 3+ [mm] 4\cdot [/mm] 3=15 Kreise,
die Formel liefert Dir diesem Wert, und sie macht ja genau das, was ich hier für n=4 beschrieben habe.
Gruss,
Mathias
|
|
|
|
