Wie kann die Anzahl der starken zusammenhangskomponenten eines Graphen ändern, wenn eine neue Kante Hinzugefügt wird
Übung: 22.5-1 CLRS
Wie kann die Anzahl der starken zusammenhangskomponenten eines Graphen ändern, wenn eine neue
Kante Hinzugefügt wird?
Irgendwo die Antwort gegeben ist, Wenn eine neue Kante Hinzugefügt wird, wird eines von zwei Dingen passieren könnte.
1) Falls die neue Kante verbindet zwei Eckpunkte gehören eine starke zusammenhangskomponente, die Anzahl der starken zusammenhangskomponenten wird die gleiche bleiben.
2) Wenn, stattdessen, die Kante verbindet zwei starken zusammenhangskomponenten, und der Rand ist in umgekehrter Richtung von einem bestehenden Weg zwischen den beiden Komponenten, dann wird eine neue starke zusammenhangskomponente gemacht werden, wodurch die Anzahl der Komponenten.
Ich denke, der zweite Punkt ist falsch.
Angenommen, wir haben zwei starke zusammenhangskomponente C und C'
a) Wenn keine Kante oder Kante C->C' zwischen Ihnen besteht und die neue Kante verbindet als C->C' dann wird nichts passieren.
b) If Rand C->C' zwischen Ihnen besteht und die neue Kante verbindet als C'->C, dann C' zusammengeführt werden, um C eine Verringerung der Anzahl von starke zusammenhangskomponente von 1, da jeder vertex wird erreichbar sein, von einander.
Bitte korrigieren Sie mich, wenn ich falsch bin.
- Diese Frage scheint off-topic, weil es um Mathe
- Ich bin einverstanden mit der zitierten Antwort. Angenommen, Sie haben zwei SCC-ie C und C'. Jetzt, in der ungerichtete graph eine neue Kante Hinzugefügt wird-D. Es ist nur edge geht von C bis D. In diesem Fall gibt es keine Möglichkeit zu erreichen jeder anderen vertex aus D. Daher D wird eine unabhängige SCC. Jetzt ist die gesamte SSC für diesen graph ist 3 ie C,C', D. Bitte korrigieren Sie mich, wenn ich falsch Liege:)
- Ich denke SCC wird, bedeutete für den gerichteten Graphen nur. Und wenn seine ungerichtete Graphen es bedeutet, alle Kanten bidirektional und daher, wenn Sie sind in der Lage zu erreichen, von C nach D, dann mit der impliziten erreichen Sie von D nach C als gut.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sind Sie genau richtig. Die Antwort, die du zitiert ist falsch in seiner Beschreibung: hinzufügen von Kanten ist nur jemals verringern Sie die Anzahl der starken zusammenhangskomponenten. Wenn alle möglichen Kanten Hinzugefügt wurden, gibt es nur eine einzige starke zusammenhangskomponente Links - das gesamte graph.