哈密頓路徑
在圖論中，哈密顿路径（）是在無向圖或有向圖中，恰好能將圖中所有頂點各拜訪一次的路徑。與之相近的概念為哈密顿环（），即該路徑在拜訪完圖中所有頂點後會回到出發點，而構成一個環。要確定圖中是否存在哈密顿路徑或哈密顿環的問題稱為哈密顿路径问题，這個問題是一個NP完全的問題。哈密顿路徑有時會跟尤拉路徑一起討論，因為哈密顿路徑要求通過所有頂點（哈密顿路径问题）而尤拉路徑要求通過所有邊（一筆畫問題）。 定義 哈密顿路徑是一個拜訪過某圖所有頂點的路徑，…
标签：#图论对象
共 3 篇文章
分團覆蓋問題
在計算複雜度理論內，找一個最小的分團覆蓋（clique cover）是一個圖論的NP完全問題。這問題屬於卡普的二十一個NP-完全問題之一，由卡普在1972年的論文"Reducibility Among Combinatorial Problems"證明為NP完全。 分團覆蓋問題（有時叫做分成分團，partition into cliques）是問一個圖裡面的所有點可否分成k個分團。一旦給定了這個圖該怎麼分成k個分團，我們可以在多項式時間…
哈密顿图
又稱漢密頓圖，是指存在哈密頓環的無向圖，由哈密顿爵士提出。 定義 下列定義，既適用於無向圖，亦適用於有向圖。 ;哈密頓路徑:圖的一條路，經過每個頂點恰好一次。 ;哈密頓環:在一條哈密頓路的基礎上，再有一條邊將其首尾連接，所構成的圈。注意，若有一個哈密頓圈，則移除其任一條邊，皆可得到一條哈密頓路，但反之則不然，即給定一條哈密頓路，不一定能延伸成哈密頓圈，因為該路徑的首尾兩頂點之間，不一定有邊相連。 ;哈密頓圖:有哈密頓圈的圖。 ;半哈密頓…