Qartəmizləyən maşın, küçə təmizləyən maşın və poçtalyon hər küçədən keçməli olan, lakin iki dəfə küçədən keçmək istəməyən avtomobillər və insanlar üçün nümunədir.

Qrafik nəzəriyyəsi riyaziyyatçı Leonard Eyler bu cür yollar üzərində işləyərkən başladı.

Eyler Königsberqin Yeddi Körpüsü haqqında bir məqalə yazdı və sübut etdi ki, hər körpünün üstündən bir dəfə şəhəri keçmək mümkün deyil.

Bu barədə ətraflı oxumaq üçün aşağıdakı problemin xəritəsi üzərinə klikləyin.

İsbat:

Bütün keçidlərin bütün uclarını saymaq, bütün düyünlərin bütün dərəcələrini toplamaqla eyni ədədi verir, razılaşırsınız?

Hər bir keçidin 2 ucu olduğundan, bütün keçidin uclarının ümumi sayı bərabər olmalıdır. (Cüt ədədlərin toplanması cüt ədəd verir.)

Bütün düyünlərin dərəcələrini toplamaq üçün cüt ədəd verən cüt dərəcələri toplamaq və tək dərəcələri toplamaq lazımdır.

Tək sayda tək dərəcəli düyünlər olsaydı, bu cəm tək və cüt + tək = tək , beləliklə dərəcələrin ümumi sayı tək olardı. Ancaq bu bütün keçidlərin sayı bütün keçidlərin uclarının ümumi sayına bərabərdir və cütdür.. Buna görə də, tək dərəcəli düyünlərin sayı tək ola bilməz, ocüt olmalıdır.

Məsələn, 1 tək ədəddir, ona görə də yalnız 1 tək dərəcə düyünü olan qrafik yoxdur.

Əgər düyün bərabər dərəcəyə malikdirsə, yəni 2, 4, 6,... keçidləri düyünə yapışdırılırsa, o düyünə gələndə, o düyünün istifadə olunmamış keçidlərin tək sayı sıfırdan böyükdür, ona görə də bu düyündən keçib davam etmək lazım olacaq. Əgər dərəcə təkdirsə, yəni 1, 3, 5,.. keçidlər yapışdırılıbsa, ya bu düyündən yola başlamaq lazımdır, ya da yol bu düyündə bitəcək. Bir yolun yalnız 2 ucu olduğundan, tək dərəcəyə malik yalnız 2 düyünü ola bilər. Buna görə də:

Eyler Dövrünə sahib olmaq üçün qrafikdə yalnız cüt dərəcəli düyünlər, Eyler Yolu üçün isə 2 ədəd tək dərəcəli düyün olmalıdır, bir düyün yolun başlanğıcı, biri isə sonu olacaq. .

Bir keçidin körpü olub-olmadığını yoxlamaq üçün keçidin bir ucundan başlamaq və onun bütün qonşu düyünlərinə, bütün qonşularına və s. keçid etmək lazımdır. Əgər keçidin digər tərəfinə keçmirsinizsə, o zaman keçid bir körpüdür. Bütün qonşuların belə tam axtarışı çox bahalı deyil. Ancaq hər bir keçidi keçməzdən əvvəl bunu etmək lazımdırsa, ümumi səy böyük olacaq. Tam alqoritm 1883-cü ilə aid olan Fleury alqoritmi adlanır.

Daha səmərəli alqoritm Hierholzer (1873) alqoritmidir.

Qrafikdə 2 tək dərəcəli düyün varsa, hər iki halda körpüləri yoxlamadan çox sürətli bir yol tapılır, əks halda dövrdür.

1) Bütün istifadə edilmiş keçidləri çıxardıqdan sonra qalan istifadə olunmamış keçidlərin dərəcəsi bütün keçidlər üçün cütdür.

Niyə?

2) İşlənmiş və işlənməmiş bitişik keçidləri olan ən azı bir düyün olmalıdır.

Niyə?

Çünki 1) bu düyündə başlayan və bitən istifadə olunmamış keçidlərin dövrəsini tapmaq olar. Çünki 2) bu dövr bu düyünə çatdıqda birinci yola/dövrə daxil edilə bilər. İndiyə qədər istifadə edilməmiş keçidlərin dövrlərinin bu şəkildə yerləşdirilməsi bütün keçidlər istifadə olunana qədər təkrarlanır və buna görə də bir Eyler yolu və ya bütün keçidləri istifadə edən Eyler dövrü var.

Bu daha sürətli versiyanın qiyməti neçədir?

Məsələn

     2   4  
    / \ / \ 
   1---3---5

Birinci dövr 1-3-2-1 olsun. 3-cü düyün bu dövrdə və istifadə olunmayan 3-4-5-3 dövründə baş verir. Biz onu birinci dövrə daxil edirik və 1-3-4-5-3-2-1 dövrünü alırıq. Artıq istifadə olunmamış keçidlər yoxdur, ona görə də alqoritm burada başa çatır, biz Eyler dövrünü tapdıq.

İnterfeysimizdən istifadə edərək dövrü necə daxil etmək olar?

Hər dəfə bir düyünə çatdıqda, digərini tərk etdiyiniz üçün cüt sayda keçid istifadə edirsiniz. İndi gəlirsiniz və cüt dərəcəli düyündə bir keçiddən istifadə edirsiniz, beləliklə, cüt dərəcəli düyündə cəmi tək sayda keçiddən istifadə edirsiniz.