【悬4关】黑丝妹子发出了四个关于点双的疑问
查看原帖
【悬4关】黑丝妹子发出了四个关于点双的疑问
726525
CuteChat楼主2024/3/26 14:40

定义一个无向图 G=(V,E)G=(V,E),其中,定义割点点集 DD 为无向图 GG 中割点的个数,再定义 SS 为这个图中,所有“点双中的点组成的集合”的集合。

例如 V={1,2,3,4},E={1−2,2−3,3−1,3−4V=\{1,2,3,4\},E=\{1-2,2-3,3-1,3-4,{1,2,3}\{1,2,3\} 是一个“点双中的点组成的集合”,{3,4}\{3,4\} 是一个“点双中的点组成的集合”,所以 S={{1,2,3},{3,4}}S=\{\{1,2,3\},\{3,4\}\}。

现在有四个问题。

  1. ∀x∈D\forall x\in D,是否有 ∑t∈S[x∈t]≥2\displaystyle\sum_{t\in S}[x\in t] \ge 2?
  2. 如果 ∑t∈S[x∈t]≥2\displaystyle\sum_{t\in S}[x\in t] \ge 2,那么 x∈Dx\in D 吗?
  3. ∀x∉D\forall x\notin D,是否有 ∑t∈S[x∈t]=1\displaystyle\sum_{t\in S}[x\in t] = 1?
  4. 如果 ∑t∈S[x∈t]=1\displaystyle\sum_{t\in S}[x\in t] = 1,那么 x∉Dx\notin D 吗?

说人话就是:

  1. 一个割点是否出现在至少两个点双中?逆命题是否成立?
  2. 不是割点的点是否仅出现在一个点双中?逆命题是否成立?

求证~

2024/3/26 14:40
加载中...