求证,玄关!!!
  • 板块灌水区
  • 楼主Hanrui1206
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/23 16:31
  • 上次更新2024/7/23 16:34:49
查看原帖
求证,玄关!!!
1283944
Hanrui1206楼主2024/7/23 16:31

设 V(G)V(G) 是一个简单图的顶点集,E(G)E(G) 为其边集。从简单图 GG 到简单图 HH 的同构是双射 V(G)→V(H)V(G) \to V(H) 使得 V∈E(G)V \in E(G) 当且仅当 f(u)f(v)∈E(H)f(u)f(v) \in E(H)。我们说,GG 同构于 HH,如果存在从 GG 到 HH 的同构。

最后,图的分解是子图的列表,使得每条边恰好出现在列表中的一个子图中。

现在,给定一个正整数 nn,你要确定 knk_n 是否分解成三个成对同构的子图。

求大佬证明:

  1. 在 N mod 3=0N \bmod 3 = 0 时,可以构造 33 个同构图,顶点数依次为 K−1,K,K+1K−1,K,K+1。
  2. 在 N mod 3=1N \bmod 3 = 1 时,也可以构造出三个同构图。
  3. 当 N mod 3=2N \bmod 3 = 2 时,无论怎样都无法构造出三个同构图。
2024/7/23 16:31
加载中...