找到“气泡"在图中 [英] Finding "bubbles" in a graph

问题描述

在游戏中，我们将一个描述为紧密相连的，充满了扇形和边缘的图形的Universe.偶尔会有小口袋，玩家称它们为气泡"，一小部分节点都通过单个节点访问网络的其余部分.在下图中，只能通过节点855才能访问扇区769、195、733、918和451.如果可以有效地保护855，则那些其他扇区是安全的.图表上的其他节点具有更多的边缘(紫色线)，并且在播放器术语中不是气泡".

在1000或5000节点的网络中，要找到这些子结构并不容易.但是我怀疑这个想法已经以某种方式在图论中得到了描述，因此很可能可以在networkx中进行搜索.

有人可以提出一种图论方法来系统地找到这样的结构吗?为了清楚起见，该图是有向图，但实际上几乎所有边缘最终都是双向的.边缘未加权.

解决方案

图论对您的气泡"没有定义，但定义类似-

In a game, we have a universe described as a strongly-connected graph full of sectors and edges. Occasionally there are small pockets, players call them 'bubbles', where a small group of nodes all access the rest of the network through a single node. In the graph below, sectors 769, 195, 733, 918, and 451 are all only reachable via node 855. If you can guard 855 effectively, then those other sectors are safe. Other nodes on the chart have more edges (purple lines) and aren't 'bubbles' in the player nomenclature.

In a 1000 or 5000-node network, it's not easy to find these sorts of sub-structures. But I suspect this idea is described in graph theory somehow, and so probably is searchable for in networkx.

Could anyone suggested a graph-theory approach to systematically find structures like this? To be clear the graph is a directed graph but almost all edges end up being bi-directional in practice. Edges are unweighted.

解决方案

Graph theory has no definitions for your "bubbles", but has the similar definition - bridges. Bridge is the edge, which removal increases the number of connected components. As you can see, it is exactly what you need. networkx has a bunch of algorithms to find bridges. Curiously enough, it is called bridges :)

Example:

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)]

这篇关于找到“气泡"在图中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！