Hamiltondar bide

Grafoen teorian, grafo batean hamiltondar bidea zirkuitu bat da (hau da, alboko ertz-segida bat), grafoaren erpin guztiak behin bakarrik bisitatzen dituena. Gainera, bisitatutako lehen eta azken erpinak bat egiten badute, bidea ziklo hamiltondarra da.

Grafo arbitrario batean ziklo (edo bide) hamiltondar bat aurkitzea NP-osoa dela jakina da eta beraz, 21 Karp arazoen zerrendan agertzen da.
eskuinera|thumb|250x250px|Ziklo hamiltondarren hiru adibide 8x8 sareta karratuko grafiko batean.
Sir William Rowan Hamilton (1805-65) matematikari irlandarretik dator izena, zeinak munduko hogei hiritara bidaiatzea proposatu zuen, dodekaedro erregular baten erpinak bezala irudikatuak, dodekaedroaren ertzei jarraituz.

Hala ere, gaur egun hamiltondar deritzen zikloak eta bideak, askoz lehenago agertu ziren. Dirudienez, IX. mendean, Rudrata koplari indiarrak zaldiaren bidea deiturikoa aipatzen du. Zaldiaren mugimendu segida bat da, taula baten gainean, pieza honek laukitxo guzti-guztiak behin bakarrik bisita ditzan. Beraz, grafo batean bide hamiltondar bat aurkitzea, zeinaren erpinak taula baten laukitxoak baitira, halako moldez non bi erpin elkarren ondoan dauden, baldin eta batetik bestera zaldi mugimendu baten bidez igaro badaiteke.

 Definizioa 

 Grafoaren erpin guztiak zeharkatzen dituen erpin errepikaturik gabeko bide bati hamiltondar bidea deitzen zaio.
 Zirkuitu bat den bide hamiltondar bati zirkuitu hamiltondarra deritzo.
 Zirkuitu hamiltondarra duen grafo bati grafo hamiltondarra deitzen zaio.

Grafo zuzenduentzat, edo digrafoentzat, dagozkien definizioek kontuan hartzen dute ertzak zuzenduak daudela.

 Grafo zuzendu batean zuzendutako bidea hamiltondar zuzendutako bidea da, digrafoaren erpin guztiak zeharkatzen baditu, bat ere errepikatu gabe.
 Zirkuitua den bide hamiltondarrari zirkuitu hamiltondarra deitzen zaio.
 Zuzendutako grafoa hamiltondar digrafoa da, baldin eta hamiltondar ziklo zuzendu bat badu.

Grafo eulertarren kasuan ez bezala, grafo hamiltondarren karakterizaziorik ez da ezagutzen.

Grafo hamiltondar guztiak lotuta daude, baina lotutako grafo guztiak ez dira hamiltondarrak.

 Adibideak 

 Ziklo grafo guztiak hamiltondarrak dira.
 Bi erpin baino gehiago dituzten  grafo osoak hamiltondarrak dira.
 Txapelketa guztiek bide zuzenduak dituzte hamiltondarrentzat [Theorem 2.2.1].
 Solido platoniko guztiak (tetraedroa, kuboa, oktaedroa, dodekaedroa eta ikosaedroa), grafotzat hartuak, hamiltondarrak dira.
 Grafo eulertarren artean, badira hamiltondarrak direnak eta ez direnak, eta grafo hamiltondarren artean, berriz, eulertarrak direnak eta ez direnak.thumb|489x489px|Grafoak: G1, G2, G3 eta G4
 G1 grafoa eulertarra eta hamiltondarra da.
 G2 grafoa eulertarra da, ez da hamiltondarra.
 G3 grafoa ez da eulertarra, eta hamiltondarra da.
 G4 grafoa ez da eulertarra, eta ez da hamiltondarra.

 Bete beharrezko baldintzak 
Hala ere, grafo bat hamiltondarra izateko beharrezko baldintza batzuk daude.

 Grafo hamiltondar batek lotuta egon behar du.
 Grafo hamiltondar batek ezin du 1. mailako erpinik izan: erpin guztietan gutxienez bi ertzetan eragin behar dute, "sarrerakoa" eta "irteerakoa".
 S G grafo baten erpin-multzoaren azpimultzo bat bada, G − S idatziko dugu, S-ren erpin guztiak eta S-ren erpinen ondoko ertz guztiak ezabatzean agertzen den azpigrafoa izendatzeko.

TeoremaGrafo hamiltondar batek, bereziki, ezin du ebaketa-erpinik izan, hau da, erpin bat, non, bertan bat egiten duten ertz guztien ondoan ezabatzen badugu, ondoriozko azpigrafoak jatorrizko grafoak baino osagai gehiago baititu lotuta.

Elkarrekikoa ez da egia.

 Baldintza nahikoak 
 Bondy-Chvátalen teorema 
Grafo baten izaera hamiltondarra bermatzen duten baldintza nahikoak ematen dituzten emaitza asko daude. Hasteko, 2 erpin baino gehiagoko grafo bat hamiltondarra den aztertzeko, begizta eta ertz paraleloak ken ditzakegu. Gainera, bi erpin dituen grafo bat hamiltondarra da baldin eta gutxienez bi ertz baditu bi erpinen artean. Beraz, grafo sinpleen analisian kontzentratzen gara, begiztarik gabe eta 2 erpin baino gehiagorekin. Zentzu horretan ekarpen onena 1976an J. A. Bondy eta V. Chvátal autoreei esker argitaratutako teorema da, G. A. Dirac-ek (1952) eta Ø.Ore (1960) aurretik aurkitutako emaitzak orokortzen dituena.  . Emaitza horiek guztiek, funtsean, grafo bat hamiltondarra dela baieztatzen dute, "nahikoa ertz" badaude. Bondy-Chvátalen teorema adierazteko, lehenik eta behin grafo baten itxiera zer den definitu behar da.

Definizioa. G grafo bat n erpinekin emanda, G-ren itxiera grafo bat da, G-ren erpin berak dituena, eta ertz guztiak {u, v} forman gehitzean agertzen da, alboko ez diren eta (v) gradua + (u) gradua ≥ n betetzen duten u eta v erpin pare guztietarako.

Teorema.Bondy-Chvátalen teoremaren frogapen bat kontsulta daiteke [Theorem 7.20].

 Ore eta Dirac-en teoremak 
Grafo oso guztiak hamiltondarrak direnez, grafo oso bat ixten duten grafo guztiak hamiltondarrak dira. Honek grafo bat hamiltondarra izateko baldintza batzuk ondorioztatzea ahalbidetzen digu; bereziki Oreren Teorema eta Diracen Teorema agertzen dira.

Teorema.Oren teoremaren zuzeneko frogapen bat kontsulta daiteke [Theorem 6.2.5] erreferentzian. TeoremaKorolarioa. G grafo konektatua bada, sinplea eta n erpinekiko begiztarik gabea, n ≥ 3 duena, eta non maila (u) + gradua (v) ≥ n − 1 ondoan ez dauden erpin pare guztietarako, u, v, horrek bide hamiltondarra duen.

Adibidea. Har dezagun grafo hau, "etxearen grafoa" deitzen dena, argi eta garbi hamiltondarra dena:
erdian|thumb|185x185px|Etxe grafoa

 Ezin dugu ondorioztatu hamiltondarra dela Dirac-en teorema aplikatuz, 2 eta 2 < 5/2 graduko erpinak baitaude.
 Ezin dugu ondorioztatu hamiltondarra dela Oreren teorema aplikatuz, 2 eta 2 + 2 < 5 graduko bi erpin bikote baitaude elkarren ondoan ez daudenak.
 Etxeko grafoa ixteko, lehenik ertz gorriak eta ondoren urdinak gehitu behar dira. Beraz, grafoaren itxiera 5 erpineko grafo osoa da. Grafo osoa hamiltondarra da. Ondorioz, etxeko grafoa hamiltondarra dela ondoriozta daiteke, Bondy-Chvátal teorema aplikatuz.

erdian|thumb|Grafo etxearen itxiera
Ore-ren teoremaren ondorio bat honako emaitza hau da. Horren frogapena [Theorem 6.2.14]-n kontsulta daiteke.

Korolarioa. G grafo konektatua bada, sinplea eta n erpinekiko begiztarik gabea, n ≥ 3 duena, eta non maila (u) + gradua (v) ≥ n − 1 ondoan ez dauden erpin pare guztietarako, u, v, horrek bide hamiltondarra duen.

Adibidea. G grafo sinplea bada, begiztarik gabea eta n erpinekoa, non gradua (u) + gradua (v) ≥ n − 1 erpin pare guztietarako, u, v, orduan G ez da nahitaez hamiltondarra, adibidez hurrengoetan.
erdian|thumb|546x546px|Adibideak

 Zuzendutako grafo hamiltondarrak 
Grafo zuzenduetarako, aipagarria da H. Meynielen-ren  emaitza bat, lotura estua duen digrafo bat hamiltondarra izateko baldintza nahikoa ematen duena.

Teorema.

 Erreferentziak 

 Kanpo estekak 

Kategoria:Grafo teoria
Kategoria:Matematika konputazionala