题目翻译
查看原帖
题目翻译
1097314
封禁用户楼主2024/8/21 09:22

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

完全图是顶点成对相邻的简单图:有 nn 个顶点的未标记完全图记为 KnK_n。图中以 K5K_5 为例。

最后,图的分解是一个子图的列表,这样每个子图 边只出现在列表中的一个子图中。

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

2024/8/21 09:22
加载中...