Mavzu: gamilton graflari

2-teorema (Dirak). Uchlari soni uchtadan kam bo'lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam bo 'Imasa, bu graf Gamilton grafi bo 'ladi.
Isboti². Uchlari soni m >3 bo'lgan graf berilgan bo'lsin. Bu
mgrafning istalgan v uchi uchun p(v)>— shart bajarilsa-da, u
Gamilton graft bo'lmasin, deb faraz qilamiz.
Tabiiyki, istalgan grafga yetarlicha sondagi yangi uchlarni qo'shib olib, bu uchlarning har birini grafdagi har bir uch bilan qirra orqali tutashtirsak, berilgan grafdan Gamilton grafini hosil qilish mumkin. Bu usul bilan berilgan grafdan Gamilton grafini hosil qilish uchun qo'shilayotgan zarur uchlarning minimal sonini к>0 bilan belgilaymiz.
Yuqorida bayon qilingan usulni qo'llash natijasida hosil bo'lgan grafdagi uchlardan tashkil topgan (v_vw,v₂,...,v^) ketma-ketlikbiron Gamilton sikli bo'lsin, bunda v,,v₂— berilgan grafning uchlari, w esa qo'shib olingan uchlardan biri. Tushunarliki, v₂ uch Vj uchga qo'shni emas, aks holda siklni tuzishda w uchni ishlatmasUgimiz mumkin bo'lar edi. Bu esa кsonining minimalligiga ziddir.
Agar grafdagi Vj uch v_luch bilan qo'shni, v₂ uch esa v₂
uch bilan qo'shni bo'lsa, v₂ uch siklda Vj uchdan bevosita keyingi
uch bo'la olmaydi, chunki bu holda (v₁,w,v₂,...,v₁ ,v₂,..., v_x) siklni
(v,,v_: ,...,v₂,v₂,...,Vj) siklga almashtirish mumkin. Natijada hosil bo'lgan grafning v₂ uchga qo'shni bo'lmagan uchlari soni v_xuchga qo'shni uchlari sonidan kichik emasligi, ya'ni bu son kamida

g a teng ekanligi) ravshan. Boshqa tomondan esa hosilbo'lgan grafning v₂ uchga qo'shni uchlari soni kamida

tengligi ko'rinib turibdi. Hosil bo'lgan grafning har bir uchi bir vaqtning o'zida v₂ uchga qo'shni ham, qo'shnimas ham bo'lishi mumkin emasligidan hosil bo'lgan graf uchlarining umumiy soni(m+k) ushbu 2 у^+/с 1= т+2к sondan kichik emas, ya'nim+k > m +2k. Oxirgi tengsizlik faqat k=0 bo'lgandagina to'g'ridir.
Bu esa k>0 shartiga ziddir. ■

Dirak teoremasi shartlari berilgan grafning Gamilton grafi bo'lishi uchun yetarli, lekin ular zaruriy emas. Bu tasdiq to'g'ri ekanligini 2-shaklda tasvirlangan graf misolida ko'ramiz. Bu grafda sakkizta uch bo'lib (/и=8>3), har bir v (v = l,8) uchning darajasi 3 ga teng: p (v)=3. Dirak
mteoremasidagi p(v)>y shart grafdagi
hech qaysi uch uchun bajarilmasa ham, bu grafda (1,2,3,4,5,6, 7,8,1) ko'rinishdagi Gamilton sikli bor bo'lgani uchun u Gamilton grafidir.
1960-yilda O. Ore quyidagi teoremani isbotladi.
3-teorema (Ore). Agar uchlari soni mga (m>2) teng bo'lgan grafdagi qo'shni bo'lmagan ixtiyoriy uchlar darajalari yig'ndisi m dan kam bo 'Imasa, иholda bu graf Gamilton graft bo 'ladi. Isboti o'quvchiga topshiriq sifatida beriladi.

2-misol.3-shaklda tasvirlangan graflar Gamilton graflariga misol bo'la oladilar.Bir qarashdayoq se-zish mumkin.