Llwybr Hamiltonaidd

bawd|Cylchlwybr Hamiltonaidd ar ddodecahedron.
bawd|Cylchlwybr Hamiltonaidd ar graff ymylon y dodecahedron uchod.
Ym maes damcaniaeth graffiau, mae llwybr Hamiltonaidd yn llwybr mewn graff (anghyfeiriedig neu'n gyfeiriedig) sy'n ymweld â phob fertig unwaith yn union. Mae cylchlwybr Hamiltonaidd (neu gylched Hamiltonaidd) yn llwybr Hamiltonaidd sy'n gylchlwybr, hynny yw'n dechrau ac yn gorffen wrth yr un fertig. Mae'r broblem llwybr Hamiltonaidd, sef penderfynu a oes llwybrau a chylchlwybrau o'r fath yn bodoli mewn graffiau, yn NP-gyflawn. 

Enwir llwybrau a chylchlwybrau Hamiltonaidd ar ôl William Rowan Hamilton a ddyfeisiodd y gêm icosiaidd, lle mae'n rhaid dod o hyd i gylchlwybr Hamiltonaidd yng ngraff ymylon y dodecahedron. Datrysodd Hamilton y broblem hon gan ddefnyddio'r calcwlws icosiaidd, ond nid yw'r datrysiad hwn yn cyffredinoli i raffiau mympwyol. 

Er gwaethaf cael eu henwi ar ôl Hamilton, roedd cylchlwybrau Hamiltonaidd mewn polyhedronau hefyd wedi cael eu hastudio flwyddyn ynghynt gan Thomas Kirkman, a roddodd, yn benodol, enghraifft o bolyhedron heb gylchlwybr Hamiltonaidd. Hyd yn oed yn gynharach, astudiwyd llwybrau a chylchlwybrau Hamiltonaidd (yng ngraff y marchog o'r bwrdd gwyddbwyll) yn y 9fed ganrif gan Rudrata, a thua'r un amser gan Adli ar-Rumi. Yn Ewrop y 18fed ganrif, cyhoeddwyd llwybrau'r marchog gan Abraham de Moivre a Leonhard Euler.. 

 Diffiniadau 
Mae llwybr Hamiltonaidd yn llwybr sy'n ymweld â phob fertig o'r graff unwaith yn unig. Gelwir graff sy'n cynnwys llwybr Hamiltonaidd yn graff y gellir ei olrhain . Mae graff gysylltiedig-Hamiltonaidd os oes llwybr Hamiltonaidd rhwng pob pâr o fertigau. 

Mae cylchlwybr Hamiltonaidd, neu gylched Hamiltonaidd yn gylchlwybr sy'n ymweld â phob fertig unwaith yn union. Gelwir graff sy'n cynnwys cylchlwybr Hamiltonaidd yn graff Hamiltonaidd. 

Gellir diffinio syniadau tebyg ar gyfer graffiau cyfeiriedig, lle mai dim ond mewn un cyfeiriad y gellir teithio pob ymyl (arc) y llwybr neu'r cylchlwybr. 

Mae drysfa Hamilton (Hamilton maze) yn fath o bos rhesymeg a'r nod yw dod o hyd i'r cylchlwybr Hamiltonaidd unigryw mewn graff penodol. 

Cyfeiriadau