Bide hamiltondarra

Grafoen teorian, grafo batean bide hamiltoniar bat bide 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 hamiltoniarra da.

Grafo arbitrario batean ziklo (edo bide) hamiltoniar bat aurkitzeko arazoa ezagutzen da NP-osoa [1] eta, beraz, 21 NP-osoa Karp arazoak zerrendan agertzen da.

Izena sir William Rowan Hamilton (1805-65) matematikari irlandarretik dator, zeinak munduko hogei hiritara bidaiatzea proposatu zuen, dodekaedro erregular baten erpinak bezala irudikatuak, dodekaedroaren ertzei jarraituz.

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

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

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

1. Digrafo batean zuzendutako bidea hamiltondar zuzendutako bidea da, digrafoaren erpin guztiak bisitatzen badituzu, bat bera ere errepikatu gabe.
2. Zirkuitua den bide hamiltoniarrari zirkuitu hamiltoniarra deitzen zaio.
3. Zuzendutako grafoa hamiltoniar digrafoa da, baldin eta hamiltoniar ziklo zuzendu bat badu.

Grafo euleriarren kasuan ez bezala, grafo hamiltoniarren karakterizaziorik ez da ezagutzen.

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

• Grafo ziklo guztiak hamiltondarrak dira.
• Bi erpin baino gehiagoko grafo osoak hamiltondarrak dira.
• Txapelketa guztiek bide zuzenduak dituzte hamiltoniarrentzat [1] [Theorem 2.2.1 [2]].
• Solido platoniko guztiak (tetraedroa, kuboa, oktaedroa, dodekaedroa eta ikosaedroa), grafotzat hartuak, hamiltoniarrak dira. [1]
• Grafo euleriarren artean, badira hamiltoniarrak direnak eta ez direnak, eta grafo hamiltoniarren artean, berriz, euleriarrak direnak eta ez direnak.

  

  1. G1 grafoa euleriarra eta hamiltondarra da.
  2. G2 grafoa euleriarra da, eta ez da hamiltondarra.
  3. G3 grafoa ez da euleriarra, eta hamiltondarra da.
  4. G4 grafoa ez da euleriarra, eta ez da hamiltondarra.

Hala ere, grafo bat hamiltoniarra izateko beharrezko baldintza batzuk idatz ditzakegu.

• Grafo hamiltoniar batek lotuta egon behar du.
• Grafo hamiltoniar 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.

Teorema

G grafo bat hamiltoniarra bada, G-ren S erpinen edozein azpimultzo ez-hutsetarako, G − S azpigrafoari lotutako osagaien kopurua S-ren kardinala baino txikiagoa edo berdina da. (Cf. [Theorem 6.3.4^[1]])

Grafo hamiltoniar 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.

Grafo baten izaera hamiltoniarra bermatzen duten baldintza nahikoak ematen dituzten emaitza asko daude. Hasteko, 2 erpin baino gehiagoko grafo bat hamiltoniarra den aztertzeko, begizta eta ertz paraleloak ken ditzakegu. Gainera, bi erpin dituen grafo bat hamiltoniarra 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 bat da, G. A. Dirac-ek (1952) eta EREk (1952) aurretik aurkitutako emaitzak orokortzen dituena. Ore (1960). Emaitza horiek guztiek, funtsean, grafo bat hamiltoniarra 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.

Grafo bat hamiltoniarra da baldin eta soilik baldin bere kalusula hamiltondarra den.^[2]

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

Grafo oso guztiak hamiltondarrak direnez, grafo oso bat ixten duten grafo guztiak hamiltondarrak dira. Honek grafo bat hamiltoniarra izateko baldintza batzuk ondorioztatzea ahalbidetzen digu; bereziki Oreren Teorema eta Diracen Teorema agertzen dira.

Teorema.

G grafo konexua bada, sinplea eta n erpinekiko begiztarik gabea, n ≥ 3 duena, non maila (u) + gradua (v) ≥ n auzokide ez diren u eta v ertz pare guztietarako G hamiltoniarra da.^[3]

Oren teoremaren zuzeneko frogapen bat kontsulta daiteke [Theorem 6.2.5] erreferentzian. Teorema

G grafo konexua bada, sinplea, begiztarik gabea, n erpinekoa eta (u) ≥ n/2 gradua u erpin guztietarako betetzen den, orduan G hamiltoniarra da.^[4]

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 hamiltoniarra duen.

Adibidea. Har dezagun grafo hau, "etxeko grafo" deitzen dena, argi eta garbi hamiltoniarra dena:

• 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 hamiltoniarra da. Ondorioz, etxeko grafoa hamiltoniarra dela ondoriozta daiteke, Bondy-Chvátal teorema aplikatuz.

Oreren 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 hamiltoniarra 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 hamiltoniarra. Adibide askotan ikus daiteke hori; bereziki, hurrengoetan.

Grafo zuzenduetarako, aipa dezagun H. Meynielen emaitza bat, lotura estua duen digrafo bat hamiltoniarra izateko baldintza nahikoa ematen duena.

Teorema.

D, n erpinekin lotura estua duen grafo zuzendu bat bada, non maila (u) + gradua (v) ≥ 2n − 1 izango den u eta v ondoan ez dauden bikote ororentzat, D grafo zuzendua hamiltoniarra izango da.^[5]