Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Graph Komplementärgraph
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Graph Komplementärgraph
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-12-05






Welche der Graphen sind selbstkomplementär? Also oben sind nur G_1 und G_2 gegeben, aber wenn man doch den Komplementär graph zeichnet, ist es doch eigentlich immer selbstkomplementär

Geben Sie möglichst viele nichtisomorphe selbstkomplementäre Graphen mit bis zu 7 Knoten an. Begründen Sie, warum es nicht mehr gibt.


Ist nicht jeder Graph zu seinem Komplement selbstkomplementär? Wenn nein, wieso?

Wie gehe ich gennau bei der zweiten Aufgabe vor?

Danke.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-12-05


Hallo,


Ist nicht jeder Graph zu seinem Komplement selbstkomplementär? Wenn nein, wieso?
Nein. Gegenfrage, warum glaubst du, dass das so sein sollte? Nimm das Haus vom Nikolaus. Es hat 5 Knoten und 8 Kanten. Der Komplementärgraph hat entsprechend $\binom{5}{2}-8=2$ Kanten, ist also nicht isomorph zum ersten.

Zum Verständnis:
Du zeichnest einen vollständigen Graphen auf $n$ Knoten und färbst jede Kante entweder rot oder blau. Wenn der rote Graph zum blauen Graphen isomorph ist, heißt der blaue Graph selbstkomplementär.

Überlege dir als erstes, für welche $n$ dies nur möglich ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-12-05


Hey ochen, danke für die schnelle Antwort. 😃

Ich glaube, mein Problem bestand eher darin, dass ich gedacht habe, dass der Komplementärgraph einfach nur eine Verschiebung der Buchstaben im Graph selbst ist.




Aber da lag ich falsch? 🤔

Wie genau muss ich den Komplementärgraph verstehen?  

Und wie genau kommt deine Formel bzgl. der Kanten zustande?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-12-05


Du zeichnest einen Graphen $G$ auf $n$ Knoten mit Kanten in roter Farbe. Wenn zwischen manchen Knoten keine rote Kante besteht, zeichnest du eine blaue. Der Graph mit den blauen Kanten heißt Komplementärgraph von $G$ oder kurz $\overline{G}$.

Die Anzahl aller Kanten auf einem vollständigen Graphen ist $\binom{n}{2}$. Entsprechend gilt für die Anzahl der Kanten $\binom{n}{2}=|E(G)|+|E(\overline{G})|$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-12-05




Hey, meinst du das so? ^^

\[\binom{5}{2}= 6 + 4 = 10\]
Da die Kantenanzahl aber nicht übereinstimmt, ist sogesehen der erste Graph definitiv schonmal falsch. ^^ Also nicht selbstkomplementär richtig? 🙄

Also bevor ich mich auf den anderen Graph stürze^^



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-12-05


2020-12-05 15:38 - Vanessax3 in Beitrag No. 5 schreibt:


Hey, meinst du das so? ^^

Ja:)


\[\binom{5}{2}= 6 + 4 = 10\]
Da die Kantenanzahl aber nicht übereinstimmt, ist sogesehen der erste Graph definitiv schonmal falsch. ^^ Also nicht selbstkomplementär richtig? 🙄

Also bevor ich mich auf den anderen Graph stürze^^
Wie zählst du denn? :P  Sowohl der rote als auch der blaue Graph haben 5 Kanten. Sie sind auch isomorph zueinander.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-12-05


Jaa, sorry war gerade einfach nur lost. 🙄

Kleine Frage: Wieso kann man aus der Kantenanzahl, also wenn beides übereinstimmt direkt sagen, dass sie isomorph sind, also fürs Verständnis.

Der zweite Graph ist nicht isomorph, da stimmt die Kantenanzahl nicht überein.


So zur zweiten Aufgabe:
Geben Sie möglichst viele nichtisomorphe selbstkomplementäre Graphen mit bis zu 7 Knoten an. Begründen Sie, warum es nicht mehr gibt.

Hast du dazu Tipps? ^^



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6571
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-12-05


Hallo Vanessax3,

2020-12-05 15:52 - Vanessax3 in Beitrag No. 7 schreibt:
Geben Sie möglichst viele nichtisomorphe selbstkomplementäre Graphen mit bis zu 7 Knoten an. Begründen Sie, warum es nicht mehr gibt.

Für einen selbstkomplementären Graphen G muss ja \(|E(G)|=|E(\overline G)|\) gelten. Mit der Formel von ochen aus Beitrag #3 kannst du dann schon mal viele Zahlen n von 1 bis 7 ausschließen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-12-05


Hei StrgAltEntf :)

Wenn ich jetzt nicht falsch liege, Knoten sei n:

Bei n = 1, gibt es keinen Komplementärgraph oder?
Bei n = 2, hier auch nicht.
Bei n = 3; hier schon, aber keiner der isomorph ist
Bei n = 4; hier gibt es ein, der auch isomorph ist.
bei n = 5;  hier gibt es ein, der auch isomorph ist.
bei n = 6; hier gibt es zwar ein, aber keiner der isomorph ist.
bei n = 7; hier gibt es zwar ein, aber keiner der isomorph ist.

Habe ich das richtig erkannt? 🤔



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-12-05


Hallo nochmal,

einen komplementären Graph gibt es immer. Das bedeutet für $n=1$, dass der Graph mit nur einem Knoten und keiner Kante zu sich selbst komplementär ist.

Kannst du mal beschreiben, was du gerechnet hast?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-12-05


Ja gerne, also zuallererst bin ich jeden Schritt von n=1 bis n=7 hochgegangen.

n = 1
\[\binom{1}{2}\]
Da man diesen Binomialkoeffizienten nicht ausrechnen kann, bin ich davon ausgegangen, dass es keinen Komplementärgraphen für G gibt, weil ja gelten muss:

\[\binom{n}{2}=|E(G)| + |E(\overline G)|\]
Oder moment mal, damit kriegt man die Anzahl der Kanten, bei einem Knoten existieren ja keine Kanten. 🤔🤔

n = 2

\[\binom{2}{2}=1\]
Mit der Formel kriegt man doch, sowie ich das jetzt verstanden habe, die Anzahl der Kanten des Graphen von G, die man insgesamt machen kann.



Der Graph unten, ist das der Komplementärgraph von dem oben?🤔

n = 3

\[\binom{3}{2}=3\]
Also wie ich auf meine Aussagen gekommen, ich habe immer den Binomialkoeffizienten ausgerechnet und geguckt, ob die Zahl durch zwei Teilbar ist. Aber da lag ich bestimmt meilenweit daneben^^

Hmm da bin ich echt überfragt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-12-05


2020-12-05 17:32 - Vanessax3 in Beitrag No. 10 schreibt:

Also wie ich auf meine Aussagen gekommen, ich habe immer den Binomialkoeffizienten ausgerechnet und geguckt, ob die Zahl durch zwei Teilbar ist. Aber da lag ich bestimmt meilenweit daneben^^


Nein, damit liegst du nicht daneben, das ist genau richtig, aber es liefert nur ein notwendiges Kriterium.

Damit meine ich:

Wenn $\binom{n}{2}$ nicht durch 2 teilbar ist, kann es erst recht keinen selbstkomplementären Graphen auf $n$ Knoten geben.

Wenn $\binom{n}{2}$ durch 2 teilbar ist, kann es einen selbstkomplementären Graphen auf $n$ Knoten geben. Dieser hätte dann $\frac 12\binom n2$ Kanten. Ob es so einen gibt, musst dann aber erst prüfen.

Es gilt übrigends $\binom{1}{2}=0$ oder allgemeiner $\binom{n}{k}=0$ für $n<k$




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-12-05


2020-12-05 17:37 - ochen in Beitrag No. 11 schreibt:

Ob es so einen gibt, musst dann aber erst prüfen.


Dieser eine Satz bringt mich zu sehr zum Nachdenken. Heißt das, dass nicht immer einen gibt, wenn die Kantenanzahl durch zwei teilbar ist? wenn ja, wie kann ich das überprüfen^^?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-12-05


Naja, es gibt einfach gar nicht so viele Graphen mit genau 4 Knoten und 3 Kanten. Überprüfe einfach, ob welche davon selbstkomplementär sind.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2020-12-05


Ich bin gerade ein bissel überfragt.^^


Meinst du das so? 🤔




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-12-05


Ja genau, welcher deiner Graphen ist jetzt selbstkomplementär? Der im ersten oder der im zweiten Bild?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2020-12-05


Der erste ist auf jeden Fall nicht selbstkomplementär, da die Verteilung der Grade nicht übereinstimmen. Der hat bei einem Knoten grad 3, während der Graph G keinen Knoten mit Grad 3 hat.

Und der zweite müsste selbstkomplementär sein oder? 🤔




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ochen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 09.03.2015
Mitteilungen: 3051
Herkunft: der Nähe von Schwerin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-12-05


Ja genau :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 13.11.2020
Mitteilungen: 27
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2020-12-05


jaaa!!!!! 😄😄😄😄

Danke dir!! 🤗🤗🤗🤗


Schönen Abend noch. 🤗



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6571
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2020-12-05


Hallo,

fassen wir also noch einmal zusammen.

Ein Graph mit n Ecken kann nur dann selbst-komplementär sein, wenn \(\frac12\binom n2\) eine ganze Zahl ist. Ist dies der Fall, hat der selbst-komplementäre Graph \(\frac12\binom n2\) Kanten.

Für \(n\in\{2,3,6,7\}\) ist \(\frac12\binom n2\) keine ganze Zahl, also gibt es keinen selbst-komplementären Graphen mit 2, 3, 6 oder 7 Ecken.

Für n = 1 gibt es nur einen Graph mit n Ecken. Dieser ist selbstkomplementär. (Klar wieso?)

Für n = 4 gibt es (bis auf Isomorphie) nur zwei Graphen mit vier Ecken und \(\frac12\binom 32\)=3 Kanten. Einer davon ist selbst-komplementär. (Siehe Beitrag #16.)

Für n = 5 haben wir bereits einen selbst-komplementären Graphen kennengelernt, nämlich den Kreis der Länge 5 (s. o.).

Was jetzt noch offen ist, ob es noch einen weiteren selbst-komplementären Graphen mit 5 Ecken gibt.





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6653
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2020-12-05


Anmerkung: Für n=4 gibt es bis auf Isomorphie drei(!) verschiedene Graphen mit je drei Kanten. Zwei davon sind zueinander komplementär, der dritte zu sich selbst.

Bei n=5 muss man ein bisschen Tüfteln. Von der Gradverteilung her kommen drei Möglichkeiten in Betracht.

[Die Antwort wurde nach Beitrag No.13 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6571
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-12-06


2020-12-05 23:12 - Kitaktus in Beitrag No. 20 schreibt:
Anmerkung: Für n=4 gibt es bis auf Isomorphie drei(!) verschiedene Graphen mit je drei Kanten. Zwei davon sind zueinander komplementär, der dritte zu sich selbst.
Stimmt, danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Vanessax3 hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]