˝ ´ KOMBINATORIKA ELOAD AS osztatlan matematika tan´ar hallgat´ok sz´am´ara
Hamilton-´ut, Hamilton-k¨or El˝oad´o: Hajnal P´eter
2015.
1. A Hamilton-´ ut/k¨ or fogalma Az Euler-vonal olyan vonal volt, amley hossza el´eri az elm´eleti plafont”. Ilyen s´eta ” utakn´al ´es k¨or¨okn´el is l´etezik. Defin´ıci´ o. Egy u ´ t egy gr´afban Hamilton-´ ut, ha az ¨osszes cs´ ucsot ´erinti. Egy k¨or egy gr´afban Hamilton-k¨or, ha az ¨osszes cs´ ucsot ´erinti. Nyilv´anval´o, hogy Hamilton-k¨or l´etez´ese eset´en gr´afunkban van Hamilton-´ ut is. Igaz´ab´ol egy Hamilton-k¨or b´armely ´el´et elhagyva egy Hamilton-utat kapunk. Egy alapk´erd´es, hogy adott gr´afban van-e Hamilton-´ ut/k¨or. Erre az alapk´erd´esre nincs olyan egyszer˝ u, sz´ep v´alasz mint amilyn Euler t´etele az Euler-vonalakra vonatkoz´o alapfeladatn´al. A Hamilton-utak/k¨o¨ok probl´em´aja mind a mai napig akt´ıvan kutatott ter¨ ulet. 1. Feladat. Vegy¨ uk a szab´alyos testek (szab´alyos tetra´eder, kocka, okta´eder, dodeka´eder, ikoza´eder) gr´afjait. Melyekben van Hamilton-´ ut/k¨or?
2. Moh´ o´ es csavart u ´ t-n¨ ovel´ es Relax´aljuk a Hamilton-´ ut keres´es probl´em´aj´at. Ne akarjuk egyb˝ol az ¨osszes cs´ ucsot ´erinteni. keress¨ unk csak egy j´o hossz´ u” utat. ” Ism´et elkezdhet¨ unk s´et´alni a gr´afunkban. S´et´al´as k¨ozben minden cs´ ucsban olyan ´elek k¨oz¨ ul v´alassszuk ki k¨ovetkez˝o l´ep´es¨ unket, amely eddig nem l´atogatott cs´ ucsba vezet. Azaz u ¨ gyelj¨ unk arra, hogy s´et´ank bej´ar´asa k¨ozben egy utat j´arjunk be. Ezt az elj´ar´ast nevezz¨ uk moh´o u ´ t-n¨ovel´esnek. Ism´et sz¨ uks´eges az elakad´as. Az elakad´as cs´ ucsa olyan lesz, hogy az ¨osszes szomsz´edj´at eddigi s´et´ank sor´an m´ar megl´atogattuk. Sajnos elk´epzelhet˝o, hogy a leghosszabbn´al j´oval r¨ovidebb u ´ thoz jutunk. Tegy¨ uk fel, hogy az a cs´ ucsb´ol moh´o u ´ t-n¨ovel´est ind´ıtunk ´es egy z cs´ ucsban elakadunk miut´an a P utat fel´ep´ıtett¨ uk, azaz z ¨osszes szomsz´edja (legyen d a sz´amuk) aP u ´ tra esik. z szomsz´edja k¨oz¨ ul egy z − az uton k¨ozvetlen¨ ul el˝otte l´ev˝o cs´ ucs. A d − 1 t¨obbi szomsz´ed az u ´ ton ment´en nem szomsz´edos z-vel. Legyen n egy ilyen szomsz´ed. Ekkor gr´afunkban P -t nem tudtuk meghosszabb´ıtani, de ´eszrevehet¨ unk egy P -vel azonos hossz´ u alternat´ıv´at P -hez. Menj¨ unk el P -t k¨ovetve n-ig, itt egyb˝ol z-be l´epj¨ unk, majd P -n visszafele haladva j´arjuk be a P - kihagyott cs´ ucsokat. Le− gyen Pn az ´ıgy kapott alternat´ıv u ´ t. Megjegyezz¨ uk, hogy a z szomsz´ed eset´en is megtehetj¨ uk a fentieket, de ekkor P -hez jutunk vissza. Az ´ıgy kapott d alternat´ıv´at (most mag´at P -t is ide soroljuk) P csavart v´altozatainak nevezz¨ uk. Hamilton-´ ut, Hamilton-k¨or-1
1. ´abra. Egy kiindul´o P u ´ t, amely utols´o cs´ ucs´anak n´egy szomsz´edja van P -n. P n´egy csavart v´atozata.
A csavart utak tulajdons´agait ¨osszefoglaljuk: (a) Kiindul´o cs´ ucsuk azonos P kiindul´o cs´ ucs´aval. (b) Utols´o cs´ ucsuk mind k¨ ul¨onb¨oz˝o (d darab) cs´ ucs. (c) Ugyanazokat a cs´ ucsokat j´arj´ak be, speci´alisan ugyanolyan hossz´ uak. Sz´amunkra a (b) tulajdons´ag k¨ ul¨on¨osen fontos. Az utols´o cs´ ucsban pr´ob´aljuk meg folytatni az utunk n¨ovel´es´et. A kezdeti z cs´ ucs sikertelen volt. A most tal´alt tov´abbi alternat´ıv´akmind lehet˝os´eget k´ın´alnak. Ha valamelyiknek van P -n k´ıv¨ uli szomsz´edja, akkor sikerrel hosszabbithatjuk meg utunkat. Ha ez lehets´eges akkor csavar´asos u ´ tn¨ovel´esr˝ol besz´el¨ unk. A moh´os´ag feladas´ar´ol van sz´o: Az elakad´askor vissza l´ep¨ unk z egy szomsz´edj´ahoz ´es az ott hozott moh´o d¨ont´esn´el visszakozunk, egyb˝ol z-be l´ep¨ unk ´es m´odos´ıtott u ´ tn´al nyer¨ unk legal´abb egy tov´abbi l´ep´est.
3. Dirac-t´ etel Bizonyos felt´etelek mellett a csavar´asos u ´ tn¨ovel´es eset´en garant´alt a siker. 2. T´ etel. Tegy¨ uk fel, hogy egy G egyszer˝ u gr´afban minden cs´ ucs legal´abb a cs´ ucsok fel´evel szomsz´edos. Legyen P egy u ´t, amely nem Hamilton-´ ut. Ekkor P garant´altan n¨ovelhet˝o csavar´asos m´odon. Bizony´ıt´ as. Legyen x egy cs´ ucs, amely nincs rajta az utunkon (mivel nem Hamiltonu ´ t ez biztos l´etezik). Legyen z az u ´ t utols´o cs´ ucsa. Ha utunk moh´o m´odon n¨ovelhet˝o, akkor k´eszen vagyunk. Tegy¨ uk fel, hogy nem ´ıgy van. Ekkor a z cs´ ucs minden szomsz´edja (d(z) Hamilton-´ ut, Hamilton-k¨or-2
darab) egy-egy csavar´as´at adja. Legyen Z azon pontok halmaza, ahova a csavart utak elvezetnek. Legyen N az x (nem az u ´ tra es˝o cs´ ucs) szomsz´edjai. Felt´eteleink alapj´an |Z|, |N| ≥ |V |/2. Tov´abb´a x 6∈ Z, N. Ez garant´alja, hogy N ´es Z nem lehet diszjunkt. Kell egy k¨oz¨os cs´ ucsuknak lenni: k. Ekkor az utunk csavarhat´o u ´ gy, hogy k-ba vezessen (k ∈ Z ´es innen x-be foly´ ıt´asunkat igazoltuk. tathat´o lesz (k ∈ N). All´ A fenti ¨otlet Hamilton-´ ut eset´en is mond valamit: 3. T´ etel. Tegy¨ uk fel, hogy egy G egyszer˝ u gr´afban minden cs´ ucs legal´abb a cs´ ucsok fel´evel szomsz´edos. Legyen P egy Hamilton-´ ut G-ben. Ekkor P garant´altan csavarhat´o u ´gy, hogy k´et v´egpontja ¨osszek¨ot¨ott legyen. Bizony´ıt´ as. Legyen P egy az Hamilton-´ ut. Ekkor a z cs´ ucs minden szomsz´edja (d(z) darab szomsz´ed, sz¨ uks´egszer˝ uen P n) egy-egy csavar´as´at adja. Legyen Z azon pontok halmaza, ahova a csavart utak elvezetnek. Legyen N az a cs´ ucs szomsz´edjai. Felt´eteleink alapj´an |Z|, |N| ≥ |V |/2. Tov´abb´a a 6∈ Z, N (a a csavart Hamiltonutak kezd˝opontja ´es a foksz´amra tett felt´etel miatt legal´abb k´et pontunk van a gr´afunkban). Ez garant´alja, hogy N ´es Z nem lehet diszjunkt. Kell egy k¨oz¨os cs´ ucsuknak lenni: k. Ekkor az utunk csavarhat´o u ´ gy, hogy k-ba vezessen (k ∈ Z). A csavar´as ut´an is ´ ıt´asunkat igazoltuk. a-b´ol indul utunk. A k´et v´egpont ¨osszek¨ot¨ott (k ∈ N). All´ A k´et t´etel egy¨ utt kiadja a k¨ovetkez˝o nagyon fontos alapt´etelt. 4. T´ etel (Dirac t´ etele). Tegy¨ uk fel, hogy egy G egyszer˝ u gr´afban minden cs´ ucs legal´abb a cs´ ucsok fel´evel szomsz´edos, tov´abba |V | = 6 2. Ekkor G-ben van Hamiltonk¨or. Bizony´ıt´ as. A felt´etelek bizotos´ıtj´ak, hogy csavar´asos u ´ tn¨ovel´essel Hamilton-´ uthoz jussunk. Ezut´an egy esetleges tov´abbi csvar´assal el´erhetj¨ uk, hogy a Hamilton-´ ut kezd˝o ´es v´egpontja szomsz´edos legyen. Mivel |V | = 6 2 ez´ert egy Hamilton-´ uthoz jutunk. A Dirac n´ev fizikusok sz´am´ara ismer˝os lehet. Paul Dirac Nobel-d´ıjas fizikus. A ´ t´etel azonban fia, Gabriel Dirac t´etele. Erdekess´ egk´ent megeml´ıtj¨ uk, hogy Gabriel Dirac magyar sz¨ ulet´es˝ u matematikus. Wigner Jen˝o egyik l´any testv´ere Wigner Margit (Manci) k´et gyerekes anya elv´alt. Egyik gyerek´et G´abornak h´ıvt´ak. Mint elv´alt asszony l´atogatta meg testv´er´et (a szint´en Nobel-d´ıjat ´erdeml˝o) Wigner Jen˝ot Princeton-ban. Ott ismerkedett meg Paul Dirac-kal, akivel ¨ossze is h´azasodtak. Dirac term´eszetesen Wigner Margit gyerekeit mag´a´enak fogadta.
4. Sz¨ uks´ eges felt´ etelek Hamilton-k¨ or l´ etez´ es´ ere A Dirac-t´etel egy el´egs´eges felt´etelt ad Hamilton-k¨or l´etez´es´ere. A felt´etel term´eszetesen nem sz¨ uks´eges. Az ¨osszes cs´ ucson ´athalad´o k¨orgr´afban van Hamilton-k¨or (maga a gr´af egy Hamilton-k¨or). M´egis minden cs´ ucs foka csak 2. Ha cs´ ucshalmazunk nagy (gondoljunk 2015-re), akkor a Dirac-t´etel felt´etelei nagyon” nem teljes¨ ulnek. ” A m´asik oldalr´ol is adunk egy felt´etelt. Egy egyszer˝ u ´eszrev´etellel kez¨ unk: Hamilton-´ ut, Hamilton-k¨or-3
´ Eszrev´ etel. Legyen G-ben egy Hamilton-k¨or. Ha k cs´ ucsot elhagyunk a gr´afunkb´ol (´ıgy a k¨orr˝ol), akkor a Hamilton-k¨or legfeljebb k ´ıvre/r´esz´ utra esik sz´et. Ezek a marad´ek utak” gr´afunkat legfeljebb k komponensbe sorolj´ak. ” Az ´all´ıt´as nyilv´anval´o. Geometriai anal´ogja is van. Egy geometriai k¨or¨on felvett k pont k ´ıvre osztja a k¨ort. Itt az´ert nem mondhatjuk meg a r´eszek pontos sz´am´at, mert ha szomsz´edos cs´ ucsok is vannak az elhagyottak k¨ozt, akkor a k¨oztes marad´ek” ” nem jelentkezik (szemben a geometriai helyzettel). Megeml´ıtj¨ uk az ´eszrev´etel Hamilton-utakra vonatkoz´o v´altozat´at is. ´ Eszrev´ etel. Legyen G-ben egy Hamilton-´ ut. Ha k cs´ ucsot elhagyunk a gr´afunkb´ol (´ıgy az u ´ tr´ol), akkor a k¨or legfeljebb k + 1 ´ıvre/r´esz´ utra esik sz´et. Ezek a marad´ek ” utak” gr´afunkat legfeljebb k + 1 komponensbe sorolj´ak. Az els˝o ´eszrev´etel ¨osszefoglal´asa: Hamilton-k¨or l´etez´es´enek sz¨ uks´eges felt´etele, hogy tetsz˝oleges k term´eszetes sz´amra ´es tetsz˝oleges k cs´ ucsra elhagy´asukkal legfeljebb k komponensre essen sz´et a gr´afunk. A m´asodik ´eszrev´etel ¨osszefoglal´asa: Hamilton-´ ut l´etez´es´enek sz¨ uks´eges felt´etele, hogy tetsz˝oleges k term´eszetes sz´amra ´es tetsz˝oleges k cs´ ucsra elhagy´asukkal legfeljebb k + 1 komponensre essen sz´et a gr´afunk.
5. Feladat. Egy sakkt´abla k´et szemk¨oztes sarokmez˝oj´et vegy¨ uk ki. V´egig h´ uzhat´o-e egy b´astya a marad´ek mez˝ok felett u ´gy, hogy minden mez˝o felett pontosan egyszer haladjunk el ´es utunk sor´an a b´astya l´ep´esnek megfelel˝oen mozogjunk? (A c1 mez˝or˝ ol a c8 mez˝ore l´epve a teljes c oszlop mez˝oi felett elh´ uztuk b´asty´ankat.) A csonkolt sakkt´abla 62 mez˝oje, az elemi b´astya l´ep´essel (egy mez˝or˝ol egy k¨oz¨os oldallal rendelkez˝o szomsz´edos mez˝ore l´ep¨ unk) defini´alt szomsz´eds´aggal egy gr´afot alkot. A k´erd´es, hogy ebben van-e Hamilton u ´ t. A v´alasz: nem: Egy indokl´as lehet, hogy a 62 mez˝o a k´et sz´ın k¨oz¨ott 30 + 32 ar´anyban oszlik meg. Ha elhagyjuk a kisebb sz´ınoszt´alyban l´ev˝o 30 mez˝ot, akkor gr´afunk sz´et esik 32 izol´alt cs´ ucsra/komponensre. ´Igy gr´afunkban nem lehet Hamilton-´ ut. 6. Feladat. Egy 4 × 4 m´eret˝ u sakkt´abla bej´arhat´o-e husz´arral u ´gy, hogy minden mez´ore pontosan egyszer l´ep¨ unk? Ism´et defini´alhatunk egy egyszer˝ u gr´afot: Cs´ ucsai a 16 mez˝o, a szomsz´eds´agot a husz´ar l´ep´es defini´alja. H´any komponense lesz gr´afunknak, ha elhagyjuk a k¨oz´eps˝o 4 mez˝onek megfelel˝o cs´ ucsot? A k´erd´es megv´alaszol´as´at ´es a feladat megold´as´at az ´erdekl˝od˝o hallgat´okra b´ızzuk.
Hamilton-´ ut, Hamilton-k¨or-4
7. Feladat. (a) Igazoljuk, hogy az al´abbi gr´afb´ol tetsz˝oleges k term´eszetes sz´amra ak´arhogy hagyunk el k cs´ ucsot a marad´ek gr´afnak legfeljebb k komponense lesz.
(b) Igazoljuk, hogy a fenti gr´afban nincs Hamilton-k¨or. ⋆ Az ´erdekl˝od˝o hallgat´onak tal´an hi´any´erzete lehet ezen fejezet elolvas´asa ut´an. Az el˝oz˝o fejezet hasonl´o probl´em´aval foglalkozott. Ott teljes volt a megold´as. Tetsz˝oleges gr´af eset´en hat´ekony elj´ar´ast kaptunk annak eld¨ont´es´ere, hogy egy gr´afban van-e Euler-vonal. Itt csak r´eszeredm´enyeket” l´atunk. Az utols´o feladat megold´as´ahoz a ” kor´abbi ¨otletek nem alkalmazhat´ok. Ez nem v´eletlen. A Hamilton-k¨or l´etez´es´enek eld¨ont´ese egy m´as kateg´oria” mint ” az Euler-vonal l´etez´es´enek eld¨ont´ese. A pontos fogalmak kialak´ıt´asa messze t´ ulmutat az el˝oad´assorozat keretein. Csak megeml´ıtj¨ uk, hogy a Hamilton-k¨or l´etez´es´enek tesztel´ese egy u ´ gy nevezett N P -teljes probl´ema. Ha valaki u ¨ gyesen tudja ezt kezelni, akkor egy nagyon t´ag, sokak ´altal vizsg´alt t´emak¨or ¨osszes probl´em´aj´ar´ol mond valamit (p´eld´aul a modern titkos´ır´asok felt¨or´es´er˝ol). A tud´osok mai v´elem´enye szerint a Hamilton-k¨or l´etez´es´enek hat´ekony eld¨ont´ese elm´eleti neh´ezs´egekbe u ¨ tk¨ozik. Ezeknek a neh´ezs´egeknek a tiszt´az´asa a modern matematika egy k¨ozponti k´erd´ese.
Hamilton-´ ut, Hamilton-k¨or-5
