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

 
Yozma mashq 
1.6.31-topshiriq. 12 –shakldagi graflarni uchlarini belgilang va har bir grafga mos 
ko’phadni yozing? Namuna: b) Shakldagi grafga mos ko’phadni aniqlaymiz. Bu 
oriyentirlanmagan grafda 6 ta uch va 8 ta qirra bor. Uning har bir uchiga bitta 
o’zgaruvchini mos qo’yamiz.
Grafda sirtmoq va karrali graflar yoq 1,3,5,6 uchlar 2 ta dan qirraga insident, 2,4 
uchlar esa 4 tadan qirraga insident. Berilgan grafga mos ko’phad
56 
41 
58 
 
35 
50 
39 
60 
33 
47 
 
44 
55 
40 
59 
34 
51 
38 
42 
57 
 
46 
49 
36 
53 
32 
61 
45 
48 
 
43 
54 
31 
62 
37 
52 
20 
 
5
30 
63 
22 
11 
16 
13 
29 
 
64 
21 
4 
17 
14 
25 
10 
6 
 
1 9 
2 
27 
8 
23 
12 
15 
1 
28
 
7 
18 
3 
26 
9 
24 

---

ko’rinishga ega bo’ladi.
1 2 
3
6 
4 5 
1.6.32- topshiriq. Lotin alifbosi bosma harflaridan quyidagilarni grag sifatida 
qarab, ular orasida Eyler grafi bo’la olmaydiganlarini aniqlang.
 

 
 
 
1.6.33-topshiri q. Yarim Eyler grafi bo’lib Eyler grafi bo’lmaydigan grafga misol 
keltiring? 
a) 
b) c) 
12-shakl 
6.34-topshiriq. 12-shaklda tasvirlangan graflarning har birini Eyler grafi 
yoki Gamilton grafi bo’lishi yoki bo’lmasligini tekshiring va fikringizni yozing? 

---

1.6.35  topshiriq. Graflar nazariyasi mavzusi bo’yicha berilgan 3-, 5-, 9-, va 10- 
shakllarda tasvirlangan graflar orasida qalamni qog’ozdan ko’tarmasdan har bir 
kesmani faqat bir marta chizib (kesmalarning uchlari bundan mustasno) chiqish 
mumkin bo’lganlarini aniqlang. 
1.6.36-topshiriq.Dirak teoremasini qo’llab 
Grafning Gamilton grafi 
bo’lishini isbotlang? 
1.6.37-topshiriq. Eyler grafi bo’ladigan 2 ta yarim Gamilton grafi bo’ladigan 2 ta 
graf chizing va to’g’riligini tushuntirib yozing? 
8-topshiriq. Boshlang’ich sinf matematikasini o’qitishda graflar nazariyasini 
tadbiqiga doir masala yoki biror topshiriqni namunaviy misol sifatida keltiring? 
 
Debat uchun savollar 
1. 
Bog’lamli graf deganda nimani tushunasiz? 
2. 
Zanjir nima? 
3. 
Qanday zanjir sikl deb ataladi? 
4. 
Oriyentirlangan Eyler yo’li deb nimaga aytiladi? 
5. 
Oriyentirlangan Eyler grafi deb nimaga aytiladi? 
6. 
Bog’lamli grafning Eyler grafi bo’lishi haqidagi teoremani ayting? 
7. 
Bog’lamli graf qanday holda yarim Eyler grafi bo’ladi? 
8. 
Flyora algoritmini tushuntiring? 
9. 
Eyler grafiga misol keltiring? 
10. Gamilton zanjiri deb nimaga aytiladi?