 |
 |
 |
 |
 |
 |
Startseite » Forum » Graphentheorie, Komplementgraph
Graphentheorie, Komplementgraph
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie, Kardinalität, Komplementgraph
 
|
  |
|---|
|
Hey Leute, ich muss die unten stehende Aufgabe lösen, jedoch habe ich große Schwierigkeiten mit Beweisaufgaben. Könnte mir jemand weiterhelfen? Viele Grüße Der Komplementgraph G ̄ = (V, E ̄) eines ungerichteten Graphen G = (V, E) ist derjenige Graph mit Knotenmenge V , dessen Kantenmenge das Komplement von E ist, also aus allen Untermengen von V der Kardinalität 2 besteht, die nicht in E sind. Beweisen oder widerlegen Sie: Ist card V ≥ 5, so enthält mindestens einer der beiden Graphen einen Kreis. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, habt Ihr einen Satz / Lemma, dass in einem kreisfreien Graph gilt: ? Gruß pwm |
 |
|
Wir haben folgendes Lemma: G = (V, E) ist kreisfrei genau dann, wenn card E(S) card S -1 für alle = S V. |
|
|
|
Hallo, Nimm an, beide Graphen seien kreisfrei. Dann stelle diese Ungleichung für den Graphen und den Komplementärgraphen auf und addiere. Beachte, dass die Kanten von beiden Graphen zusammen die Menge aller 2-er Mengen aus ergeben. Daraus ergibt sich eine Einschränkung für . Gruß pwm |
|
|
|
Also dann habe ich Folgendes: Wir nehmen an, beide Graphen seien kreisfrei, dann gilt: für G = (V, E): card E(S) card S -1 und für : card Wenn wir beides addieren erhalten wir: "Beachte, dass die Kanten von beiden Graphen zusammen die Menge aller 2-er Mengen aus V ergeben. Daraus ergibt sich eine Einschränkung für n." card E(S) + card (wie gebe ich die 2-er Menge von V an?) Ich weiß außerdem das n := card V und m := card E. Und Jede Kantenmenge mit Kardinalität beinhaltet einen Kreis |
|
|
|
Hallo, du interessierst dich doch nur für ... Gruß ermanus |
|
|
|
Ich addiere card E card V - 1 und card card V -1. Daraus erhalte ich: card E + card 2*(card V - 1) Wir wissen n := card V. Daraus folgt: card E + card 2*(n - 1) Außerdem wissen wir das card E + card = card V mit card V = 2 Dann folgt daraus n = card E + card 2*(n - 1) |
|
|
|
2 = card E + card E‾≤ 2*(n - 1) Daraus folgt 2 2*(n-1) Also wir wissen, wenn beide Graphen kreisfrei sind, dann gilt |
|
|
|
Keine Ahnung, was du da seltsames machst ;-) ist doch die maximale Anzahl von Kanten, die bei Knoten möglich sind, also . |
|
|
|
Und was kommt danach? Ich bedanke mich wirklich ganz herzlich bei dir für deine Hilfe und Mühe |
|
|
|
Dann hast du als Bedingung für die Kreisfreiheit . Deine Aufgabe besteht nun darin zu zeigen, dass diese Ungleichung für nicht mehr erfüllt ist. |
|
|
|
Also ich habe die Ungleichung umgeformt und erhalte . Das bedeutet die Ungleichung ist für n > 4 nicht mehr erfüllt. Ist card V 5, also n , ist diese Bedingung verletzt und somit hat einer der beiden Graphen einen Kreis. ist der Beweis hiermit beendet? |
|
|
|
Ja. So hast du die Behauptung bewiesen ! Gruß ermanus |
 |
|
Ich danke dir vielmals!! |
1539333
1539221