Beinhaltet ein k-zusammenhängender graph ein Untergraph der k-vollständig ist?

Aufrufe: 173     Aktiv: 14.06.2024 um 00:21
Jetzt Frage stellen
1

Erstmal ein k-zusammenhängender Graph ist ein Graph wo man mindestens k Kanten entfernen muss damit der Graph nicht mehr zusammenhängend ist.

Ein k vollständiger Graph ist ein Graph mit k Knoten wo jeder Knoten mit jedem verbunden ist.

Ich versuche grade zu beweisen oder zu widerlegen, das wenn ein Grap k-zusammenhängend ist, er einen k-vollständigen Graph beinhalte.
Könnte mir jemand bitte einen Tipp geben um weiter zu kommen oder falls die Implikation falsch ist ein Gegenbeispiel?
Viele Grüße

Diese Frage melden
gefragt

Schüler, Punkte: 142

 
Kommentar schreiben
1 Antwort
1
Gegenbeispiel: Der Graph G bestehe aus den 6 Knoten
  • E-Werk
  • Wasserwerk
  • Gaswerk
  • Haus 1
  • Haus 2
  • Haus 3
Jedes Haus braucht Gas, Wasser und Strom; also wird jedes Werk mit jedem Haus durch eine Kante verbunden. Ansonsten hat G keine Kanten.

Dieser Graph ist m.E. 3-zusammenhängend, hat aber keinen vollständigen Untergraphen aus 3 Knoten.Denn gäbe es so ein Untergraphen U, dann hätte dieser mehrere Häuser oder mehrere Werke. Da weder Häuser noch Werke untereinander verbunden sind, kann U nicht vollständig sein.

Ich werde noch ein kleines Java-Progrämmchen schreiben, um das zu bestätigen.
Diese Antwort melden
geantwortet

Punkte: 2.34K

 
ne du hast recht, du hast einen bipartiten Graph erstellt, sozusagen wobei die eine Knotenmenge die werke und die andere Menge die Häuser sind. Das kann man auch sehr gut beweisen, da in beiden Mengen gelten muss das zwischen den Knoten in der selben Menge keinen Kanten exestieren. Vielen dank dafür bisschen peinlich das ich darauf nicht selber gekommen bin XD. Ich kann da gleich noch ein Beweis aufschreiben um das zu bestätitigen.   ─   henry dutter 13.06.2024 um 13:53

Der beweis sollte so gehen: Sei H die Knotenmenge der Häuser und W die Knotenmenge der Werke, nehmen wir an es gebe ein vollständigen untergraph G' mit 3 Knoten. G' muss mindestenst 2 Knoten aus einer der beiden Knotenmenge enthalten, da G' vollständig muessen a und b verbunden sein. Das ist aber ein Widerspruch da Knoten aus der Knotenmenge nicht verbunden sein duerfen.   ─   henry dutter 13.06.2024 um 14:03
1
Man muss dann natürlich noch zeigen, dass G 3-zusammenhängend ist.   ─   m.simon.539 13.06.2024 um 16:23
Also, mein Java-Progrämmchen ist auch der Meinung, dass der in meiner Antwort genannte Graph 3-zusammenhängend ist :-).   ─   m.simon.539 14.06.2024 um 00:21

Kommentar schreiben

Jetzt Antwort schreiben