Найти все разрезы сети (графа)
Есть сеть N (граф имеющий исток и сток) состоящая из k вершин. Представленная в виде списка смежности (словарь).
N = dict()
k = int(input("Из скольки вершин состоит сеть? >> "))
for v in range(k):
N[v] = [int(i) for i in input(f"В какие вершины есть ребро из {v}-й вершины? >> ").split()]
print(N)
Нужно найти все разрезы данной сети и вывести их. Разрез - множество ребер, удалив которые сток (конечная вершина) будет недостижим. То есть удалив некоторые ребра графа (нужно найти как раз все варианты), мы никогда не сможем прийти от начальной вершины к конечной.
Ответы (1 шт):
Приходит а голову такой вариант - перечислить все подмножества графа, доступные из истока - да, их экспоненциальное количество, но ведь и разрезов тоже.
Для каждого подмножества проверить, является ли дополнение (набор остальных узлов) связным, и найти все дуги, которые начинаются в узлах данного подмножества, и кончаются в узлах остатка (множества-дополнения). Это и будет разрез.
Подводные камни наверняка есть - например, мне не вполне очевидно навскидку, что dfs или bfs дадут все связные подмножества из истока (их ещё, видимо, придётся проверять на уникальность, например - храня битовые маски проверенных)