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.

Hamiltono ciklas grafe, atitinkančiame dodekaedrą

Egzistavimo sąlygos

redaguoti

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

Taikymai

redaguoti

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

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