关于路 链 哈密顿回路的点点滴滴

1、关于路链哈密顿回路的点点滴滴具有n个节点的赋权网络,有许多话题,除路 链哈密顿回路外,还有最小树,最大流等等,无非都是问如何才能最多最快最好最省;具有n个节点的赋权网络,分为对称与非对称即无向与有向,前者对应一个n阶对称阵a(ai,j=aj,i),后者对应一个n阶非对称阵a(至少有一次ai,j!=aj,i);它们的对角线上的元素均为0;指定起点与终点的最短路,其中间点可有可无,中间点多少不限,该问题有很好的解法;指定起点与终点的最短链,其中间点当然只能是n-2个,这时,若是非对称的,所有链是(n-2)!条,若是对称的,所有链是(n-2)!/2条;对于不指定起点与终点的最短链,链中的节点是n个,

2、这时,若是非对称的,所有链是(n)!/2条,若是对称的,所有链是(n)!/2条;对于哈密顿回路不存在指定起点与终点的问题,这时,若是非对称的,所有回路是(n-1)!条,若是对称的,所有回路是(n-1)!/2条;最短链与最小哈密顿回路都没找到较好的解法;当n不太大,可由枚举法求解;最小哈密顿回路的几个简单例子:最小H回路问题 最小H回路原始数据: 0113171311013610101207131116160161171560最小H回路路长: 37最小H回路: 4 0 2 3 1 4最小H回路原始数据: 012085506151914110231715100121761780最小H回路路长: 3

3、2最小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回路原始数据: 061512560189319140131111512010161415160最小H回路路

4、长: 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回路原始数据: 03751013905161815148014174137307533101

5、30353813110最小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最小H回路路长: 40最

6、小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 0