Bide Hamiltondarra
Grafoen teorian, grafo batean bide hamiltondar bat 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[1] dela jakina da eta beraz, 21 Karp arazoen zerrendan agertzen da.
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
[aldatu | aldatu iturburu kodea]- 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
[aldatu | aldatu iturburu kodea]- Ziklo grafo guztiak hamiltondarrak dira.
- Bi erpin baino gehiago dituzten grafo osoak hamiltondarrak dira.
- Txapelketa guztiek bide zuzenduak dituzte hamiltondarrentzat [Theorem 2.2.1][2].
- Solido platoniko guztiak (tetraedroa, kuboa, oktaedroa, dodekaedroa eta ikosaedroa), grafotzat hartuak, hamiltondarrak dira[3].
- Grafo eulertarren artean, badira hamiltondarrak direnak eta ez direnak, eta grafo hamiltondarren artean, berriz, eulertarrak direnak eta ez direnak.
- 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
[aldatu | aldatu iturburu kodea]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.
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])
Grafo 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
[aldatu | aldatu iturburu kodea]Bondy-Chvátalen teorema
[aldatu | aldatu iturburu kodea]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.
Grafo bat hamiltoniarra da baldin eta soilik baldin bere kalusula hamiltondarra den.[4]
Bondy-Chvátalen teoremaren frogapen bat kontsulta daiteke [Theorem 7.20].
Ore eta Dirac-en teoremak
[aldatu | aldatu iturburu kodea]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.
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.[5]
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.[6]
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. Har dezagun grafo hau, "etxearen grafoa" deitzen dena, argi eta garbi hamiltondarra 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 hamiltondarra da. Ondorioz, etxeko grafoa hamiltondarra dela ondoriozta daiteke, Bondy-Chvátal teorema aplikatuz.
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.
Zuzendutako grafo hamiltondarrak
[aldatu | aldatu iturburu kodea]Grafo zuzenduetarako, aipagarria da H. Meynielen-ren emaitza bat, lotura estua duen digrafo bat hamiltondarra 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.[7]
- ↑ Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
- ↑ Ranganathan Balakrishnan, R. K.. (2000). A Textbook of Graph Theory. Springer.
- ↑ «"Eine kombinatorischer Satz"» Acta Litt. Sci. Szeged: 39–43..
- ↑ J. A. Bondy y V. Chvátal, A method in graph theory. Discrete Math. 15 (1976) 111-135.
- ↑ O. Ore, Note on Hamilton circuits. Amer. Math. Monthly 67 (1960) 55.
- ↑ G. A. Dirac, Some theorems on abstract graphs. Proc. London Math. Soc, 2 (1952) 69-81
- ↑ H. Meyniel, Une condition sufisante d’existence d’un graphe orienté. J. Combinatorial Theory B 14 (1973), 137–147.