本質(zhì)上是有哈密頓路和哈密頓圈的問題
Direr 1952年的定理n>=3個頂點的圖最小度數(shù)大于n/2則有哈密頓圈沒有啊，我看書上是任意兩點度數(shù)之和大于n-1則有哈姆頓路，大于n則有哈姆敦圖，可是如何得到n-1 與n，只能得到n-2??？這是圖論中的定理你那個定理也可以兩個認識的人之間連線，每人連出去n-2，兩個人之和2n-4，當n>3時2n-4>=n，當n=3時2n-4>=n-1我寫錯題了,是任意兩人合起來認識其他n-2人,這該如何解決?1. n=3時一定有哈密頓路是顯然的2. n>3用數(shù)學(xué)歸納法可證 一定有哈密頓路3. 下證n>3時一定有哈密頓圈根據(jù)題目至少有一對頂點相鄰（否則圖不連通，不可能滿足題意），因為任意兩人認識其余n-2個人，所以從這對頂點各自出發(fā)，可連結(jié)到一對不相同的頂點（因為n>=4）。然后從這對不相同的頂點出發(fā)做上面相同的事（但要排除前面用過的頂點），做到不能做為止（即兩個頂點連接相同頂點），于是最早兩隊頂點相鄰邊加上做出來這條路，組成哈密頓圈。