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.