Llwybr Hamiltonaidd

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.^[1] 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.^[2]

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.^[3]

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.^[4]^[5]

Cyfeiriadau

↑ Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society 13 (2): pp. 97–120, doi:10.1112/blms/13.2.97, MR 608093
↑ Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5.
↑ Bollobas, Bela (6 Rhagfyr 2012). Graph Theory: An Introductory Course (yn Saesneg). Springer Science & Business Media. ISBN 978-1-4612-9967-7.
↑ de Ruiter, Johan (2017). Hamilton Mazes: The Beginner's Guide.
↑ Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archifwyd o'r gwreiddiol ar 16 Ebrill 2016. Cyrchwyd 27 Mai 2017.

[1] Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society 13 (2): pp. 97–120, doi:10.1112/blms/13.2.97, MR 608093

[2] Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5.

[3] Bollobas, Bela (6 Rhagfyr 2012). Graph Theory: An Introductory Course (yn Saesneg). Springer Science & Business Media. ISBN 978-1-4612-9967-7.

[4] Ruiter, Johan (2017). Hamilton Mazes: The Beginner's Guide.

[5] Friedman, Erich (2009). "Hamiltonian Mazes". Erich's Puzzle Palace. Archifwyd o'r gwreiddiol ar 16 Ebrill 2016. Cyrchwyd 27 Mai 2017.

[1]

[2]

[3]

[4]

[5]