Eyler jolı dep ataladı. Quramında oriyentirlengen Eyler jolı bar bolǵan oriyentirlengen graf oriyentirlengen Eyler grafi

Eyler cikli. Fleri algoritmi

Oriyentirlengen graflarda oriyentirlengen Eyler jolin izlew menen shuǵıllanıw múmkin. Hár bir qırdan tek bir ret ótetuǵın jol oriyentirlengen Eyler jolı dep ataladı. Quramında oriyentirlengen Eyler jolı bar bolǵan oriyentirlengen graf oriyentirlengen Eyler grafi dep ataladı.

Endi qırları sanına n teń bolǵan berilgen Eyler grafinda Eyler shınjırın dúziwdiń Flyori algoritmın keltiremiz. Bul algoritmǵa kóre graftıń qırları Eyler ciklinda dús keliwi tártibi boyınsha 1 den n ge shekem nomerlep shıǵıladı.
Berilgen Eyler grafi ushın Flyori algoritmına qaray tómendegi eki qaǵıyda tiykarında jumıslar izbe-iz atqarıladı:
Graftıń qálegen úshıdan baslap bul úshqa ınsident bolǵan qálegen qırǵa (mısalı, qırǵa) 1 nomeri beriledi. Bul qır grafdan alıp taslanadı hám úshten úshqa ótiledi.
Aqırǵı ótiwden aldınǵı ótiw nátiyjesinde payda bolǵan úsh bolsın hám aqırǵı ótiwde qandayda bir qırǵa nomeri berilgen deylik. Úshqa insident qálegen qır múmkinshiligi barınsha sonday tánlanadı, bul qırdı alıp taslaw grafdagi baylamlilikni buzmaydı. Saylanǵan qırǵa náwbettegi (k+1) nomeri beriledi jáne bul qır grafdan alıp taslanadı.
Flyori algoritmına kóre jumıs júrgiziw Eyler grafi ushın mudami shekli process ekenligi jáne bul process mudami grafdan bárshe qırlardıń alıp taslanıwı, yaǵnıy Eyler shınjırın dúziw menen tawısıwı tastıyıqlanǵan. Sonı da atap ótiw kerek, Flyori algoritmini qóllaw processinde qırlardı tańlaw múmkinshilikleri kóp bolǵanı ushın, bunday jaǵdaylarda, algoritmdı qóllaw ámeldegi Eyler cikllerinen birin tabıw menen sheklenedi. Túsiniletuǵını, Flyori algoritmın tákirar qollap (bunda qırlardı tańlaw processi algoritmın aldınǵı qóllawlardaǵı sıyaqlı áyne tákirarlanbawı kerek) grafda ámeldegi bolǵan barlıq Eyler ciklların tabıw múmkin.

forma 1
1- mısal. 1- formada suwretlengen graftı qaraymız. Áwele bul graftıń Eyler grafi bolıwı shártini, yaǵnıy 1- teorema shártleriniń orınlanıwın tekseremiz. Berilgen grafda toǵızta úsh bolıp, 1, 3, 7, 9 belgili úshlerdiń dárejesi ekige, 2, 4, 6, 8 belgili úshlerdiń dárejesi tórtge, 5 belgili uchning dárejesi bolsa altiǵa teń. Qullası, bul grafdagi barlıq úshlerdiń dárejeleri júp bolıp tabıladı. Sol sebepli, 1- teoremaga kóre, 1- formada suwretlengen graf Eyler grafi bolıp tabıladı jáne onıń quramında Eyler sikli bar.
Berilgen grafqa flyori algoritmın qollap ámeldegi Eyler cikllerinen birin anıqlaymız. Dáslepki úsh retinde grafdagi 1 belgili úsh alınǵan bolsın. Bul úshten eki jóneliste: qır boylap yamasa qır boylap háreketleniw múmkin. Mısalı, qır boylap háreketlenip 2 belgili uchqa ótemız. Endi háreketti 3 jóneliste: yamasa qır boylap, yamasa qır boylap, yamasa qır boylap dawam ettiriw múmkin. Aytaylik, qır boylap háreketlenip 3 belgili uchqa ótken bo'laylik. Sol usılda dawam etip múmkin bolǵan Eyler cikllerinen birin, mısalı, tómendegi siklni payda etemiz:
( , , , , , , , ,
, , , , , , ).