6-Mavzu: graflar nazariyasi mavzusiga oid matn Reja: 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.