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.

 Egzistavimo sąlygos 
Nėra žinoma jokios paprastos būtinos ir pakankamos Hamiltono maršruto egzistavimo sąlygos.Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007

 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 

Kategorija:Grafų teorija