Chordale Komplemente < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
was ein chordaler Graph ist, ist mir sehr wohl bekannt. Was ist jedoch ein chordaler Komplement? Kann mir einer hierbei behilflich sein?
Vielleich würd eich es verstehen, wenn einer mir kurz erklären könnte, wie ein chordaler Komplement zu einem chordalen Graphen mit 4 Knoten (als Rechteck) aussieht, das Diagonal mit zwei Kanten verbunden ist ( Sehne).
Vielen Dank
|
|
| |
|
Das ist kein feststehender Begriff, sondern besagt, dass das Komplement eines Graphen eben chordal ist. Dazu muss der Graph nicht unbedingt selbst chordal sein. Sind Graph und Komplement beide chordal, nennt man den Graphen oft co-chordal.
Wenn Du auf Englisch googelst, findest Du mehr zu chordal complement.
|
|
|
| |
|
Das ist aber gerade das was ich nicht verstehe.
Ich habe auch schon auf englisch gegooglet.
Aber die Aussage, das ein das Komplement eines chordalen Graphen ebenfalls chordal sei, macht mich verrückt!
Du gibst mir doch recht, das ein Graph G mit 4 Knoten, als Rechteck, mit einer Diagonalen Kante, ein chordaler Graph ist oder?
Das Komplement zu diesem Graphen [mm] \overline{G} [/mm] würde doch so aussehen, das es nur noch die andere Diagonale Kante vorhanden ist.
Ursprünglich waren 5 Kanten vorhanden. Jetzt nur noch eine!
Ist das ein chordales Komplement?
Vermutlich nicht. Weil es kein Kreis mehr ist. Also wie kann das Komplement chordals sein?
Kannst du mir sagen, wie das chordale Komplement zu dem graphen G aussieht?
|
|
|
| |
|
Es gibt (Eindeutigkeit des Inversen!) i.a. nur ein Komplement zu einem Graphen. Das kann dann chordal sein oder nicht. Das Komplement zu dem von Dir beschriebenen Graphen ist nicht chordal. Hättest Du dieses Komplement aber vorliegen und würdest davon das Komplement bilden, erhieltest Du ja den ursprünglichen Graphen, und der wäre chordal...
|
|
|
| |
|
Ok, das bringt dann doch bisschen Licht ins dunkle 
Letzte Frage:
Wenn ein Graph G chordal ist, und das zughörige [mm] \overline{G} [/mm] nicht chordal sei (aber wie du sagtest, wenn ich das Komplement von [mm] \overline{G} [/mm] bilden würde, dann wäre der ursprüngliche Graph chordal) so ist [mm] \overline{G} [/mm] immer chordal?
Also es spielt doch keine Rolle ob der dargestellt Graph [mm] \overline{G} [/mm] chordal ist oder nicht. Da der ursprüngliche Graph chrodal ist, ist auch [mm] \overline{G} [/mm] immer chordal oder?
Vielen Dank für deine Hilfe
|
|
|
| |
|
Nein, es ist eine Besonderheit, wenn G und [mm] \overline{G} [/mm] beide chordal sind. Aus dem einen ist das andere nicht zu folgern, egal in welcher Richtung.
In dieser Notation bräuchte ich jetzt eine Doppellinie über dem G...
Darum wechsle ich einmal in eine andere Schreibweise: sei [mm] G^{-1} [/mm] das Komplement von G. Wenn G chordal ist, dann ist es [mm] (G^{-1})^{-1} [/mm] auch, weil ja [mm] G=(G^{-1})^{-1} [/mm] gilt.
Eine Aussage über [mm] G^{-1} [/mm] ist damit aber nicht getroffen und im allgemeinen auch nicht zu treffen.
|
|
|
|
