Hamiltono maršrutas
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
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.
Nėra žinoma jokios paprastos būtinos ir pakankamos Hamiltono maršruto egzistavimo sąlygos.[1]
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;
}
|
