21-ma’ruza. Yo’naltirilgan graflarda marshrut, zanjir, sikl (2 soat). Reja

Isboti o‘quvchiga havola qilinadi.
Natija. Karrali qirralari bo‘lmagan sirtmoqsiz tekis -graf uchun tengsizlik o‘rinlidir.
Isboti. Haqiqatdan ham, har bir yoq hech bo‘lmaqanda uchta qirra bilan chegaralanganligi va yoqlarni chegaralovchi qirralarni sanaganda har bir qirra ikki marta hisobda qatnashganligi uchun tengsizlik o‘rinlidir (ta’kidlaymizki, agar grafda uchta uch va ikkita qirra bo‘lsa, u holda tengsizlik bajariladi). tengsizlikdan Eyler formulasini ko‘rinishda qo‘llab, tengsizlikni hosil qilamiz.
Ushbu bobning 2- paragrafida va graflarning planar emasligi ta’kidlangan (isbotsiz keltirilgan) edi. Endi bu tasdiqlarni qat’iy isbotlash mumkin.
Teorema. graf planar emas.
Isboti. planar graf bo‘lsin deb faraz qilamiz. Planar graf uchun tengsizlik o‘rinlidir. graf uchun va bo‘lganligidan bu tengsizlik ko‘rinishdagi noto‘g‘ri munosabatga olib keladi. Demak, graf planar emas.
Teorema. graf planar emas.
Isboti. planar graf bo‘lsin deb faraz qilamiz. Bugrafda 6ta uch ( ) va 9ta qirra ( ) bo‘lgani uchun, Eyler teoremasiga ko‘ra, unda 5ta ( ) yoq bo‘lishi kerak. grafning har bir yoqi kamida to‘rtta qirra bilan chegaralanganligi sababli bu graf uchun tengsizlik o‘rinlidir. Lekin bu tengsizlik graf uchun ko‘rinishdagi noto‘g‘ri munosabatga olib keladi. Demak, graf planar emas.
Isbotlash mumkinki, quyidagi tasdiq o‘rinlidir.
Teorema. Agar biror graf yoki grafga gomeomorf bo‘lgan qism grafga ega bo‘lsa, u holda bu graf tekislikda yotuvchi bo‘lmaydi.
1930 yilda K. Kuratovskiy¹ bu tasdiqqa teskari tasdiqni isbot qildi: agar graf tekislikda yotuvchi bo‘lmasa, u holda u yoki grafga gomeomorf bo‘lgan qism grafga ega bo‘ladi. Umuman olganda, graflarning planarligi haqidagi bu asosiy natija K. Kuratovskiydan oldin 1922 yilda L. S. Pontryagin² tomonidan isbotlangan, lekin bu natija o‘sha vaqtda matbuotda e’lon qilinmagan edi.
Eyler grafi: Bizga yo'naltirilmagan G graf berilgan bo'lsin. Eyler sikli shunday siklki, unda grafning ma'lum bir tugunidan chiqib, barcha qirralardan faqat bir marta o'tib, yana shu tugunga qaytib kelishi kerak.
Grafda Eyler sikli mavjud bo’lishi uchun:
a) Graf bog`langan bo'lishi;
b) Grafning barcha tugunlarining lokal darajalari juft
bo`lishi kerak;
Grafda Eyler zanjiri mavjud bo`lishi uchun:

1. 
   Graf bog’langan bo'lishi;
   

b) Grafning 2 ta tuguni (boshlanish va oxirgi) lokal darajalari toq bo`lib, qolgan barcha tugunlarining lokal darajalari juft bo`lishi kerak.
Agar G yo'naltirilmagan grafda Eyler sikli mavjud bo'lsa, bunday grafga Eyler grafi deyiladi.
Misol. a₁ a₃


a₂ a₄