跳转到内容

User:Lfs92002/導出路徑

维基百科,自由的百科全书
一條於超立方圖英语Hypercube graph中長度為 4 的導出路徑。在超立方圖中尋找最長的導出路徑被稱為盒中蛇英语Snake-in-the-box問題。

圖論領域裡,導出路徑是無向圖G的一條路徑,並且該路徑同時為圖 G導出子圖。因此,導出路徑可以被表示為一個 G的頂點序列,序列中相鄰的兩頂點在 G 中都有邊連接;而序列中不相鄰的兩頂點在G中也沒有邊相互連接。導出路徑有時也被稱之為,在超立方圖英语Hypercube graph中尋找最長的導出路徑被稱為盒中蛇英语Snake-in-the-box問題。

同樣的,定義導出環是一個,並同時為為導出子圖導出環也被稱為無弦環(當環的長度大於等於四時)或是 孔(hole)。而一個反孔(antihole),則是對孔取補圖

演算法和複雜度

[编辑]

  [[Category:图论]]