Was ist ein schneller Algorithmus zum Auffinden kritischer Knoten?

Ich bin auf der Suche nach einer schnellen Methode/Algorithmus zum Finden der Knoten in einem Graphen ist kritisch.Was ist ein schneller Algorithmus zum Auffinden kritischer Knoten?

Zum Beispiel in diesem Diagramm: alt text

Knotennummer 2 und 5 sind kritisch.

Meine aktuelle Methode besteht darin, jeweils einen Nicht-Endpunkt-Knoten aus dem Diagramm zu entfernen und dann zu überprüfen, ob das gesamte Netzwerk von allen anderen Knoten aus erreicht werden kann. Diese Methode ist offensichtlich nicht sehr effizient.

Was ist ein besserer Weg?

Quelle

2010-09-09 monoceres

Siehe: http://portal.acm.org/citation.cfm?id=1480409. Sie beweisen, dass das Erkennen kritischer Knoten NP-vollständig ist, daher würde ich keine drastischen Verbesserungen erwarten. –

Sie sind besorgt über die Knoten, nicht die Links? Zum Beispiel, wenn ich eine Verbindung zwischen 3 und 6 habe, dann, um kritische Knoten zu finden, muss ich Links finden, die zuerst entfernt werden können. –

@Jerry Coffin - Ich erinnere mich an etwas in einer elektrischen Netzwerkanalyse-Klasse, aber ich würde es wieder suchen müssen, aber je nach den Vereinfachungen kann dies leicht oder sehr schwer zu lösen sein, da der allgemeine Fall zu schwierig ist, wie du gesagt hast. –

Siehe biconnected components. Wenn man sie anstelle von kritischen Knoten Artikulationspunkte nennt, ergeben sich bessere Suchergebnisse.

In jedem Fall besteht der Algorithmus aus einer einfachen depth first search, wo Sie bestimmte Informationen für jeden Knoten pflegen.

Quelle

2010-09-09 16:37:15 IVlad

Vielen Dank, Artikulationspunkte haben tatsächlich bessere Ergebnisse gebracht und ich habe einige sehr gefunden nützliche Links zur Tiefensuche – monoceres

gibt es mehrere bessere Möglichkeiten. research is always helpful

aber da diese Hausaufgaben, ist der Sinn der Übung wahrscheinlich, es zu sein, herauszufinden, selbst

Hinweis: wie kann man die Grafik dekoriert, Ihnen zu sagen, was Knoten abhängen, welche anderen Knoten, und würde Diese Information ist vielleicht nützlich, um die kritischen Knoten zu erkennen?

Quelle

2010-09-09 16:11:41

Was ist ein schneller Algorithmus zum Auffinden kritischer Knoten?

Antwort

Verwandte Themen