跳转到内容

用户:Lfs92002/导出路径

维基百科,自由的百科全书
一条于超立方图英语Hypercube graph中长度为 4 的导出路径。在超立方图中寻找最长的导出路径被称为盒中蛇英语Snake-in-the-box问题。

图论领域里,导出路径是无向图G的一条路径,并且该路径同时为图 G导出子图。因此,导出路径可以被表示为一个 G的顶点序列,序列中相邻的两顶点在 G 中都有边连接;而序列中不相邻的两顶点在G中也没有边相互连接。导出路径有时也被称之为,在超立方图英语Hypercube graph中寻找最长的导出路径被称为盒中蛇英语Snake-in-the-box问题。

同样的,定义导出环是一个,并同时为为导出子图导出环也被称为无弦环(当环的长度大于等于四时)或是 孔(hole)。而一个反孔(antihole),则是对孔取补图

算法和复杂度

[编辑]

  [[Category:图论]]