Нахождение «пузырей» на графике

Question

В игре у нас есть вселенная, описанная как сильно связанный граф, полный секторов и ребер. Иногда есть небольшие карманы, игроки называют их «пузырями», где небольшая группа узлов получает доступ к остальной части сети через один узел. На приведенном ниже графике секторы 769, 195, 733, 918 и 451 доступны только через узел 855. Если вы можете эффективно охранять 855, то эти другие сектора безопасны. Другие узлы на графике имеют больше ребер (фиолетовые линии) и не являются «пузырьками» в номенклатуре игрока.

В сети с 1000 или 5000 узлами найти такие подструктуры нелегко. Но я подозреваю, что эта идея как-то описана в теории графов, и поэтому, вероятно, ее можно найти в сети x.

Может ли кто-нибудь предложить теоретико-графический подход для систематического поиска таких структур? Чтобы быть понятным, граф - это ориентированный граф, но практически все ребра на практике оказываются двунаправленными. Края невзвешенные.

Answer 1

Теория графов не имеет определений для ваших «пузырей», но имеет аналогичное определение - bridges .Мост - это ребро, удаление которого увеличивает количество подключаемых компонентов.Как видите, это именно то, что вам нужно.networkx имеет кучу алгоритмов для поиска мостов.Как ни странно, это называется мосты :)

Пример:

import networkx as nx

G = nx.Graph()
G.add_edges_from([
    (1,2),(1,3),(2,3),
    (1,4),(4,5),(5,6),
    (6,7),(7,4)
])
nx.draw(G)
list(nx.bridges(G))

[(1, 4)]