Hamiltono maršrutas
(Nukreipta iš puslapio Hamiltono ciklas)
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.
Egzistavimo sąlygos
redaguotiNėra žinoma jokios paprastos būtinos ir pakankamos Hamiltono maršruto egzistavimo sąlygos.[1]
Taikymai
redaguotiUž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
redaguoti- ↑ Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007