Peržiūrėti šaltinį Hamiltono maršrutas

[[Vaizdas:Hamiltonian_path.svg|thumb|Hamiltono ciklas grafe, atitinkančiame [[dodekaedras|dodekaedrą]]]]
'''Hamiltono maršrutas''' - maršrutas [[grafas (matematika)|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 [[William Rowan Hamilton|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.<ref>Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007</ref>

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

Algoritmas Hamiltono ciklui rasti C++ kalba:

<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><table><tr><td><pre style="margin: 0; line-height: 125%"> 

 /* 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;
}
</pre></td></tr></table></div>


== Išnašos ==
{{Išn}}

{{Commonscat|Hamiltonian paths}}

{{mat-stub}}

[[Kategorija:Grafų teorija]]