mycielskian

mycielskian(G, iterations=1)

返回一个简单无向图 G 的 Mycielski 图

Mycielski 图保持了原图的无三角形特性，同时将色数增加 1。

对图 \(G=(V, E)\) 进行 Mycielski 操作，构造一个新图，该图有 \(2|V| + 1\) 个节点和 \(3|E| + |V|\) 条边。

构造过程如下：

设 \(V = {0, ..., n-1}\) 。构造另一个顶点集 \(U = {n, ..., 2n}\) 和一个顶点 w 。 构造一个新图 M ，其顶点为 \(U \bigcup V \bigcup w\) 。 对于边 \((u, v) \in E\) ，在 M 中添加边 \((u, v), (u, v + n)\) 和 \((u + n, v)\) 。最后，对于所有顶点 \(u \in U\) ，在 M 中添加边 \((u, w)\) 。

Mycielski 操作可以多次进行，通过迭代重复上述过程。

更多信息请参见 https://en.wikipedia.org/wiki/Mycielskian

Parameters:

G图

一个简单的无向 NetworkX 图

iterationsint

对 G 进行 Mycielski 操作的迭代次数。默认为 1。必须是一个非负整数。

Returns:

M图

经过指定迭代次数后的 G 的 Mycielski 图

Notes

图、节点和边数据不一定传播到新图中。