Я пытаюсь найти количество различных разрезов s-t в ориентированном невзвешенном графе. В статье Перечисление в графиках стр. . 45 Я нашел хороший способ перечислить эти разрезы (раздел 7.3). Есть ли более быстрый или простой алгоритм, который я могу использовать, если меня интересует только количество таких разрезов, и мне на самом деле не нужно их перечислять?
Определение разреза s-t, которое я использую, следующее. У нас есть ориентированный граф, в котором две вершины помечены S и T. Разрез — это минимальный набор ребер графа, при удалении которых перестанет существовать путь из вершины S в вершину T. .
