贪心和最优，各要几个点

一张七个点的图（顶点覆盖：挑最少的点，让每条边至少有一头被挑中）。贪心和暴力最优各挑了几个点？

from itertools import combinations

E = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (4, 6)]
V = [0, 1, 2, 3, 4, 5, 6]

def greedy_vc(edges):
    """贪心：挨个看边，两头都没被盖住就把两头都收进来"""
    cover, used = [], set()
    for a, b in edges:
        if a not in used and b not in used:
            cover += [a, b]
            used |= {a, b}
    return sorted(cover)

def opt_vc(edges, vs):
    """暴力：从小到大试每一种规模，第一个能盖住所有边的就是最优"""
    for k in range(len(vs) + 1):
        for c in combinations(vs, k):
            s = set(c)
            if all(a in s or b in s for a, b in edges):
                return sorted(s)
    return sorted(vs)

print(str(len(greedy_vc(E))) + "/" + str(len(opt_vc(E, V))))