Mithilfe der Adjazenzmatrix eines Graphen feststellen ob dieser zusammenhängend ist (Graphentheorie)

...komplette Frage anzeigen

2 Antworten

Alter, was soll denn das für ein Schulniveau sein? Ich hab mir jetzt mal ein paar Gedanken gemacht, aber durch meine Unidefinitionen hab ich meine Gedanken nur unnötig verkompliziert, bin aber - so hoffe ich - auf die richtige Lösung gekommen...

Also jetzt mal allgemein zusammenhängend bei einem ungerichteten Graphen. Die Adjazenzmatrix eines ungerichteten Graphen ist ja wegen seiner Ungerichtetheit symmetrisch (denn wenn du über die Kante e von v1 nach v2 kommst, dann kommst du auch über selbige zurück, da sie ja ungerichtet ist).

Bei einem schwach zusammenhängenden Graphen muss Gsym (also der dazugehörige symmetrische oder quasi auch ungerichtete Graph) stark zusammenhängend sein. Also läuft's wieder darauf hinaus, dass eine symmetrische Adjazenzmatrix zu betrachten ist.

Ich betrachte jetzt in der Adjazenzmatrix jene Werte außerhalb der Hauptdiagonalen, denn dort stehen ja nur die Schleifen, die völlig egal sind. Ein Graph ist unserem Fall ja nur dann nicht stark zusammenhängend, wenn mindestens ein Knoten keine Kanten zu einem anderen Knoten besitzt, denn sonst kommt man ja über die ungerichteten Kanten immer zu jedem anderen und zurück.

Wie erkennt man so einen solchen Knoten in der Adjazenzmatrix? Die Kanten an einem bestimmten Knoten sind ja in der Adjazenzmatrix immer die Spalten (oder die Zeilen, was identisch ist, da unsere Matrix ja symmetrisch ist). Eine Spalte/Zeile darf NICHT nur Nullen als Elemente außerhalb des einen Eintrags, der auch auf der Hauptdiagonalen liegt (!!!), besitzen.

Warum? Besitzt er nur Nullen, so hat er keine Kanten und der Graph ist nicht zusammenhängend. Sonderfall: Ein Knoten hat eine oder mehrere Schleifen, aber sonst keine Kanten. Dann ist er auch nicht verbunden mit anderen Knoten, obwohl er eben Kante(n) hat. Deswegen dieser wichtige Zusatz mit dem Element der Hauptdiagonale!

Puh... das war's. Das Ganze ist natürlich nicht übertragbar auf die Frage, wann ein gerichteter Graph stark zusammenhängend ist. Hier wäre nämlich der Fall möglich, dass trotz Kanten zwischen allen Knoten dies nicht erfüllt wäre. Beispiel: 2 Knoten v1 und v2 und eine Kante e von v1 gerichtet nach v2. Dieser hat zwar eben eine Kante, aber man kommt nicht von v2 nach v1. Hier müsste man das Problem anders behandeln.

ich meine allgemein ob der Graph zusammen ist, jetzt unabhängig von der Art

Was möchtest Du wissen?