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

---

            6-Mavzu: GRAFLAR NAZARIYASI mavzusiga oid matn 

                                  Reja: 

1. Graflar nazariyasining boshlang’ich ma’lumotlari 

 2.Graflar ustida amallar 

3.  L. Eyler va Uilyam Gamilton graflari 

Adabiyotlar 

1.

 

N.  To’rayev, I. Azizov, S. Otaqulov.  “Kombinatorika va graflar 

nazariyasi” Toshkent- “Ilm ziyo”-2009y   

2.

 

 O.Ore. “Teoriya grafov”  M….”Nauka” 1987y 

3.

 

 

 F. Rajabov. S. Masharipov. R. Madrahimov. “Oliy matematika 

“Toshkent”“Turon- Iqbol” 2007 yil 

  

1. Graflar nazariyasining boshlang’ich ma’lumotlari 

 

        

1736 yilda L.Eyler tomonidan qiziqarli amaliy masalalardan biri hisoblangan 

Kyonigsberg

’ 

ko’prigi haqidagi masalaning qo’yilishi va yechilishi graflar 

nazariyasining paydo bo’lishiga asos bo’ldi

1

.  

         V  qandaydir  bo’shmas  to’plam  bo’lsin.  Uning  elementlaridan  tuzilgan 

(v

1

,v

2

) barcha juftliklar (kortejlar) to’plamini V×V bilan belgilaymiz.  

         Ta’rif.  Graf  deb  shunday  (V,U)  juftlikka  aytiladiki,  bu  yerda  (

   

               

 

   

 

          

 

   

 

    

)  V bo’sh bo’lmagan to’plam va 

U – V to’plamning elementlaridan tuzilgan 

  

 

   

 

 

 kortejlar to’plami. 

Grafni elementini ko’rsatish shart bo’lmasa uni lotin alfavitining bitta harfi bilan 

belgilash mumkin. G=(V,U) graf berilgan bo’lsin. V to’plamning elementlariga G 

grafning uchlari, V to’plam esa graf uchlari to’plami, 

  

 

   

 

 

 kortejlar grafning 

qirralari,  yoylari 

  

 

   

 

 

kortejlardan  tuzilgan  U  to’plam  grafning  qirralari  yoki 

yoylari to’plami deyiladi. Agar 

  

 

   

 

 

 grafning qirrasi bo’lsa, u holda 

  

 

   

 va 

                                      

1

 ‘Kyonigsberg-bu shahar 1255-yilda asoslangan bo’lib, 1946 yildan boshlab, Kaliningrad deb 

nomlanadi. Hozir Rossiya Federatsiyasi tarkibida.  

---

  

 

 

 uchlar qoshni uchlar boshqa uchlar esa qoshni bo’lmagan uchlar bo’ladi.  G 

grafning  qirralari  yo’naltirilmagan  (oreyentirilmagan)  yoki    yo’naltirilgan 

(oreyentirilgan) bo’lishi mumkin. 

             Agar  G  grafning  qirralari    yo’naltirilgan  (oreyentirilgan)  bo’lsa 

yo’naltirilgan (oreyentirilgan) graf  yoki qisqacha orggraf deb ataladi. Ikkala uchi 

ustma  –ust  tushgan  qirralalari  bo’lsa,  grafning  bu  elementi  sirtmoq  deyiladi. 

Qirralari orasida sirtmoqlari bo’lgan graf psevdograf deyiladi. 

      Hech  qanday  qirra  bilan  bog’lanmagan  uch  yakkalangan(ajratilgan,  xolis, 

yalang’och)  uch  deyiladi.  Graf  uchiga  insdent  qirralar  soni  shu  uchning  darajasi 

yoki valentligi deb ataladi. Grafdagi a uchning darajasi   

    

  bilan belgilanadi. 

Grafning hamma uchlarining darajasi 3 ga teng bo’lsa, u kubik graf deyiladi.  

          Faqat  uchlardan  iborat  qirrasi  yoq  graf  nolgraf  (bosh  graf)    deyiladi. 

Nolgraf 

  

 

       

 

 

  bilan belgilanadi. 

Istalgan  ikki  uchi  qo’shni  bo’lgan  karrali  qirralarsiz  yo’naltirilmagan 

(oriyentirlanmagan) graf to’la graf deyiladi. Uchlari soni m ga teng bo’lgan to’la 

graf 

 

 

 bilan belgilanadi. 

 

 

 grafning qirralari soni  

                                     

 

 

 

 

      

 

 

  

 ga  teng.  Agar  orggrafning  istalgan  ikki  uchini  yo’nalishlari  qarama-qarshi 

bo’lgan yoylar bilan almashtirilsa, u holda to’la orggraf hosil bo’ladi. 

To’la orggrafning qirralari soni to’la oriyentirlanmagan grafning qirralari sonidan 

ikki barobar ko’pdir, yani  

                                           

 

 

 

          

  boladi 

XVIII asrdayoq L. Eyler graflar haqida quyidagi lemmani isbotlagan. 

1-lemma.  (“ko’rishishlar“  haqida).  Istalgan  oriyentirlanmagan  grafda  barcha 

uchlar darajalari yig’indisi qirralar sonining ikki barobariga teng.