迈谢尔斯基#
- 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)\) 到Mmycielski操作可以通过重复上述过程多次完成。
更多信息请访问https://en.wikipedia.org/wiki/mycielskian
- 参数
- G图表
简单的无向网络X图
- iterations集成
要对G执行的Mycielski运算的迭代次数默认为1。必须是非负整数。
- 返回
- M图表
指定迭代次数后G的Mycielskian。
笔记
图形、节点和边缘数据不必传播到新图形。