Zählen Sie die Anzahl der unterschiedlichen ST -Schnitte in einem orientierten Diagramm

Question

Ich versuche, die Anzahl der unterschiedlichen ST -Schnitte in einem orientierten, nicht schneller Diagramm zu finden. In einem Artikel Aufzählung in Grafiken p. 45 Ich fand einen guten Weg, wie man diese Schnitte aufzählt (Abschnitt 7.3). Gibt es einen schnelleren oder einfacheren Algorithmus, den ich verwenden kann, wenn ich nur an der Anzahl solcher Schnitte interessiert bin, und ich muss ihn eigentlich nicht aufzählen?

Die Definition eines ST -Schnitts, den ich verwende, folgt. Wir haben ein gerichtetes Diagramm, in dem zwei Scheitelpunkte gekennzeichnet sind S und T. Schnitt ist a minimal Satz von Kanten eines Diagramms, so dass durch Entfernen dieser Kanten keinen Pfad mehr von Scheitelpunkt vorhanden ist S zu Scheitelpunkt T.

Answer 1

Csteory.Stackexchange war der Ort! Meine Frage war antwortete dort, in dem Negativ.