Llwybr Euleraidd

Aml-graff Pontydd Königsberg. Nid yw'r aml-graff hwn yn Euleraidd, felly, nid oes datrysiad yn bodoli.

Mae gan bob fertig y graff hwn gradd sy'n eilrif. Felly, graff Euleraidd yw hwn. Mae dilyn yr ymylon yn nhrefn yr wyddor yn rhoi cylchlwybr 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. 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.

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.

Priodweddau

• Mae gan graff heb ei gyfeirio cylchlwybr Euleraidd os a dim ond os oes gan bob fertig radd sy'n eilrif, a bod ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig.
• Gellir dadelfennu graff heb ei gyfeirio yn gylchlwybrau ymyl-digyswllt os a dim ond os mad gradd bob un o'i fertigau yn eilrif. Felly, mae gan graff gylchlwybr Euleraidd os a dim ond os gellir ei ddadelfennu i gylchlwybrau ymyl-digyswllt ac mae ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig.
• Mae gan graff heb ei gyfeirio llwybr Euleraidd os a dim ond os oes gan sero neu ddau fertig radd sy'n odrif, a bod ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig.
• Mae gan graff cyfeiriedig gylchlwybr Euleraidd os a dim ond os oes gan bob fertig mewnradd yn hafal i'w allradd, a bod ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig gryf. Yn gywerth, mae gan graff cyfeiriedig gylchlwybr Euleraidd os a dim ond os gellir ei ddadelfennu'n gylchlwybrau cyfeiriedig ymyl-digyswllt ac mae ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig gryf.
• Mae gan graff cyfeiriedig lwybr Euleraidd os a dim ond os oes gan un fertig ar y mwyaf (allradd) − (mewnradd) = 1, ar y mwyaf un fertig â (mewnradd) − (allradd) = 1, mae gan bob fertig arall allradd a mewnradd gyfartal, ac mae ei holl fertigau â gradd nad yw'n sero yn perthyn i un gydran gysylltiedig o'r graff tanfodol sydd heb ei gyfeirio.

Canfod llwybrau a chylchlwybrau Euleraidd

Algorithm Fleury

Mae algorithm Fleury yn algorithm cain ond aneffeithlon sy'n dyddio yn ôl i 1883. Ystyriwch graff anghyfeiriedig Euleraidd neu lled-Euleraidd.

• Os yw'r graff yn lled-Euleraidd mae'r algorithm yn cychwyn ar un o'r fertigau sydd â gradd sy'n odrif;
• Neu os yw'r graff yn Euleraidd mae'n dechrau ar unrhyw fertig.

Ar bob cam:

• Dewiswch ymyl nesaf y llwybr i fod un na fyddai ei ddileu yn datgysylltu'r graff; neu os nad oes ymyl o'r fath, rhaid bod ond un ymyl ar ôl, felly dewiswch yr ymyl hyn.
• Yna mae'n teithiwch ar hyd yr ymyl hyn i'w ddiweddbwynt, ac yn dileu'r ymyl.

Ar ddiwedd yr algorithm nid oes unrhyw ymylon ar ôl, ac mae'r dilyniant yr ymylon a ddewiswyd yn ffurfio cylchlwybr Euleraidd os yw'r graff yn Euleraidd, neu lwybr Euleraidd yw'r graff yn lled-Euleraidd.

Er bod y teithio ar hyd ymylon y graff yn llinol yn ôl nifer yr ymylon, h.y. , mae angen i ni hefyd ystyried cymhlethdod canfod pontydd. Yn defnyddio algorithm Tarjan i wneud hyn, bydd gan algorithm Fleury gymhlethdod amser . Mae algorithm deinamig o ddarganfod pontydd gan Thorup (2000) caniatáu gwella hyn i gymhlethdod amser $O(|E|(\log |E|)^{3}\log \log |E|)$, mae hyn yn dal yn sylweddol arafach nag algorithmau amgen.

Algorithm Hierholzer

Mae papur Hierholzer ym 1873 yn darparu dull gwahanol ar gyfer dod o hyd i gylchlwybrau Euler sy'n fwy effeithlon nag algorithm Fleury:

• Dewiswch unrhyw fertig cychwynnol v, a dilynwch lwybr ymylon o'r fertig hwnnw nes dychwelyd i v. Nid yw'n bosibl mynd yn sownd ar unrhyw fertig heblaw v, oherwydd gan fod gan bob fertig radd sy'n eilrif, pan fydd y llwybr yn mynd i mewn i fertig arall w, rhaid bod ymyl na ddefnyddiwyd yn barod yn gadael w. Mae'r llwybr a ffurfiwyd fel hyn yn gylchlwybr, ond efallai na fydd yn gorchuddio holl fertigau ac ymylon y graff cychwynnol.
• Cyn belled â bod fertig u yn perthyn i'r daith gyfredol ond sydd ag ymylon cyfagos nad yw'n rhan o'r daith, dechreuwch lwybr arall o u, gan ddilyn ymylon ni ddefnyddiwyd eto nes dychwelyd i u, ac ymuno'r llwybr a ffurfiwyd yn y modd hwn i'r llwybr blaenorol.
• Oherwydd bod y graff yn Euleraidd mae'n gysylltiedig, felly bydd ailadrodd y cam blaenorol yn ychwanegu holl ymylon y graff i'r cylchlwybr.

Mae gan yr algorithm hwn cymhlethdod amser $O(|E|)$.

Cymwysiadau

Defnyddir llwybrau Euleraidd mewn biowybodeg i ailadeiladu dilyniannau DNA o'i dameidiau toredig. Fe'u defnyddir hefyd wrth ddylunio cylchedau CMOS i ddod o hyd i drefn gatiau rhesymeg gorau bosib. Mae yna rai algorithmau ar gyfer prosesu coed graffiau sy'n dibynnu ar lwybrau Euleraidd.