迈谢尔斯基

mycielskian(G, iterations=1)

返回简单无向图g的MyCielskian

图的Mycielskian保持了图的无三角形性质，同时增加了色数1。

图表上的mycielski操作， \(G=(V, E)\) ，构造一个新的图表 \(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)\) 最后，对于所有顶点 \(u \in U\) 添加边缘 \((u, w)\) 到M

mycielski操作可以通过重复上述过程多次完成。

更多信息请访问https://en.wikipedia.org/wiki/mycielskian

参数

G图表

简单的无向网络X图

iterations集成

要对G执行的Mycielski运算的迭代次数默认为1。必须是非负整数。

返回

M图表

指定迭代次数后G的Mycielskian。

笔记

图形、节点和边缘数据不必传播到新图形。