极大全连通子图

定义

  • 连通图: 图中任意两点均是可达的。
  • 子图: 一个图的一部分。
  • 全连通图:一个图中的每个点与图中任意其他点均有边连接。
  • 极大全连通子图: 在全连通子图上添加图上其他任意一点，均破坏其全连通性质。

问题

给一个连通图,找出其中所有的极大全连通子图，如下图中 {1,2,3},{3,4},{4,5}都是极大全连通子图。
图一

初步想法

从一个点开始遍历，扩展全连通子图，直至不能继续扩展。同时将访问过的边标记为已访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
while (!isEmpty(vertexList)){
	Vertex cur = vertexList.peek();
	Queue maxSubG = new LinkedList<Vertex>();
	maxSubG.add(cur);
	//极大连通子图最少两个点
	if (isEmpty(cur.Edges())) continue;
	Vertex other = cur.Edges.poll().other(cur);
	removeEdge(cur, other);
	for (Vertex neighbour : cur.Edges()){
		int cnt = 0;
		int common = 0;
		for (Vertex nn: neighbour.Edges()){
			if (maxSubG.contains(nn)){
				common ++;
			}
			if (nn == cur || nn == other){
				cnt++; 
			}
			if (cnt >=2 ) break;
		}
		if (cnt == 2 && common == maxSubG.size()){
			maxSubG.add(neighbour);
			removeEdge(neighbour, cur);
			removeEdge(neighbour, other);
		}
	}
}

Bad case

见下图，如果我们用上述的方法可能会漏掉{1，3，4}这个极大连通子图，而误将{1,4}看做一个极大连通子图。
图二

下面我们就要开始着手解决这个问题。首先我们可以发现极大连通子图至少有一条边，这提示我们是否可以按照边而不是顶点来进行遍历呢？其次，我们观察造成我们遗漏{1,3,4}这个子图的罪魁祸首是{1,3}和{3,4}这两条边被错误的删除了。注意到删除{1,3}时，{1,3}除了2以外，还有另一个可扩展的点4，所以其还有利用价值，不能直接删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while (!isEmpty(edgeList)){
	Edge init = edgeList.peek();
	Set<Vertex> maxSubG = new Set<Vertex>();
	Vertex one = init.one();
	Vertex other = init.other();
	maxSubG.add(one);
	maxSubG.add(other);
	for (Edge e : union(one.edges(), other.edges()){
		Set<Vertex> common = intersect(e);
		if (intersect(common, maxSubG).size() = maxSubG.size()){
			maxSubG.add(e.other(one));
			if (common.size() == maxSubG.size()){
				edgeList.remove(e);
			}
		}
	}
	if (intersect(init).size() == maxSubG.size()){
		edgeList.remove(init);
	}
}

评论