社区讨论

【悬4关】黑丝妹子发出了四个关于点双的疑问

CChatSheep
P8435【模板】点双连通分量参与者 13已保存回复 30

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
29 条
当前快照
1 份
快照标识符
@lu80ejr7
此快照首次捕获于
2024/03/26 14:42
2 年前
此快照最后确认于
2024/03/26 14:59
2 年前
查看原帖
定义一个无向图 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. 不是割点的点是否仅出现在一个点双中？逆命题是否成立？
求证~

回复

共 30 条回复，欢迎继续交流。

正在加载回复...