imported>Piusbmaier: Neuer Abschnitt /* Zwei Dinge: Graph G und Zusammenhang Z */

2023-11-05T23:06:41Z

Neuer Abschnitt Zwei Dinge: Graph G und Zusammenhang Z

Neue Seite

== 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 [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/78.94.59.190|78.94.59.190]] ([[Benutzer Diskussion:78.94.59.190|Diskussion]])<nowiki/> 09:54, 23. Feb. 2014 (CET))

== Fehlende Quellen ==

Der Absatz "Wichtige Algorithmen" ist mit keiner Quelle belegt! --[[Benutzer:C0bra1987|C0bra1987]] ([[Benutzer Diskussion: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.
--[[Spezial:Beiträge/85.0.66.103|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. --[[Benutzer:Coma|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. --[[Benutzer:Coma|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? -- [[Benutzer:Thorsten Thielen|thth]] 12:33, 11. Mai 2006 (CEST)

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

== Satz von Mader ==

Im Text stand:

"Man zeigt dies, indem man als <math>A</math> die Menge aller [[Nachbarschaft und Grad in Graphen|Nachbarn]] von <math>a</math> 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. --[[Benutzer:FerdiBf|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 [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/188.107.172.161|188.107.172.161]] ([[Benutzer Diskussion:188.107.172.161|Diskussion]])<nowiki/> 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.--[[Benutzer:Claude J|Claude J]] ([[Benutzer Diskussion: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)--[[Benutzer:Suhagja|Suhagja]] ([[Benutzer Diskussion: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...--[[Benutzer:Claude J|Claude J]] ([[Benutzer Diskussion: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 [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/93.129.38.53|93.129.38.53]] ([[Benutzer Diskussion:93.129.38.53|Diskussion]])<nowiki/> 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 [[Hilfe:Signatur|signierter]] Beitrag von'' [[Spezial:Beiträge/93.129.38.53|93.129.38.53]] ([[Benutzer Diskussion:93.129.38.53|Diskussion]])<nowiki/> 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? --[[Benutzerin:Graf Alge|Graf Alge]] ([[Benutzerin Diskussion: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. {{unsigniert|77.183.76.50|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 [[Graph (Graphentheorie)|Graphen]] 'zusammenhängend' zu sein reduziert. In der Definition wird dann eine weitere Bezeichnung '(Zusammenhang-s-)Komponente' eingeführt, indem die Betrachtungsposition auf [[Teilgraph|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 (Graphentheorie)|Knoten]], die paarweise über mindestens einen [[Weg (Graphentheorie)|Pfad]] verbunden sind, wobei eine etwaige [[Kante (Graphentheorie)|Kante]]nrichtung 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 (Graphentheorie)|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 (Graphentheorie)|Wald]]. --[[Benutzer:Piusbmaier|Piusbmaier]] ([[Benutzer Diskussion:Piusbmaier|Diskussion]]) 00:06, 6. Nov. 2023 (CET)

Diskussion:Zusammenhang (Graphentheorie) - Versionsgeschichte

imported>Piusbmaier: Neuer Abschnitt /* Zwei Dinge: Graph G und Zusammenhang Z */