關于路 鏈 哈密頓回路的點點滴滴

1、關于路 鏈 哈密頓回路的點點滴滴具有n個節(jié)點的賦權網絡,有許多話題,除路 鏈哈密頓回路外,還有最小樹,最大流等等,無非都是問如何才能最多最快最好最省;具有n個節(jié)點的賦權網絡,分為對稱與非對稱即無向與有向,前者對應一個n階對稱陣a(ai,j=aj,i),后者對應一個n階非對稱陣a(至少有一次ai,j!=aj,i);它們的對角線上的元素均為0;指定起點與終點的最短路,其中間點可有可無,中間點多少不限,該問題有很好的解法;指定起點與終點的最短鏈,其中間點當然只能是n-2個,這時,若是非對稱的,所有鏈是(n-2)!條,若是對稱的,所有鏈是(n-2)!/2條;對于不指定起點與終點的最

2、短鏈,鏈中的節(jié)點是n個,這時,若是非對稱的,所有鏈是(n)!/2條,若是對稱的,所有鏈是(n)!/2條;對于哈密頓回路不存在指定起點與終點的問題,這時,若是非對稱的,所有回路是(n-1)!條,若是對稱的,所有回路是(n-1)!/2條;最短鏈與最小哈密頓回路都沒找到較好的解法;當n不太大,可由枚舉法求解;最小哈密頓回路的幾個簡單例子:最小H回路問題 最小H回路原始數據: 0113171311013610101207131116160161171560最小H回路路長: 37最小H回路: 4 0 2 3 1 4最小H回路原始數據: 0120855061519141102317151001217617

3、80最小H回路路長: 32最小H回路: 4 1 0 3 2 4最小H回路原始數據: 05518111701813108110103620707981240最小H回路路長: 34最小H回路: 4 3 2 0 1 4最小H回路原始數據: 0810134200191515730116321601288850最小H回路路長: 33最小H回路: 4 2 1 3 0 4最小H回路原始數據: 071215131401921813200591920142191180最小H回路路長: 22最小H回路: 4 0 1 3 2 4最小H回路原始數據: 061512560189319140131111512010161

4、415160最小H回路路長: 38最小H回路: 4 2 3 0 1 4最小H回路原始數據: 086214031418175031361101613515120最小H回路路長: 15最小H回路: 4 1 2 3 0 4最小H回路原始數據: 01115201220111141290191920135020181614190最小H回路路長: 46最小H回路: 4 1 3 2 0 4最小H回路原始數據: 0171812514014137360817669010351110最小H回路路長: 29最小H回路: 4 3 1 2 0 4最小H回路原始數據: 03751013905161815148014174

5、13730753310130353813110最小H回路路長: 29最小H回路: 5 0 3 4 1 2 5最小H回路原始數據: 0417116208021019320130121615841402713431901419314180最小H回路路長: 25最小H回路: 5 0 1 2 3 4 5最小H回路原始數據: 0329132001482918020241661012111010920311158880最小H回路路長: 24最小H回路: 5 0 1 3 2 4 5最小H回路原始數據: 05181682050712363200162012587011512188150171920218120

6、最小H回路路長: 40最小H回路: 5 2 0 1 3 4 5最小H回路原始數據: 02017181110200191918151620314142141304817201317014101191140最小H回路路長: 44最小H回路: 5 3 0 4 2 1 5最小H回路原始數據: 0182047114081016111612013116101750191917101050109101316200最小H回路路長: 34最小H回路: 5 1 0 3 2 4 5最小H回路原始數據: 01221294706135691012259315013161814152001017172160最小H回路路長: 26最小H回路: 5 3 1 0 2 4 5最小H回路原始數據: 01221294706135691012259315013161814152001017172160最小H回路路長: 26最小H回路: 5 3 1