Eyler va Gamilton grafi

Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalar universiteti Komputer injiniring 023-21-guruh talabasi Muhammadjonov sherzodbekning diskrit tuzilmalar fanidan bajargan mustaqil ishi

O’qituvchi: Alisher Usmonov

Eyler graflari

Graflar nazariyasining shakllanishi Kyonigsberg
ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi
ma’lum. L. Eyler 1736-yilda bu masalaning yechimga ega emasligini
isbotladi. U graflar nazariyasining ancha umumiy hisoblangan
quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda,
bog‘lamli grafda barcha qirralardan faqat bir marta o‘tadigan sikl
mavjud bo’ladi?
Leonard Eyler
Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir
Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga)
ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo‘lmagan
Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb
ataladi.

1-teorema. Bog‘lamli graf Eyler graft bo‘lishi uchun undagi

barcha uchlaming darajalari juft bo‘lishi zarur va yetarlidir.

Isboti. Zarurligi. G Eyler graflda C—Eyler sikli bo‘lsin.

U holda С sikl bo‘ylab harakatlanganda grafning har bir uchidan

o‘tish uchun bir juft qirradan foydalaniladi — bu qirralardan

biri uchga kirish uchun, ikkinchisi esa uchdan chiqish uchun

zarur bo‘ladi. Bu yerda har bir uch darajasining juftligi С sikldagi

har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi.

Oriyentirlangan graflarda oriyentirlangan Eyler yolini izlash bilan shug‘ullanish mumkin. Har bir yoydan faqat bir marta o‘tadigan yo‘l oriyentirlangan Eyler yo‘li, deb ataladi. Tarkibida oriyentirlangan Eyler yo‘li bor bo‘lgan oriyentirlangan graf oriyentirlangan Eyler grafi, deb ataladi.

Download 6.34 Kb.

1 2 3

Download 6.34 Kb.