如何筛选图顶点组合列表：移除含相邻顶点的组合

给定含5个顶点的图，顶点集合 v = [0,1,2,3,4]，已生成所有顶点的组合列表（包含空组合、单顶点、多顶点组合），同时给定边集合：

[(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]

需要剔除所有包含任意一条边中两个顶点的组合（比如包含0和3的所有组合都要被剔除）。现有生成所有组合的代码如下：

list_combinations = list()
for n in range(len(N_vert) + 1):
    list_combinations += list(combinations(vert, n))    
    n_comb = len(list_combinations)

请编写条件判断代码，验证某个组合中是否存在两个相邻顶点（即该组合包含某条边的两个端点）。

核心思路 #

判断组合是否包含相邻顶点，本质是检查该组合的任意两个顶点是否构成给定边集合中的某条边。为避免因顶点顺序漏判，先将边集合转换为无序对的集合，再遍历组合的所有2元素子组合，检查是否存在于边集合中。

具体实现 #

1. 预处理边集合

把原始边集合转换成排序后的元组集合，统一无向边的表示形式：

edges = [(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]
# 转换为排序后的元组集合，消除顶点顺序影响
edge_set = set(tuple(sorted(edge)) for edge in edges)

2. 过滤有效组合

有两种实现方式，按需选择：

方式一：生成组合时直接过滤

在生成组合的过程中，直接跳过包含相邻顶点的组合：

from itertools import combinations

vert = [0,1,2,3,4]
edges = [(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]
edge_set = set(tuple(sorted(e)) for e in edges)

valid_combinations = []
for n in range(len(vert) + 1):
    for comb in combinations(vert, n):
        has_adjacent = False
        # 遍历当前组合的所有2元素子组合
        for pair in combinations(comb, 2):
            if tuple(sorted(pair)) in edge_set:
                has_adjacent = True
                break
        if not has_adjacent:
            valid_combinations.append(comb)

# 输出符合要求的组合
print(valid_combinations)

方式二：对已生成的组合列表过滤

如果已经生成了list_combinations，可以用filter函数配合判断规则筛选：

from itertools import combinations

# 假设list_combinations已经生成
edges = [(0, 3), (1, 2), (2, 3), (2, 4), (3, 4)]
edge_set = set(tuple(sorted(e)) for e in edges)

# 判断函数：组合中无相邻顶点则返回True
def is_valid_combination(comb):
    for pair in combinations(comb, 2):
        if tuple(sorted(pair)) in edge_set:
            return False
    return True

# 过滤得到有效组合
valid_combinations = list(filter(is_valid_combination, list_combinations))

说明 #

• 转换边为排序元组集合：解决了无向边的顺序问题，比如(0,3)和(3,0)会被统一识别为同一个边。
• 遍历2元素子组合：确保不会遗漏组合中任何可能的相邻顶点对，只要存在一对属于边集合，该组合就会被剔除。

内容的提问来源于stack exchange，提问作者Goncalo Freitas