0 Daumen
3k Aufrufe

 

Komplementärgraphen: Ein Graph G wird selbstkomplementär genannt, wenn G isomorph zu seinem Komplementärgraphen  ist. (Anm: G hat den Querstrich oben, nicht unten)



Aufgabe 3: Komplementärgraphen 5 + 1 Punkte Ein Graph G wird selbstkomplementär genannt, wenn G isomorph zu seinem Kom- plementärgraphen Ü ist. a) Entscheiden Sie für die nachfolgend abgebildeten Graphen, ob sie selbstkomple- mentär sind oder nicht. Positive Antworten sind durch Beschreibung eines Isomor- phismus zu begründen, negative Antworten durch Argumente, warum G und Ü nicht isomorph sein können. b) Zeigen Sie, dass es keine selbstkomplementären Graphen mit 6 Knoten gibt!

Gefragt von
Du darfst den Text auch abschreiben und die Graphen dazuposten.
:))))

danke

2 Antworten

+1 Punkt
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.
Beantwortet von
0 Daumen

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.

Beantwortet von 144 k
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. :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...