1. Graflar nazariyasining boshlang’ich ma’lumotlari Graflar ustida amallar

 

 

 

Grafning  har  bir  uchidan  faqat  bir  marta  o’tadigan  zanjir  Gamilton  zanjiri  deb 

ataladi.  Yopiq  Gamilton  zanjiriga(ya’ni  Gamilton  sikliga)ega  graf  Gamilton  grafi 

deyiladi.  

        Agar grafda yopiq bo’lmagan Gamilton zanjiri topilsa, u holda bunday graf 

yarim  Gamilton  grafi  deb  ataladi.  Gamilton  siklini    tuzishga  doir  samarali 

algoritmlar ham yaratilgan. 1952 yilda G.E.Dirak quyidagi teoremani isbotladi. 

Teorema

.  (Dirak).  Uchlari  soni  uchtadan  kam  bo’lmagan  grafdagi  istalgan 

uchning darajasi uchlar sonining yarmidan kam bo’lmasa, bu graf Gamilton grafi 

bo’ladi. 

Teo’rema

  (Ore).  Agar  uchlari  soni  m  ga  (m>2)  teng    bo’lgan  grafdagi  qo’shni  

bo’lmagan    ixtiyoriy  uchlar  darajalari  yig’indisi    m  dan  kam  bo’lmasa,  bu  graf 

Gamilton grafi bo’ladi.  

   Misol.  1  Shaxmat  oyinidagi  otning  yurishi  haqidagi  Eyler  masalasi  deb 

ataluvchi  quyidagi  masala  Gamilton  grafiga  misol  bo’ladi.  Shaxmat  taxtasining 

istalgan katagida turgan shaxmat oti uchun yurushlarning shunday ketma-ketligini 

tuzingki,  u  barcha  kataklardan  faqat  bir  martadan  o’tsin  va  yurish  boshlangan 

b 

d 

e 

k 

l 

1-rasm 

---

katakka      qaytib  kelsin.  Bunda  shaxmat  kataklari  grafning  uchlari  otning  yurish 

yo’liga esa grafning qirralari mos qo’yilgan.   

 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

    

                                                    11-shakl