Alle vollst. Gr. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:12 Mi 26.10.2011 | | Autor: | clemenum |
| Aufgabe | | Man zeige, dass alle vollständigen Graphen [mm] $K_n$ [/mm] stets zusammenhängend sind. |
Es muss also definitionsgemäß gezeigt werden, dass der vollständige Graph G=(V,E) aus einer einzigen Äquivalenzklasse besteht. D.h., ich nehme mir einen ungerichteten Graphen her mit n Knoten und versuche zu zeigen, dass es zu je zwei beliebigen Knoten $v, w [mm] \in [/mm] V$ einen ungerichteten Weg in G gibt, wobei v Startknoten und w Endknoten ist.
Aber vollständig heißt doch gerade, dass es (in dem Fall) n Knoten gibt, welche paarweise miteinander verbunden sind, womit die Aussage schon gezeigt sein sollte...
Mein Problem ist, dass ich mir bei diesem anschaulichen Sachverhalt schwer tu, es in viele elementarere logische Schritte zu zerlegen...
Kann mir jemand helfen, meine Andeutung zu formalisieren?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:41 Mi 26.10.2011 | | Autor: | Blech |
Hi,
Du hast voll und ganz recht.
> Mein Problem ist, dass ich mir bei diesem anschaulichen Sachverhalt schwer tu, es in viele elementarere logische Schritte zu zerlegen...
z.z. [mm] $\forall\ [/mm] x, [mm] y\in [/mm] V$ (V ist Knotenmenge), gibt es einen ungerichteten Weg von x nach y
Beweis: [mm] $(x,y)\in [/mm] E$ (E Kantenmenge), da [mm] $K_n$ [/mm] vollständig.
ciao
Stefan
|
|
|
|
