Diskussion:Zusammenhang (Graphentheorie)

Falsche Definition?

„Ein gerichteter Graph G=(V,E) heißt (stark) zusammenhängend von einem Knoten v aus, falls es zu jedem Knoten w einen gerichteten Weg in G mit v als Startknoten und w als Endknoten gibt. G heißt stark zusammenhängend, falls G von jedem Knoten aus stark zusammenhängend ist”

Irr ich mich oder müsste es nicht im letzten Teil heißen „[…], falls G von jedem Knoten aus zusammenhängend ist“. Falls nein, fehlt im Artikel gänzlich eine Definition von „stark zusammhängend“. (nicht signierter Beitrag von 78.94.59.190 (Diskussion) 09:54, 23. Feb. 2014 (CET))

Fehlende Quellen

Der Absatz "Wichtige Algorithmen" ist mit keiner Quelle belegt! --C0bra1987 (Diskussion) 13:15, 5. Apr. 2012 (CEST)

Alte Diskussion

Der ARtikel sollte dringend einem Facelifting unterzogen werden, der sieht rein optisch schrecklich und unansprechend aus. Eventuell wären kleinere illustrationen auch gut. --85.0.66.103 05:38, 30. Dez. 2007 (CET)

Vorschlag eines Alternativen Artikel siehe Zusammenhang (Graphentheorie)

Am besten wäre natürlich zu jeder Definition ein Bild als Beispiel ;-)

Genau hier bekommst Du Probleme. Wenn jemand Zusammenhang von gerichteten Graph sucht, findet er nichts. Meine Artikel brauchen auch noch Bilder und Beispiele, geb ich zu, hab aber grad nicht so viel Zeit. Ich suche ja jemanden der soetwas malt!

Ich finde die alternative Version schlechter, weil Ausdrücke wie "zerfällt in ZSK" sehr stark interpretierbar sind. Viele verbinden damit vielleicht einen Prozess, der garnicht stattfindet! Und wie eine ZSK aussieht oder was sie ist, weiß man auch nicht genau. --Coma 11:51, 28. Jan 2003 (CET)

Hallo! Ist es möglich, den Text auf die einzelnen Begriffe aufzuteilen? Ich finde so einen langen Text etwas unübersichtlich. Danke!

Nein, der Text bleibt so, da es sich um einen Übersichtsartikel zu einem ganzen Gebiet der Graphentheorie handelt, allerdings bekommen die einzelnen Begriffe noch kurze eigene Artikel. --Coma 01:03, 6. Apr 2004 (CEST)

Hallo! Bist Du sicher, dass die Definition der starken Zusammenhangskomponenten wirklich einschliesst, dass kein Knoten aus VK Vorgänger oder Nachfolger eines Knotens aus V\VK sein darf? Ich habe diese Einschränkung bei keiner anderen Definition von SZK gefunden und IMHO würde das doch bedeuten, dass entweder der ganze Graph stark zusammenhängend ist oder der Graph (nur) aus mehreren überhaupt nicht zusammenhängenden SZK besteht? -- thth 12:33, 11. Mai 2006 (CEST)

Danke für den Hinweis. Du hast recht, das war falsch. Habs geändert. --Koethnig 12:55, 11. Mai 2006 (CEST)

Satz von Mader

Im Text stand:

"Man zeigt dies, indem man als $A$ die Menge aller Nachbarn von $a$ nimmt und den Satz von Mader anwendet."

Das kann ich so nicht nachvollziehen, insbesondere das Auftauchen der Menge A verlangt nach einer Erklärung (wie wird der Satz von Mader hier auf A angewendet?). Daher habe ich diesen Satz bis auf Weiteres entfernt. --FerdiBf 17:02, 15. Jun. 2011 (CEST)

Definitionen: Grausam!!!

"Verbindbarkeit" ist doch keine Äquivalenzrelation, sondern etwas aus dem Umfeld von Krankenschwestern.

Eine Äquivalenzklasse ist auch kein Teilgraph.

Falls  nicht zusammenhängend ist, nennt man  unzusammenhängend, der Graph zerfällt dann in seine Zusammenhangskomponenten.

occam's razor: Du sollst nicht definieren, was du nicht brauchst.

Was ist jetzt eine Zusammenhangskomponente ? Eine Knotenmenge? Ein Teilgraph? Ein Pfad? Die Menge aller möglichen Pfade zwischen A und B. Man kann das alles im Lehrbuch nachlesen, Warum also dieser Unsinn? (nicht signierter Beitrag von 188.107.172.161 (Diskussion) 20:26, 15. Okt. 2012 (CEST))

Nach der Definition von k-fach kantenzusammenhängend wäre ein Graph einfach kantenzusammenhängend wenn es keine maximal nullelementige Menge von Kanten gibt (also leere Menge), die den Graph trennt. Das ist doch widersinnig.--Claude J (Diskussion) 13:57, 13. Mär. 2013 (CET)

1-fach zusammenhängend = zusammenhängend. (Sollte vielleicht auch im Artikel erwähnt werden, schon um die Bezeichnung zu motivieren)--Suhagja (Diskussion) 19:11, 13. Mär. 2013 (CET)

Das betrifft nicht nur diese Definition (knotenzusammenhängend genauso), hier wird Brücke so definiert: Eine Brücke ist eine Kante, die ihre beiden inzidenten Knoten trennt. Das würde ich so verstehen, dass mit inzident die beiden Knoten gemeint sind, die die Kante verbindet (inzident zu Kante: liegt an einem der beiden Enden). Das trifft auf jede Kante zu. Was gemeint ist ist klar (nach Entfernen der Kante gehören die inzidenten Punkte (sprich Endpunkte) zu zwei nicht miteinander zusammenhängenden Graphen), aber die Formulierung...--Claude J (Diskussion) 07:39, 14. Mär. 2013 (CET)

[Inkorrekte Verlinkung englischer Artikel]

Es wird auf Connectivity statt auf SCC im Englischen verlinkt, man könnte da auch einen Verweis einbauen, ist nur für die Suche blöd (nicht signierter Beitrag von 93.129.38.53 (Diskussion) 18:33, 3. Aug. 2015 (CEST))

[Andere Algorithmen]

Kosaraju's algorithm bzw. Kosaraju's Algorithmus und Path-based strong component algorithm wären zumindest erwähnenswert bzw. die Unterschiede könnte man erwähnen (nicht signierter Beitrag von 93.129.38.53 (Diskussion) 18:33, 3. Aug. 2015 (CEST))

Was soll der Programmcode hier?

Was hat ein Rechnerprogramm in einer Enzyklopädie zu suchen? Ich kann keinen Mehrwert zum Verstehen des Themas erkennen. Der ganze Abschnitt sollte gelöscht werden - auch wenn sicher viel Mühe in dem langen Text steckt. Es gehört einfach nicht hierher. Meinungen? --Graf Alge (Diskussion) 12:57, 25. Mär. 2021 (CET)

Graphentheorie ist für die Entwicklung von bestimmten Computerprogrammen sehr relevant, weshalb dieser Abschnitt absolut Sinn macht. (nicht signierter Beitrag von 77.183.76.50 (Diskussion) 10:22, 9. Jun. 2021 (CEST))

Zwei Dinge: Graph G und Zusammenhang Z

Der Überschrift nach sollte der Artikel etwas beschreiben, das als 'Zusammenhang' bezeichnet wird - leider wird bereits in der Einführung der Begriff auf die Eigenschaft eines Graphen 'zusammenhängend' zu sein reduziert. In der Definition wird dann eine weitere Bezeichnung '(Zusammenhang-s-)Komponente' eingeführt, indem die Betrachtungsposition auf Teilgraphen verschoben wird. Ein Teilgraph ist jedoch genauso ein Graph, wie eine 'Zusammenhangskomponente' ein 'Zusammenhang' ist. Ein 'Zusammenhang' ist entsprechend eine (Teil-)Menge von Knoten, die paarweise über mindestens einen Pfad verbunden sind, wobei eine etwaige Kantenrichtung nicht beachtet wird. Veranschaulicht: Wenn man an einem Knoten des Zusammenhangs zieht, hängen alle dem Zusammenhang zugehörigen Knoten daran. Andersherum bedeutet es aber nicht, dass zwingend alle Knoten des Graphen zugehörig sein müssen. Genauso wie ein Baum unabhängig von unverbundenen Knoten vorliegen kann, ist ein konkreter Zusammenhang ein eigenständiges 'Gebilde' und als Begriff eine Obermenge zum Begriff Baum - jeder Baum ist ein Zusammenhang. An vielen Stellen in den Graphentheorieartikeln wird leider diese Verschiebung der Betrachtungsposition vorgenommen - dieses Changieren zwischen Aussagen, welche alle Knoten/Kanten eines bestimmten Graphen und jenen, welche nur eine Teilmenge dieser betreffen, trägt wenig zum Begriffsverständnis bei. Weitere Anmerkungen/Fragen: "Einen maximalen zusammenhängenden Teilgraphen eines Graphen nennt man eine Komponente oder Zusammenhangskomponente." - bedeutet hierbei 'maximal', dass ein Zusammenhang nur dann eine Komponente ist, wenn alle verbundenen Knoten auch Element des Teilgraphen sind? Fehlt dann ein Artikel zu 'Komponente'? "Ein nicht zusammenhängender Graph wird durch seine Zusammenhangskomponenten partitioniert." - daraus ergibt sich, dass verbindungsfreie (isolierte) Knoten auch '(Zusammenhang-s-)Komponenten' sind. Da isolierte Knoten azyklisch sind, sind sie auch Bäume. Diese Sichtweise verträgt sich gut mit dem Begriff Wald. --Piusbmaier (Diskussion) 00:06, 6. Nov. 2023 (CET)