matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieSelbstkomplementäre Graphen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Graphentheorie" - Selbstkomplementäre Graphen
Selbstkomplementäre Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Selbstkomplementäre Graphen: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 13:30 Mi 25.12.2013
Autor: MeineKekse

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?


        
Bezug
Selbstkomplementäre Graphen: Definitionen ?
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:18 Mi 25.12.2013
Autor: Al-Chwarizmi


> 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.


Bezug
                
Bezug
Selbstkomplementäre Graphen: Ergänzung
Status: (Mitteilung) Reaktion unnötig Status 
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)


Bezug
        
Bezug
Selbstkomplementäre Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 17:35 Do 26.12.2013
Autor: Al-Chwarizmi


> 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]
>  
> 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]    [ok]

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]
>
> 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


  


Bezug
                
Bezug
Selbstkomplementäre Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.   [haee]

>  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 :)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 1h 03m 1. Teekanne3d
UAnaR1FolgReih/Potenzreiehenentwicklung
Status vor 2h 26m 15. Al-Chwarizmi
IntTheo/Flächenmaß berechnen
Status vor 5h 18m 3. leduart
z-transformation/z transformation und dann?
Status vor 8h 30m 4. leduart
Algebra/Gleichung auflösen
Status vor 9h 37m 7. Tipsi
UAnaR1FunkInt/Faltungen abschätzen
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]