Komplementgraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:59 Di 24.01.2006 | | Autor: | dump_0 |
Hallo.
Könnt ihr mal bitte schauen ob ich den folgenden Beweis richtig gemacht habe ?
Satz: Der Komplementgraph eines nicht zusammenhängenden Graphen ist stets zusammenhängend.
Beweis: Sei G ein nicht zusammenhängender Graph mit mehreren Zusammenhangskomponenten.
Sei nun [mm] \overline{G} [/mm] sein Komplementgraph, wobei [mm] \overline{G} [/mm] ebenfalls nicht zusammenhängend ist. Da in G mind. 2 Knoten x,y existieren für die {x,y} [mm] \notin [/mm] E gilt, muss es laut Def. von [mm] \overline{G} [/mm] in [mm] \overline{G} [/mm] eine Kante {x,y} [mm] \in \overline{E} [/mm] geben, was ein Widerspruch dazu ist das [mm] \overline{G} [/mm] nicht zusammenhängend ist. Das gilt für alle Knoten x,y [mm] \in [/mm] G für die keine Kante in G existiert.
Umgekehrt soll ich noch beweisen das der Komplementgraph eines zusammenhängenden Graphen stets nicht zusammenhängend ist.
Hier würde ich es analog machen.
Kann man das als Beweis hinnehmen ?
Grüße
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:30 Di 24.01.2006 | | Autor: | DaMenge |
Hi,
ich denke nicht, dass dein Beweis schon reicht, denn du zeigst nicht, warum alle Punkte im Komplementärgraph zusammenhängend sind.
(du kannst nicht für alle x,y fordern, dass die Kante dazwischen nicht in E liegt)
Du gehst also von der Existenz von zwei Punkten aus und willst dies auf alle verallgemeinern..
ich würde so vorgehen:
sei G nicht zusammenhängend.
für beliebige x,y aus V(G) gilt entweder:
1) es gibt keinen Weg von x nach y in G - dann ist aber die Kante {x,y} im Komplementärgraph
oder
2) es gibt einen Weg von x nach y - dann wähle man eine Ecke z aus einer anderen Zusammenhangskmponente, dann gibt es keine Wege von x nach z und z nach y, also liegen die Kanten {x,z} und {z,y} im Komplement..
in beiden Fällen sind x und y im Komplement verbunden (evtl über einen Umweg)
Die Umkehrung ist dann trivial durch einen Widerspruchsbeweis machbar..
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:00 Mi 25.01.2006 | | Autor: | dump_0 |
Danke für deine Antwort, habs jetzt so ähnlich gemacht wie du, mit Fallunterscheidung, ich denke das sollte dann reichen :)
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 17:01 So 24.04.2011 | | Autor: | Igor1 |
Hallo,
>
> Die Umkehrung ist dann trivial durch einen
> Widerspruchsbeweis machbar..
Ich habe keine Idee, wie man trivial die Umkehrung durch einen Widerspruchsbeweis zeigt.
z.z: G zusammenhängend [mm] \Rightarrow [/mm] G komplement
nichtzusammenhängend.
Angenommen G komplement wäre zusammenhängend . Warum muss dann G nichtzuammenhängend gewesen sein?
Gruss
Igor
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:21 Di 26.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 11:08 Mo 25.04.2011 | | Autor: | Igor1 |
Hallo,
im Datei-Anhang poste ich ein Beispiel, wo aus einem zusammenhängenden Graph ein komplementär zusammenhängender Graph entsteht.
![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang
Kann sowas überhaupt sein?
Gilt nicht, dass aus einem zusammenhängenden immer ein nichtzusammenhängender entsteht?
PS: Könnt ihr die Datei öffnen?
Gruss Igor
Dateianhänge:
Anhang Nr. 1 (Typ: jpg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Mi 27.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[a]](uploads/forum/00788040/forum-i00788040-n001.jpg "Dateianhänge"){kind=small}
Datei-Anhang