mycielskian

mycielskian(G, iterations=1)

返回简单无向图 G 的 Mycielskian

图的 Mycielskian 保持了图的无三角形属性，同时将色数增加 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\)，将边 \((u, v), (u, v + n)\) 和 \((u + n, v)\) 添加到 M 中。最后，对于所有顶点 \(u \in U\)，将边 \((u, w)\) 添加到 M 中。

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

更多信息可以在以下链接找到 https://en.wikipedia.org/wiki/Mycielskian

参数:

G图

一个简单的无向 NetworkX 图

iterationsint

在 G 上执行 Mycielski 操作的迭代次数。默认为 1。必须是非负整数。

返回:

M图

经过指定迭代次数后 G 的 Mycielskian。

注意

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