Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Hamiltono maršrutas maršrutas grafe kuriuo galima pereiti visas jo viršūnes po vieną kartą Jei tokiu maršrutu grįžtama į
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.
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
- Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Hamiltono maršrutas, Kas yra Hamiltono maršrutas? Ką reiškia Hamiltono maršrutas?
Hamiltono marsrutas marsrutas grafe kuriuo galima pereiti visas jo virsunes po viena karta Jei tokiu marsrutu grįztama į pradine virsune jis vadinamas Hamiltono ciklu jei ne Hamiltono keliu arba Hamiltono grandine Pavadinimas kilo nuo pavardes matematiko Viljamo Rovano Hamiltono 1857 m sukurusio zaidima kuriame reikejo apeiti visas dodekaedro tiksliau jį atitinkancio grafo virsunes einant jo briaunomis Hamiltono ciklas grafe atitinkanciame dodekaedraEgzistavimo salygosNera zinoma jokios paprastos butinos ir pakankamos Hamiltono marsruto egzistavimo salygos TaikymaiUzdavinys kai pilnajame svoriniame grafe ieskoma minimalaus Hamiltono ciklo vadinamas keliaujancio pirklio uzdaviniu 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 lt stdio h gt 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 lt V i printf n for j 0 j lt 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 lt V i if graph pos i amp amp 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 IsnasosKostas Plukas Eugenijus Macikenas Birute Jarasiuniene Irena Mikuckiene Taikomoji diskrecioji matematika Kaunas Technologija 2007 Vikiteka Hamiltono marsrutas vaizdine ir garsine medziaga Sis su matematika susijes straipsnis yra nebaigtas Jus galite prisideti prie Vikipedijos papildydami sį straipsnį