Kantenanzahl < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:46 Do 11.06.2009 | | Autor: | eppi1981 |
| Aufgabe | Sei G = [mm] (E,K,\phi) [/mm] ein schlichter Graph mit |E| = n Knoten, der aus m paarweise disjunkten Untergraphen [mm] G_{j} [/mm] = [mm] (E_{j}, K_{j}, \phi|_{K_{j}}) [/mm] für j =1,...,m besetzt.
Zeigen Sie, dass für die Menge K der Kanten des Graphen G die folgende Abschätzung gilt:
[mm] |K|\le\bruch{(n-m)(n-m+1)}{2}
[/mm]
|
kann mir jemanden helfen. Ich habe keinen Ahnung, wie ich das zeigen kann, aber habe eine kleine Idee, dass das mit einem Induktionsbeweis gezeigt werden kann.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:55 Do 11.06.2009 | | Autor: | M.Rex |
Hallo
Addiere die Anzahl der Kanten der Untergraphen [mm] G_{j} [/mm] mal auf, und benutze die Summenformel [mm] 1+2+3+\ldots+k=\bruch{k(k+1)}{2}
[/mm]
Beachte aber noch, dass an jedem Knoten mindestens zwei Kanten anliegen (Schlichter Graph)
Kommst du damit erstmal weiter?
Marius
|
|
|
| |
|
Leider kann ich nicht weiter :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Sa 13.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
