定义一个无向图 G=(V,E),其中,定义割点点集 D 为无向图 G 中割点的个数,再定义 S 为这个图中,所有“点双中的点组成的集合”的集合。
例如 V={1,2,3,4},E={1−2,2−3,3−1,3−4,{1,2,3} 是一个“点双中的点组成的集合”,{3,4} 是一个“点双中的点组成的集合”,所以 S={{1,2,3},{3,4}}。
现在有四个问题。
- ∀x∈D,是否有 t∈S∑[x∈t]≥2?
- 如果 t∈S∑[x∈t]≥2,那么 x∈D 吗?
- ∀x∈/D,是否有 t∈S∑[x∈t]=1?
- 如果 t∈S∑[x∈t]=1,那么 x∈/D 吗?
说人话就是:
- 一个割点是否出现在至少两个点双中?逆命题是否成立?
- 不是割点的点是否仅出现在一个点双中?逆命题是否成立?
求证~