Diskussion:K-Zusammenhang

Definitionsschwächen

Die verwendete Definition enthält leider mehrere Schwächen.

1) Welche Zusammenhangszahl vollständige Graphen (mit n Knoten) haben, bleibt völlig unklar. Naheliegend wäre n-1. Aber auch für alle größeren k bleibt die Bedingung "Es gibt keinen Trenner T=(X,Y) in G mit einer maximal (k-1)-elementigen Knotenmenge X und einer leeren Kantenmenge Y." erfüllt, da es in einem vollständigen Graphen überhaupt keine Trenner mit leerer Kantenmenge gibt.

2) Der Definition folgt die Behauptung: "Äquivalent dazu ist, dass für alle Knotenmengen K mit Mächtigkeit k − 1 der von V ∖ K induzierte Teilgraph zusammenhängend ist." Das klingt plausibel, ist es aber nicht. Betrachten wir einen Graphen, der aus zwei nichtverbundenen(!) Knoten besteht und wählen k=2. Wählt man eine beliebige Knotenmenge K mit k-1 Knoten, so ist der von V\K induzierte Teilgraph zusammenhängend (er besteht nur aus einem Knoten).

Das gleiche Problem taucht im Abschnitt über gerichtete Graphen nochmal auf.

Man kann das zweite Problem lösen/abmildern, indem man "mit Mächtigkeit k-1" durch "mit Mächtigkeit <=k-1" ersetzt. Für k>=1 kann man eine leere Knotenmenge K wählen. V\K ist dann nicht zusammenhängend. Die Problematik bei vollständigen Graphen bleibt aber im Wesentlichen erhalten. Bestenfalls verlagert sie sich auf die Frage, ob Graphen mit leeren bzw. einelementigen Knotenmengen zusammenhängend sind. Ist die Antwort ja (was mir sinnvoll erscheint), dann ist auch mit dieser Definition ein vollständiger Graph für jedes natürliche k auch k-zusammenhängend.

Kitaktus --194.31.198.71 12:35, 11. Aug. 2016 (CEST)

Diestel fordert für einen k-zsh. Graph, dass er mehr als k Knoten hat. Demnach wäre der vollständige Graph mit k Knoten nicht k-zsh. Und der Graph, der aus zwei nichtverbundenen Knoten besteht, wäre nicht 2-zsh.

StrgAltEntf --2001:9E8:46EE:EE00:180F:ECE0:6BAC:CF12 13:31, 12. Jan. 2023 (CET)