Qor mashinasi, ko'chani tozalash yuk mashinasi va pochtachi har bir ko'chadan o'tishi kerak, ammo ko'chadan ikki marta o'tmaslikni istagan mashinalar va odamlarga misoldir.

Graflar nazariyasi matematik Leonhard Euler shu kabi yo'llar ustida ishlayotgan paytda boshlangan.

Euler Königsbergning etti ko'prigi to'g'risida har bir ko'prikdan aniq bir marta o'tib bo'lmasligini isbotlagan maqola yozdi.

Bu haqda ko'proq ma'lumot olish uchun quyidagi muammo xaritasini bosing.

Isbot:

Barcha qirralarning barcha uchlarini hisoblash barcha tugunlarning barcha darajalarini qo'shish bilan bir xil raqamni beradi, rozi bo'ldingizmi?

Har bir qirraning 2 uchi bo'lgani uchun, barcha qirralarning umumiy soni teng bo'lishi kerak. (Juft sonlarni qo'shish juft sonni beradi.)

Barcha tugunlarning darajalarini qo'shish uchun juft darajalarni qo'shish va toq darajalarni qo'shish mumkin.

Agar toq darajali tugunlarning toq soni bo'lsa, bu summa toq bo'ladi va keyin hatto + toq = toq, shuning uchun darajalarning umumiy soni toq bo'ladi. Lekin u barcha qirralarning barcha uchlarining umumiy soniga teng va bu teng. Shuning uchun toq darajali tugunlarning soni toq bo'lishi mumkin emas, u teng bo'lishi kerak .

Masalan, 1 - toq son, shuning uchun faqat 1 toq darajali tugunli grafik yo'q.

Agar tugun teng darajaga ega bo'lsa, ya'ni 2, 4, 6,... qirralar tugunga biriktiriladi, keyin bu tugunga kelganda, foydalanilmagan qirralarning toq soni qoladi, bu noldan katta, shuning uchun bu tugunni tark etib, davom ettirish mumkin. Agar daraja toq bo'lsa, ya'ni 1, 3, 5,.. qirralar biriktirilgan, keyin yo'lni ushbu tugundan boshlash kerak yoki yo'l bu tugunda tugaydi. Yo'lning faqat 2 uchi bo'lganligi sababli, toq darajali faqat 2 tugun bo'lishi mumkin. Shuning uchun:

Eulerian tsikliga ega bo'lish uchun grafikda faqat teng darajali tugunlar bo'lishi kerak, Euler yo'liga ega bo'lish uchun esa 2 ta to'q darajali tugunlar bo'lishi kerak, bitta tugun boshlang'ich va biri yo'lning oxiri bo'ladi.

Chekkaning ko'prik ekanligini tekshirish uchun chekkaning bir uchidan boshlanib, barcha qo'shni tugunlarini va barcha qo'shnilarini va boshqalarni ziyorat qilish kerak. Agar chekkaning boshqa tomoniga etib borilmasa, chekka ko'prikdir. Barcha qo'shnilarni bunday to'liq qidirish unchalik qimmat emas. Ammo agar har bir chekkani kesib o'tishdan oldin buni qilish kerak bo'lsa, unda umumiy harakat katta. To'liq algoritm 1883 yildan beri Fleury algoritmi deb nomlanadi.

Yanada samarali algoritm Hierholzer (1873).

Agar grafikda 2 ta toq darajali tugunlar bo'lsa, unda yo'lni topadi, aks holda tsikl, har ikkala holatda ham ko'priklarni tekshirmasdan juda tez.

1) Barcha ishlatiladigan qirralarni olib tashlagandan so'ng, qolgan foydalanilmagan qirralarning darajasi barcha tugunlar uchun hamdir.

Nima uchun?

2) Ishlatilgan va foydalanilmagan qo'shni qirralarga ega bo'lgan kamida bitta tugun bo'lishi kerak.

Nima uchun?

1 tufayli ushbu tugunda boshlangan va tugaydigan foydalanilmagan qirralarning aylanishini topish mumkin. Chunki 2) ushbu tsikl ushbu tugunga etib borganda birinchi yo'l / tsiklga kiritilishi mumkin. Hozirgacha foydalanilmagan qirralarning tsikllarining bu joylashtirishi barcha qirralar ishlatilguncha takrorlanadi va shuning uchun barcha qirralarni ishlatadigan Euler yo'li yoki Euler tsikli mavjud.

Ushbu tezroq versiyaning narxi qanday?

Misol:

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

Birinchi tsikl 1-3-2-1 bo'lsin. 3 tuguni ushbu tsiklda va foydalanilmagan tsiklda 3-4-5-3 sodir bo'ladi. Biz uni birinchi tsiklga kiritamiz va 1-3-4-5-3-2-1 tsiklini olamiz. Endi foydalanilmagan qirralar yo'q, shuning uchun algoritm bu erda tugaydi, biz Euler tsiklini topdik.

Bizning interfeysimiz yordamida tsiklni qanday kiritish mumkin?

Har safar tugunga kelganida, biri ham tugunni tark etdi, shuning uchun teng sonli qirralar ishlatiladi. Endi biri keladi va teng darajali tugunda bir chekkadan foydalanadi. Shunday qilib, hammasi bo'lib juft daraja tugunidagi qirralarning toq sonini ishlatgan.