0

Есть сеть 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 ответ 1

0

Приходит а голову такой вариант - перечислить все подмножества графа, доступные из истока - да, их экспоненциальное количество, но ведь и разрезов тоже.

Для каждого подмножества проверить, является ли дополнение (набор остальных узлов) связным, и найти все дуги, которые начинаются в узлах данного подмножества, и кончаются в узлах остатка (множества-дополнения). Это и будет разрез.

Подводные камни наверняка есть - например, мне не вполне очевидно навскидку, что dfs или bfs дадут все связные подмножества из истока (их ещё, видимо, придётся проверять на уникальность, например - храня битовые маски проверенных)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.