寻找割点组

Question

我有一些无向图，想要找到关键节点。以下是一个示例：

它有一个关节点 - 顶点#2。

但我还想找到#4和#5作为关节组点。因为移除#4，#5的连接也会将图形切割成不相连的子图。我将示例图像想象为3个相连的子图。

我该如何找到特定的切点？

- user1312837

---

切点组是否还有其他条件？ 因为这样的组可能会非常多。例如(1, 14), (0, 1, 15), (6, 9), (11, 7, 8, 9)，……我认为它们甚至可以呈指数级增长。 - Jakube

我认为这取决于这些群组的大小。切点应该将大型节点集群分开。 - user1312837

你需要更具体一些。什么是“大”？为什么4-5是可以接受的，而6-9不行？ - FrankS101

根据您提供的信息，我认为没有比检查所有可能的组更好的解决方案。首先要做的是严格定义“组”的含义。在定义中留下变量是可以的，但允许的限制越多（例如，它们必须是给定最大大小的子树的节点），就增加了高效算法的可能性。否则，我确信您可以在选择中编码一个SAT问题，这将使问题成为NP难问题，这意味着没有运行时间指数与最大组大小。我会把证明留给您。 - Gene

Answer 1

我认为除了遍历所有组合以外，没有其他更快的方法，因为您没有任何限制。（我甚至不认为这个测试有意义。）

尽管编程语言未指定，请允许我以Python为例。

当您正在进行关节点搜索时，最著名的方法是Tarjan算法。我认为每个阅读此文的人都知道它，所以如果您不介意，我将跳过它作为一个函数，您可以在https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/中找到它。

class Graph:
   #From www.geeksforgeeks.org
def worker(g, prefix, arr, u):

    container = g.graph[u]
    if u in g.AP():
        print prefix
        arr.append([prefix])
        del g
    else:
        for i in container:
            if str(i) not in prefix.split(' '):
                new_prefix = prefix + ' ' + str(i)
                new_g = copy.deepcopy(g)
                new_g.combineNode(u, i)
                if len(new_g.graph) > 1:
                    worker(new_g, new_prefix, arr, i)

struct = {
    0:[1,12,13,14,15],
    1:[2,12,14,15],
    2:[3,4,5,14],
    3:[4],
    4:[5,6],
    5:[6,9],
    6:[7,8,9],
    7:[8,10,11],
    8:[9,10,11],
    9:[10],
    10:[11],
    12:[15],
    13:[14,15]
} 
g1 = Graph (total)

for key,value in struct.iteritems():
    for child in value:
        g1.addEdge(key, child)

result = []
for i in range(0, total):
    print 'Remove root ' + str(i)
    worker(g1, str(i), result, i)
print result

我写这篇文章是为了仅需要将图形分成最小长度的组。比如说(4,5)，如果它已经是AP，任何点连接到它们也应该是AP。

以防万一，如果有人想要完整的测试代码。https://gist.github.com/MichaelKHTai/c438fd0911d0584be1e37f1fd1599b7e 此外，应通过跳过重复的节点组进行优化，例如(4,5)和(5,4)。

- MT-FreeHK

Answer 2

一种方法是找到你的图形的“2-连通分量”。

2-连通图是指连接的图形，且不包含任何关节点。

任何简单图的边都可以分成一些2-连通子图。

第一个例子：

在上图中，以下是2-连通分量：

• 4–2 3–4 3–1 2–3 1–2
• 8–9
• 8–5 7–8 5–7
• 6–0 5–6 1–5 0–1
• 10–11

第二个例子：

每种颜色对应一个2连通分量。多色顶点是割点（关节点），因此属于多个2连通分量。

我认为每个分量都是您问题的答案。您可以使用Tarjan算法来查找这些分量。其时间复杂度为O（|V| + |E|）或O（n + m）。

time = 0
function DFS(vertex, adj[][], low[], disc[], parent[], visited[], V, stack)
    disc[vertex]=low[vertex]=time+1
    time = time + 1
    visited[vertex]=true
    child = 0
    for i = 0 to V
        if adj[vertex][i] == true
            if visited[i] == false
                child = child + 1
                push edge(u,v) to stack
                parent[i] = vertex
                DFS(i, adj, low, disc, visited, V, time, stack)
                low[vertex] = minimum(low[vertex], low[i])
                if parent[vertex] == nil AND child > 1
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
                if parent[vertex] != nil AND low[i] >= disc[vertex]
                    while last element of stack != (u,v)
                        print last element of stack
                        pop from stack
                    print last element of stack
                    pop from stack
            else if parent[vertex] != i AND disc[i] < low[vertex]
                low[vertex] = disc[i]
                push edge(u,v) to stack

fuction biconnected_components(adj[][], V)
    for i = 0 to V
        if visited[i] == false
            DFS(i, adj, low, disc, parent, visited, V, time, stack)
            while stack is not empty
                print last element of stack
                pop from stack 

来源：

https://www.geeksforgeeks.org/biconnected-components/

https://en.wikipedia.org/wiki/Biconnected_component

https://www.hackerearth.com/practice/algorithms/graphs/biconnected-components/tutorial/

- Erfan Alimohammadi