6-Mavzu: graflar nazariyasi mavzusiga oid matn Reja: Graflar nazariyasining boshlang’ich ma’lumotlari Graflar ustida amallar

1.6.11-masala. Chizmadagi grafning uchlarini A,B,C,D,E,K,L harflar bilan
belgilang va har bir uchning lokal darajasini aniqlang. 


 
 
1.6.12-masala.  Uchlari soni 6 ga teng bo’lgan orggraf chizing va 
Har bir uchining darajasini aniqlang? M:
… 
1.6.13-masala, V-guruh talabalari to’plami. U-guruh talabalari orasidagi 
partadoshlik holatiga mos keluvchi grafning bir necha kortejlarini tuzing. Bu graf 
no’lgraf, orggraf yoki to’la graf bo’la oladimi? Fikringizni asoslang? 
1.6.14-topshiriq. Siz yashayotgan aholi punkiti yoki uning bir qismida joylashgan 
yo’llar va chorrohalar bilan bog’liq biron masalani graflar yordamida hal qiling? 
 
Debat uchun savollar 
1. 
Graflar nazariyasining yaratilishiga qanday masalaning qo’yilishi sabab 
bo’ldi? 
2. 
“Graf “ iborasi 1- marta kim tomonidan qachon kiritilgan? 
3. 
Grafning ta’rifini ayting? 
4. 
Grafning uchi va qirrasi deganda nimani tushunasiz? 
5.Grafdagi yoy va qirra nimasi bilan farq qiladi? 
6. Qo’shni uchlar qo’shni bo’lmagan uchlardan nimasi bilan farq qiladi? 
7. Oriyentirlanmagan graf va orggraf nimasi bilan farq qiladi?
8. Graflarning qanday turlarini bilasiz? 

---

9. Grafdagi uchning lokal darajasi qanday aniqlanadi? 
10 Oriyentirlanmagan grafda barcha uchlar darajalari yig’indisi bilan qirralari 
orasidagi qanday bog’lanish bor ? 
11.To’la graf deb nimaga aytiladi? 
 
6.2.Graflar ustida amallar 
Graflar ustida grafdan uchni olib tashlash amali quyidagicha: Grafdan 
bitta uchni olib tashlansa uchlari soni bitta kam bo’lgan yangi graf hosil bo’ladi. 
Uchni olib tashlash jatumanida shu uch bilan insident barcha qirralar ham olib 
tashlanadi. 
Shuningdek qirrani olib tashlash amali ham bo’lib, bu amalda qirralardan 
birortasi olib tashlanadi. Qirrani olib tashlash amalida shu qirra bilan insident 
uchni qoldirish ham olib tashlash ham mumkin.
G=(V,U) va 
graflar berilgan bo’lsin. Agar 
va G grafning barcha qirralari 
grafning ham qirralari yani 
bo’lsa, u holda G graf 
grafning qism grafi deb ataladi.
G grafga to’ldiruvchi amalini qo’llash natijasida 
graf hosil bo’ladi. 
Graflar ustida shunday amallarni bajarish mumkinki, ular elementlari berilgan 
grafdagidan ko’proq bo’lgan boshqa graflarni hosil bo’lishiga olib keladi.