Hamiltono maršrutas

Hamiltono maršrutas - maršrutas grafe, kuriuo galima pereiti visas jo viršūnes po vieną kartą. Jei tokiu maršrutu grįžtama į pradinę viršūnę, jis vadinamas Hamiltono ciklu, jei ne - Hamiltono keliu arba Hamiltono grandine. Pavadinimas kilo nuo pavardės matematiko Viljamo Rovano Hamiltono, 1857 m. sukūrusio žaidimą, kuriame reikėjo apeiti visas dodekaedro (tiksliau - jį atitinkančio grafo) viršūnes einant jo briaunomis.

Hamiltono ciklas grafe, atitinkančiame dodekaedrą

Egzistavimo sąlygos

Nėra žinoma jokios paprastos būtinos ir pakankamos Hamiltono maršruto egzistavimo sąlygos.

Taikymai

Uždavinys, kai pilnajame svoriniame grafe ieškoma minimalaus Hamiltono ciklo, vadinamas keliaujančio pirklio uždaviniu ir taikomas logistikoje.

Algoritmas Hamiltono ciklui rasti C++ kalba:

/* Paste your code here (You may delete these lines if not writing code) */ // Program to print Hamiltonian cycle #include<stdio.h> // Number of vertices in the graph #define V 5 void print(int soln[V]) { int i,j; printf("solution exists\n"); for(i=0;i<V;i++,printf("\n")) //for(j=0;j<V;j++) printf("%d ",soln[i]); printf("\n\n"); } int findcycle(int graph[V][V],int soln[],int pos,int c,int path[]) { if(c==V) return graph[pos][0]; int i; for(i=0;i<V;i++) { if(graph[pos][i] && soln[i]==0) { soln[i]=1,path[c]=i; if(findcycle(graph,soln,i,c+1,path)) return 1; soln[i]=0; } } return 0; } void hamCycle(int graph[V][V]) { int soln[V]={0},path[V]={0}; soln[0]=1; if(findcycle(graph,soln,0,1,path)) print(path); else printf("no soln\n"); } int main() { /* Let us create the following graph (0)--(1)--(2) | / \ | | / \ | | / \ | (3)-------(4) */ int graph1[V][V] = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 1}, {0, 1, 1, 1, 0}, }; // Print the solution hamCycle(graph1); /* Let us create the following graph (0)--(1)--(2) | / \ | | / \ | | / \ | (3) (4) */ int graph2[V][V] = {{0, 1, 0, 1, 0}, {1, 0, 1, 1, 1}, {0, 1, 0, 0, 1}, {1, 1, 0, 0, 0}, {0, 1, 1, 0, 0}, }; // Print the solution hamCycle(graph2); return 0; }

Išnašos

1. Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007

Vikiteka: Hamiltono maršrutas – vaizdinė ir garsinė medžiaga