Zerlegung von Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:35 Mo 01.06.2009 | | Autor: | Kiki85 |
| Aufgabe | Beweise den Satz:
Wenn man den Graphen [mm] K_n [/mm] in vollständig bipartite Untergraphen [mm] H_1,...,H_m [/mm] zerlegt, dann ist m [mm] \ge [/mm] n-1 |
Die ist ein Satz aus dem Buch der Beweise. Mir liegt der Beweis also vor, allerdings versteh ich ihn nicht so ganz. Er lautet:
Sei die Eckenmenge von [mm] K_n [/mm] mit {1,...,n} bezeichnet, und seien [mm] L_j, R_j [/mm] die definierenden Eckenmengen der vollständig bipartiten Graphen [mm] H_j, [/mm] j=1,...,m. Jeder Ecke i ordnen wir eine Variable [mm] x_i [/mm] zu. Da [mm] H_1,...,H_m [/mm] eine Zerlegung des [mm] K_n [/mm] bilden, haben wir:
[mm] \summe_{i
Nun nehmen wir an, dass der Satz falsch ist, m<n-1. Dann hat das LGS
[mm] x_1+...+x_n=0,
[/mm]
[mm] \summe_{a\in\ L_k} x_a=0 [/mm] (k=1,...,m)
weniger Gleichungen als Variablen also gibt es eine nichttriviale Lösung
[mm] c_1,...,c_n. [/mm] Aus (1) schließen wir
[mm] \summe_{i
aber dies impliziert
[mm] 0=(c_1+...+c_n)² [/mm] = [mm] \summe_{i=1}^{n}c_i²+2\summe_{i0
[/mm]
also ein Widerspruch der den Beweis abschließt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Fragen lauten nun:
1. Was genau bedeutet egtl. [mm] \summe_{i
2. Wie komme ich überhaupt auf das LGS und wie habe ich die 2 Zeilen zu verstehen? Ich meine ich habe doch sowieso nur 2 Gleichungen und jede Menge Variablen. Was versteh ich da nicht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Mi 03.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
