问题
团与最大团的定义
图顶点集的子集满足任意两个顶点相邻,称该子集是该图的一个团。图的所有团中顶点最多的,即最大的一个或多个,称为图的最大团或极大团。
图的最大团的实际应用问题
CVPR2023最佳论文之一用最大团算法实现鲁棒的点云对准,有效解决外点问题。顾名思义有矛盾:点云对准,即3D-3D点匹配,是各自独立的关联,最大团中顶点是两两关联,乍一看最大团算法无法适用。原论文作者们将候选匹配点对作为图的顶点,顶点相邻关系被定义为匹配点对之间满足匹配一致性约束,两帧点云中有两对匹配点
x
−
x
′
x-x^{\prime}
x−x′、
y
−
y
′
y-y^{\prime}
y−y′,如设一致性约束为距离阈值d
a
b
s
(
∣
∣
x
−
y
∣
∣
−
∣
∣
x
′
−
y
′
∣
∣
)
<
d
abs(||x-y||-||x^{\prime}-y^{\prime}||)< d
abs(∣∣x−y∣∣−∣∣x′−y′∣∣)<d
如何求图的最大团?
求解图最大团
启发式思路:遍历顶点,对每个顶点查找其相邻顶点,构建初始团,遍历该团的顶点,对其相邻顶点,若已经在团内的跳过,判断可否加入团,保存极大团;比较各次结果的大小。
例,
Python代码实现
# 检查重复的团
def isNotRepeat(all, a):
for i in all:
s = set(i)
sa = set(a)
if sa.issubset(s):
return False
return True
def findMaxClique(graph):
print("Start")
clique_set = []
# 遍历该团的顶点,
for a in graph.keys():
# 遍历顶点,对每个顶点查找其相邻顶点,构建初始团
cli_can = [a, graph[a][random.randrange(0, len(graph[a]))]]
# 跳过已经被结果中的某个团包含的种子团
if isNotRepeat(clique_set, cli_can):
for i in cli_can:
# 对其相邻neighbour顶点,若已经在团内的跳过,判断可否加入团,
nb = graph[i]
for j in nb:
if j in cli_can:
continue
else:
is_memb = True
for ii in cli_can:
if j not in graph[ii]:
is_memb = False
break
if is_memb:
cli_can.append(j)
clique_set.append(cli_can)
n_max = 0
mc = None
# 比较各个团的大小。
for c in clique_set:
num = len(c)
if num > n_max:
n_max = num
mc = c
return mc
if __name__ == "__main__":
Gc = {
1: [2, 5],
2: [1, 3, 4, 5, 6],
3: [2, 4, 6],
4: [2, 3, 5, 6],
5: [1, 2, 4],
6: [2, 3, 4],
}
print("Max Clique Problem")
print(findMaxClique(Gc))
BronKerbosch算法
标签:__,prime,图论,set,cli,graph,算法,点云,顶点 From: https://blog.csdn.net/CSUzhangpeike/article/details/136643138