Selbstkomplementäre Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe 4. Sei G ein einfacher Graph. Zeigen Sie:
1. Ist G nicht zusammenhangend, so ist [mm] \overline{G} [/mm] zusammenhangend.
2. P3 und C5 sind selbstkomplementar.
3. Jeder selbstkomplementäre einfache Graph ist zusammenhangend |
Hi, ich würde gerne mal Fragen ob meine Überlegungen(besonders Aufgabenteil 3) richtig sind.
1) Betrachte man zwei Knoten x,y in G die keine Kante verbindet -> in [mm] \overline{G} [/mm] gibt es eine Kante.
2.Fall betrachte x,y in G die in G mit einer Kante verbunden sind. So gibt es ein z in G, sodass es keinen x,z Weg in G gibt(dieses y existiert, weil wenn es nicht existieren würde wäre G zusammenhängend). Dann kann es in G auch keinen z,y Weg geben(denn gäbe es einen, so gäbe es auch einen x,z-Weg, da x und y über eine Kante verbunden sind). Da es diese beiden Wege in G nicht gibt, gibt es sie im Komplement [mm] \overline{G} \Box
[/mm]
2. Kann man aufzeichnen und dann den passenden Isomorphismus aufschreiben.
3. Hier bin ich mir nicht sicher: Angenommen es gäbe einen selbstkomplementären Graphen S, der nicht zusammenhängend ist. Dann folgt aus Teilaufgabe 1, dass dann das Komplement [mm] \overline{S} [/mm] zusammenhängend ist. und das steht ja im Widerspruch dazu, dass ich einen geeigneten Isomorphismus finden kann, der den Nichtweg aus S in [mm] \overline{S} [/mm] abbilden kann.
Reicht das an Begründung?
|
|
| |
|
> Aufgabe 4. Sei G ein einfacher Graph. Zeigen Sie:
> 1. Ist G nicht zusammenhängend, so ist [mm]\overline{G}[/mm]
> zusammenhängend.
> 2. P3 und C5 sind selbstkomplementär.
> 3. Jeder selbstkomplementäre einfache Graph ist
> zusammenhängend
Hallo,
teile uns doch bitte auch noch mit, was denn
genau mit [mm] \overline{G} [/mm] gemeint ist (wenn G gegeben),
was P3 und C5 bedeuten sollen und was mit
"selbstkomplementär" gemeint ist.
Einige wissen das vielleicht, aber bestimmt
nicht alle, und auch ich müsste zuerst nach
Definitionen suchen.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:08 Do 26.12.2013 | | Autor: | MeineKekse |
Def 1.So Als Komplementgraph, komplementären Graph oder Komplement bezeichnet man in der Graphentheorie einen speziellen Graphen, den man aus einem gegebenen Graphen erhält.
Dabei besitzt der komplementäre Graph die gleichen Knoten wie Ursprungsgraph, unterscheidet sich aber in seinen Kanten: Der Komplementgraph besitzt genau die Kanten, die der Ursprungsgraph nicht hat. Der Komplementgraph eines gegebenen Graphen G wird häufig auch mit [mm] \overline{G} [/mm] bezeichnet.
Def 2.Als selbstkomplementär bezeichnet man Graphen, die isomorph zu ihrem komplementären Graphen sind.
Def 3. P3 ist der Pfad der Länge 3, C5 der Kreis der Länge 5(bezogen auf die Kantenzahl)
|
|
|
| |
|
> Aufgabe 4. Sei G ein einfacher Graph. Zeigen Sie:
> 1. Ist G nicht zusammenhängend, so ist [mm]\overline{G}[/mm]
> zusammenhängend.
> 2. P3 und C5 sind selbstkomplementär.
> 3. Jeder selbstkomplementäre einfache Graph ist
> zusammenhängend
> Hi, ich würde gerne mal Fragen ob meine
> Überlegungen(besonders Aufgabenteil 3) richtig sind.
> 1) Betrachte man zwei Knoten x,y in G die keine Kante
> verbindet -> in [mm]\overline{G}[/mm] gibt es eine Kante. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> 2.Fall betrachte x,y in G die in G mit einer Kante
> verbunden sind. So gibt es ein z in G, sodass es keinen x,z
> Weg in G gibt(dieses y existiert, weil wenn es nicht
> existieren würde wäre G zusammenhängend). Dann kann es
> in G auch keinen z,y Weg geben(denn gäbe es einen, so
> gäbe es auch einen x,z-Weg, da x und y über eine Kante
> verbunden sind). Da es diese beiden Wege in G nicht gibt,
> gibt es sie im Komplement [mm]\overline{G} \Box[/mm]
Gut argumentiert !
> 2. Kann man aufzeichnen und dann den passenden
> Isomorphismus aufschreiben.
Klar.
> 3. Hier bin ich mir nicht sicher: Angenommen es gäbe einen
> selbstkomplementären Graphen S, der nicht zusammenhängend
> ist. Dann folgt aus Teilaufgabe 1, dass dann das Komplement
> [mm]\overline{S}[/mm] zusammenhängend ist. und das steht ja im
> Widerspruch dazu, dass ich einen geeigneten Isomorphismus
> finden kann, der den Nichtweg aus S in [mm]\overline{S}[/mm]
> abbilden kann. ![[haee]](/images/smileys/haee.gif "[haee]")
>
> Reicht das an Begründung?
Was verstehst du denn unter einem "Nichtweg" ??
Ich denke mal, dass du ohne diesen undefinierten Begriff
auskommen solltest.
Das Wesentliche für den Beweis ist doch wohl die Fest-
stellung (die allenfalls noch kurz zu erläutern wäre),
dass das Komplement des Komplements eines Graphen G
wieder dieser ursprüngliche Graph G ist. Dann ergibt
sich der Rest des Beweises aus der unter (1.) gezeigten
Aussage.
Man kann dann ganz leicht zeigen, dass die Annahme,
dass G selbstkomplementär und unzusammenhängend
wäre, zu einem Widerspruch führt, denn ein unzusammen-
hängender und ein zusammenhängender Graph können
ja nicht isomorph sein.
LG , Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:45 Do 26.12.2013 | | Autor: | MeineKekse |
> > 3. Hier bin ich mir nicht sicher: Angenommen es gäbe einen
> > selbstkomplementären Graphen S, der nicht zusammenhängend
> > ist. Dann folgt aus Teilaufgabe 1, dass dann das Komplement
> > [mm]\overline{S}[/mm] zusammenhängend ist. und das steht ja im
> > Widerspruch dazu, dass ich einen geeigneten Isomorphismus
> > finden kann, der den Nichtweg aus S in [mm]\overline{S}[/mm]
> > abbilden kann.
> Man kann dann ganz leicht zeigen, dass die Annahme,
> dass G selbstkomplementär und unzusammenhängend
> wäre, zu einem Widerspruch führt, denn ein unzusammen-
> hängender und ein zusammenhängender Graph können
> ja nicht isomorph sein.
Super danke für deine Hilfe, das habe ich versucht mit dem "Nichtweg auszudrücken". Ich wollte damit sagen, dass ich in einem nicht zusammenhängendem Graphen ja zwischen mindestens zwei x,y eV keinen Weg in G habe(einen "Nichtweg") und im Komplement nach Aufgabenteil a) dieser Weg ja in [mm] \overline{G} [/mm] exisitiert, sodass ich deswegen keinen Isomorphismus finden kann :)
|
|
|
|
