设 V(G) 是一个简单图的顶点集,E(G) 为其边集。从简单图 G 到简单图 H 的同构是双射 V(G)→V(H) 使得 V∈E(G) 当且仅当 f(u)f(v)∈E(H)。我们说,G 同构于 H,如果存在从 G 到 H 的同构。
最后,图的分解是子图的列表,使得每条边恰好出现在列表中的一个子图中。
现在,给定一个正整数 n,你要确定 kn 是否分解成三个成对同构的子图。
求大佬证明:
- 在 Nmod3=0 时,可以构造 3 个同构图,顶点数依次为 K−1,K,K+1。
- 在 Nmod3=1 时,也可以构造出三个同构图。
- 当 Nmod3=2 时,无论怎样都无法构造出三个同构图。