Komplementärgraphen: Ein Graph wird selbstkomplementär genannt ...

Question

Aufgabe: Komplementärgraphen

Ein Graph \( G \) wird selbstkomplementär genannt, wenn \( G \) isomorph zu seinem Komplementärgraphen \( \bar{G} \) ist.

a) Entscheiden Sie für die nachfolgend abgebildeten Graphen, ob sie selbstkomplementär sind oder nicht. Positive Antworten sind durch Beschreibung eines Isomorphismus zu begründen, negative Antworten durch Argumente, warum \( G \) und \( \bar{G} \) nicht isomorph sein können.

b) Zeigen Sie, dass es keine selbstkomplementären Graphen mit 6 Knoten gibt.

Answer 1

Aufgabe a) ist recht trivial:

Nein

Ja

Nein

Ja

Nein

 

Bei Aufgabe b)  bin ich mir nicht sicher, ob die Begründung ausreicht:

Da ein Graph nur selbstkomplementär ist, wenn er genau halb so viele Kanten hat, wie der vollständige Graph (sonst würde entweder beim Graphen oder beim Komplement ein Überhang sein), kann man zeigen, dass ein Graph mit 6 Kanten NICHT selbstkomplementär ist:

Anzahl der Kanten:

Der erste Knoten hat (n-1) Ausgänge, der zweite (n-2), .. usw. = (n * (n-1)) / 2

n=6

|E| = (6*5) / 2 = 15

15 lässt sich nicht durch 2 teilen ( da es keine halben Kanten gibt) , somit hat entweder der Graph oder sein Komplement ein Überhang an Kanten, somit ist ein 6-Graph niemals selbstkomplementär. qed.

Answer 2

Zeichne überall alle fehlenden Kanten (mit einer andern Farbe!) ein. Das ist dann der Komplementärgraph.

a)1. Komplementärgraph enthält einen Zyklus der Länge 3.

Da der gegebene Graph keinen Zyklus enthält: nein!

a)2. Komplementärgraph lässt sich auch in einem Strich (2-4-1-3) zeichnen. --> ja!

a)3. Nein! Kompl. enthält Zyklus.

a)4. Ja! Kompl. lässt sich ein einem geschlossenen Pfad zeichnen. 1-3-5-2-4-1

a)5. Nein! Kein Zyklus der Länge 3 im Kompl. enthalten.

 

b) vgl. die andere Antwort.

Comments

a)5. Die Antwort ist zwar richtig, die Begründung jedoch nicht. Der Komplementärgraph besitzt sehr wohl einen Zyklus undzwar 2,3,4,5 der knoten 1 ist als einziger aussen und nur mit der 5 verbunden. Im KomplementärGraph sind nämlich noch die Diagonalen Knoten verkantet: 4 mit 3 und 5 mit 2.
Die nicht vorhandene Isomorphie lässt sich dann mit den unterschiedlichen Klassen der Knoten erklären. Es gibt nun nur noch einen Knoten mit einer Kante, dafür einen Knoten mit 3 Kanten (Der Rest hat 2 Kanten).

---

Danke für die Korrektur. Genügt meine Begründung in 5. jetzt?

---

Ja  genau, der Zyklus des Komplementärgraphen hat die Länge 4, -> nicht länge 3, demnach würde ich sagen, reicht das vollkommen aus. :)