用户:Lfs92002/导出路径
外观
在图论领域里,导出路径是无向图G的一条路径,并且该路径同时为图 G 的导出子图。因此,导出路径可以被表示为一个 G的顶点序列,序列中相邻的两顶点在 G 中都有边连接;而序列中不相邻的两顶点在G中也没有边相互连接。导出路径有时也被称之为蛇,在超立方图(英语:Hypercube graph)中寻找最长的导出路径被称为盒中蛇(英语:Snake-in-the-box)问题。
同样的,定义导出环是一个环,并同时为为导出子图。导出环也被称为无弦环(当环的长度大于等于四时)或是 孔(hole)。而一个反孔(antihole),则是对孔取补图。
[[Category:图论]]