Diskussion:Zusammenhang (Graphentheorie)

Letzter Kommentar: vor 11 Monaten von Piusbmaier in Abschnitt Zwei Dinge: Graph G und Zusammenhang Z

Falsche Definition?

Bearbeiten

„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))Beantworten

Fehlende Quellen

Bearbeiten

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

Alte Diskussion

Bearbeiten

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)Beantworten

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)Beantworten

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

Satz von Mader

Bearbeiten

Im Text stand:

"Man zeigt dies, indem man als   die Menge aller Nachbarn von   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)Beantworten

Definitionen: Grausam!!!

Bearbeiten

"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)) Beantworten

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)Beantworten

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)Beantworten

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)Beantworten

[Inkorrekte Verlinkung englischer Artikel]

Bearbeiten

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))Beantworten

[Andere Algorithmen]

Bearbeiten

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))Beantworten


Was soll der Programmcode hier?

Bearbeiten

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)Beantworten

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))Beantworten

Zwei Dinge: Graph G und Zusammenhang Z

Bearbeiten

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)Beantworten