Llwybr Euleraidd

Mewn damcaniaeth graffiau, mae llwybr Euleraidd (neu drywydd Euleraidd) yn llwybr mewn graff meidraidd sy'n ymweld â phob ymyl unwaith yn union (yn caniatáu ailymweld â'r fertigau). Yn yr un modd, mae cylchlwybr Euleraidd yn llwybr Euleraidd sy'n cychwyn ac yn gorffen ar yr un fertig. Fe'u trafodwyd yn gyntaf gan Leonhard Euler wrth ddatrys y broblem enwog Saith Pont Königsberg ym 1736.

Profodd Euler mai amod angenrheidiol ar gyfer bodolaeth cylchlwybrau Euleraidd yw bod gan bob fertig yn y graff gradd sy'n eilrif, a nododd heb brawf bod gan raffiau cysylltiedig sydd â phob fertig gradd sy'n eilrif gylchlwybr Euleraidd. Cyhoeddwyd y prawf cyflawn cyntaf o'r honiad olaf hwn gan Carl Hierholzer ym 1873, ar ôl marwolaeth.^[1] Gelwir hyn yn Theorem Euler:

Mae gan graff cysylltiedig gylchlwybr Euleraidd os a dim ond os oes gan bob fertig radd sy'n eilrif.

Mae dau ystyr i'r term graff Euleraidd: un ystyr yw graff gyda chylchlwybr Euleraidd, a'r llall yw graff lle mae gan bob fertig gradd sy'n eilrif. Mae'r diffiniadau hyn yn gywerth ar gyfer graffiau cysylltiedig.^[2]

Ar gyfer bodolaeth llwybrau Euleraidd mae'n angen bod gan sero neu ddau fertig sydd â gradd sy'n odrif. Mae hyn yn golygu nad yw graff Königsberg yn Euleraidd. Os nad oes fertigau sydd â gradd sy'n odrif, mae pob llwybr Euleraidd yn gylchlwybrau. Os oes gan ddau fertig yn union gradd sy'n odrif, mae'r holl lwybrau Euleraidd yn cychwyn yn un ohonynt ac yn gorffen yn y llall. Gelwir graff sydd â llwybr Euleraidd ond dim cylchlwybr Euleraidd yn graff lled-Euleraidd.

1. ↑ N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736–1936, Clarendon Press, Oxford, 1976, 8–9, ISBN 0-19-853901-0.
2. ↑ C. L. Mallows, N. J. A. Sloane (1975). "Two-graphs, switching classes and Euler graphs are equal in number". SIAM Journal on Applied Mathematics 28 (4): 876–880. doi:10.1137/0128070. JSTOR 2100368. http://neilsloane.com/doc/MallowsSloane.pdf.