Graflar nazariyasi elementlari va ularning masalalar yechishga tadbiqlari - Педагогика - Дипломные работы

Информация о документе

Цена	12000UZS
Размер	769.4KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Педагогика

Graflar nazariyasi elementlari va ularning masalalar yechishga tadbiqlari

Купить

GRAFLAR NAZARIYASI ELEMENTLARI VA ULARNING MASALALAR
YECHISHGA TADBIQLARI
MUNDARIJA
KIRISH : ………………………………………………………………………… 3
I Bob. Maktabda matematika o’qitish jarayonida graflar nazariyasi
elementlari.
1.1-§. Graflar nazariyasi paydo bo’lish tarixi............................................................6
1.2-§. Graflar nazariyasining asosiy
tushunchalari..................................................10
1.3- § . Eyler va Gamilton
graflari.............................................................................13
1.4-§. Labirintlar…………………………………………………………………..15
1.5- §.Rangli qirrali graflar va ularning xossalari....................................................18
II Bob.”Graflar nazariyasi elementlari”tanlov kursining uslubiy ta’minoti
2.1-§. Maktabda garflar nazariyasi elementlarini o’qitish
xususiyatlari..................20
2.2-§. Matematika o’qitishda tanlov kurslarining ahamiyati...................................28
2.3-§. 9-sinf o’quvchilari uchun ”Graflar nazariyasi elementlari” tanlov kursi
dasturi va
mazmuni.............................................................................................................34
XULOSA ................................................................................................................ 56
FOYDALANILGAN ADABIYOTLAR .............................................................. 57
FOYDALANILGAN INTERNET SAYTLARI….............................................. 57
1

KIRI S H
Hozirgi vaqtda diskret matematikaning ahamiyati ortib bormoqda. Bu
ehtimollar nazariyasi, matematik mantiq va axborot texnologiyalarining
rivojlanishi bilan bog‘liq. Diskret matematikaning tarmoqlaridan biri graflar
nazariyasidir. Graflar nazariyasining dastlabki asoslari L. E yler ning ishida 1736-
yilda paydo bo‘lgan, u yerda boshqotirma va matematik m asalala rning
yechimlarini tasvirlab berdi. Graflar nazariyasi XX asrning 50-yillaridan boshlab
kibernetikaning paydo bo‘lishi va kompyuter texnikasining rivojlanishi tufayli
keng rivojlana boshladi .
Boshqotirma va qiziqarli o‘yinlarni hal qilishdan paydo bo‘lgan graf lar
nazariyasi endi keng ko‘lamli muammolar bilan bog‘liq savollar uchun oddiy,
qulay va kuchli vositaga aylandi. Graflar nafaqat fanda , balki kundalik hayotda
mavjud . Masalan, yo‘l xaritasi, metroning sxematik tasviri, yulduzli osmon
xaritasi, molekulyar kimyoviy birikmalar va odamlar o‘rtasidagi munosabatlar.
Ko‘pchilik kompyuter dasturlari asosida zamonaviy kommunikatsiya va
texnologik jarayonlarni amalga oshirishga imkon beradigan graflar ham yotadi.
Graflar nazariyasi iqtisodiyot va statistika, kimyo va biologiyada qo‘llaniladi.
Graflar nazariyasi orqali matematik usullarning fan va texnikaga kirib borishi ro‘y
bermoqda. Graflar nazariyasi tez rivojlanmoqda, yangi tadbiqlari ishlab
chiqilmoqda.
Graflar nazariyasi maktab o‘quv dasturida o‘rganilmaydi, chunki o‘quv
dasturi tig‘iz, lekin maktab o‘quvchilari uchun matematika olimpiadalarida
ko‘pincha graflarga oid masalalar ko‘p uchraydi. Shuning uchun o‘quvchilarni
fakultativ darslarda graflar nazariyasi bilan tanishtirish, graflar nazariyasi nuqtai
nazaridan ishlashga, masalalar yechishda undan foydalanish va qo‘llashga
o‘rgatish kerak. Axir, graflar matematik fikrlash rivojlanishga hissa qo‘shadi
Graflardan foydalanish maktab o‘quvchilari uchun hech qanday qiyinchilik
tug‘dirmasdan, o‘rganishning ko‘rgazmaligiga hissa qo‘shishi mumkin, bunda
haqiqiy ob’ektlar ularning ramziy tasviri bilan almashtiriladi.
3

Bundan tashqari, graflar nazariyasi o‘quvchilarga matematikaning
go‘zalligini tushunishga imkon beradi va bu, o‘z navbatida, tarbiya va
motivatsiyadir.
Yuqoridagilarning barchasi tadqiqotning dolzarbligini belgilaydi.
Tadqiqot maqsadi : umumta’lim maktabining 9-sinf o‘quvchilari uchun
"Graf nazariyasi elementlari" tanlov kursini nazariy va mazmunli asoslash
Tadqiqot ob’ekti va predmeti : umumta’lim maktabidagi fakultativ
mashg‘ulotlarda graflar nazariyasi elementlarini o‘qitish jarayoni.
Tadqiqot predmeti umumta’lim maktablarida graflar nazariyasi asoslarini
o‘qitish metodikasi.
Gipoteza : graflar nazariyasi bo‘yicha fakultativ darslarni o‘tkazish
o‘quvchilarda matematik tafakkurni rivojlantirishga yordam beradi
Tadqiqot davomida quyidagi vazifalar qo‘yildi:
1. Tadqiqot muammosi bo‘yicha o‘quv - uslubiy va psixologik - pedagogik
adabiyotlarni o‘rganish va tahlil qilish.
2. Graflar nazariyasining asosiy tushunchalari va tasdiq larini o‘rganish.
3. Masalani yechishga o‘rgatish vositasi sifatida graflardan foydalanish
imkoniyatlarini ochib beri sh .
4. Sinfdan tashqari mashg‘ulotlarning matematika o‘qitishning o‘quv shakli
sifatidagi rolini o‘rgani sh
5. Umumta’lim maktabining 9-sinf o‘quvchilari uchun “Graflar nazariyasi
elementlari” fakultativ kursi dasturini ishlab chiqish.
6. 9-sinf o‘quvchilari uchun “Graflar nazariyasi elementlari”mavzusidagi
tanlov kursi mazmunini va ularni amalga oshirish metodikasini ishlab chiqish.
Ishning tuzilishi : malakaviy bitiruv ishi kirish, ikki bob, xulosa,
foydalanilgan adabiyotlar ro‘yxati va ilovadan iborat.
Kirishda tadqiqot muammosining dolzarbligi mantiqiy asoslab
berilgan,uning dastlabki parametrlari tavsiflanadi.
Birinchi bobda graflar nazariyasining nazariy asoslari yoritilgan.
4

Ikkinchi bobda matematika o‘qitish shakllari sifatida sinfdan tashqari
mashg‘ulotlarning roli tasvirlangan, umumta’lim maktablarining 9-sinf
o‘quvchilari uchun “Graflar nazariyasi elementlari” tanlov kursining dasturi va
mazmuni keltirilgan.
Xulosa tadqiqot natijalariga asoslangan xulosalarni o‘z ichiga oladi.
Ishning natijalari quyidagi maqolada o’z aksini topgan :
Ostonov Q. Qurbonova F. MAKTABDA GRAFLAR HAQIDA ASOSIY
TUSHUNCHALARNI O’RGANISH. “OLIY TA’LIMNI RAQAMLASH-
TIRISH MUHITIDA INNOVATSION TEXNOLOGIYALAR: MUAMMO VA
YECHIMLAR-2024” xalqaro ilmiy-amaliy konferensiya KONFERENSIYA
MATERIALLARI TO’PLAMI (O’zbekiston Respublikasi,Jizzax shahri,14-15-
mart 2024-yil)(2-QISM) 351-357-betlar
5

I BOB. MAKTABDA MATEMATIKA O‘QITISH JARAYONIDA
GRAFLAR NAZARIYASI ELEMENTLARI
1. 1- §. Graflar nazariyasining paydo bo‘lishi tarixi
Graflar nazariyasi diskret matematikaning graflarning xossalarini
o‘rganuvchi bo‘limidir. Uzoq vaqt davomida graflarni o‘rganish butunlay
jumboqlar, o‘yinlar va o‘yinga bog’liq muammolar bilan bog‘liq bo‘lgan "bema’ni
mavzu" deb hisoblangan. Graflar nazariyasi juda uzoq vaqt davomida
matematikada ilmiy tadqiqotlarning asosiy yo‘nalishlaridan chetda edi, uning
iste’dodlari faqat mutaxassislarning kichik doirasini qiziqtiradigan - topologiya
zamonaviy matematikaning o‘ta murakkab bo‘limning e’tiborini tortganidan so‘ng
to‘liq namoyon bo‘ldi;
Alohida matematik fan sifatida graflar nazariyasi birinchi marta 20-asrning
30-yillarida V enger matematigi Kyonigning ishida taqdim etilgan edi. So‘nggi
paytlarda graflar va ular bilan bog‘liq tegishli tadqiqot usullari turli darajada
zamonaviy matematika turli sohalari deyarli to‘liq qamrab olingan .

L.Eyler(1707-1783)
Graflar nazariyasining otasi Eylerdir. 1736 yilda o‘sha paytda ma’lum
bo‘lgan Kyonigsberg ko‘priklari muammosi deb nomlangan muammoni yechdi.
Kyonigsberg shahrida ikkita orol bor edi. Bu orollar yettita ko‘prik orqali Pregol
6

daryosi qirg‘oqlari va bir-biri bilan bog‘langan. Muammo quruqlikning barcha
to‘rt qismidan o‘tadigan ularning har qandayidan boshlanib, xuddi shu qismda
tugaydigan va har bir ko‘prikdan bir marta o‘tuvchi marshrutni topishni talab
qildi. Eyler bunday marshrutning mumkin emasligini isbotladi va shu bilan ushbu
muammoni hal qilishga o‘z hissasini qo‘shdi.
Bu muammoning yechimi yo‘qligini isbotlash uchun Eyler yerning har bir
qismini nuqta (uch),har bir ko‘prikni esa tegishli nuqtalarni bog‘laydigan chiziq
(qirra) bilan belgiladi, nuqtalar yerning to‘rtta qismi bilan bir xil harflar bilan
belgilangan "graf" hosil bo‘ldi. Eylerning ushbu muammoning "ijobiy" yechimi
yo‘qligi haqidagi tasdig‘i grafni maxsus tarzda aylanib o‘tishning mumkin
emasligi haqidagi tasdiqqa teng kuchli.
Ushbu alohida holatdan kelib chiqib, Eyler muammoni shakllantirishni
umumlashtirdi va berilgan graf uchun aylanma yo‘l (maxsus marshrut) mavjudligi
mezonini topdi, ya’ni graf bog‘langan bo‘lishi va uning har bir uchiga juft sondagi
qirralar kelib tushishini aniqladi .
1847-yilda Kirxgof chiziqli algebraik tenglamalarning birgalikdagi
sistemasini yechish uchun daraxtlar nazariyasini ishlab chiqdi, bu har bir
o‘tkazgichda (yoyda) va ko‘rib chiqilayotgan elektr zanjirining har bir konturida
tok kuchi qiymatini topishga imkon berdi. U fizik bo‘lsada, masalani yechishga
matematiklardek yondashgan. U qarshiliklarni, kondensatorlar, induktivlik va
h.k.larni o‘z ichiga olgan elektr sxemalar va zanjirlardan abstrakt qilish orqali
faqat uchlar va bog‘lanishlarni (qirralar yoki yoylar)ni o‘z ichiga olgan mos
kombinatsion tuzilmalarni ko‘rib chiqdi va bog‘lanishlar uchun ular qanday
turdagi elektr elementlarga mos kelishini ko‘rsatish shart emas. Shunday qilib,
haqiqatda Kirxgof har bir elektr zanjirini o‘ziga mos keladigan graf bilan
almashtirdi va tenglamalar tizimini yechish uchun elektr zanjiri grafning har bir
siklini alohida ko‘rib chiqish kerak emasligini ko‘rsatdi. Buning o‘rniga u oddiy,
ammo samarali texnikani taklif qildi, unga ko‘ra faqat uning har qanday “asosiy
daraxtlari” bilan aniqlanadigan bog‘liqmas oddiy graf sikllari bilan cheklanish
kifoya[1].
7

Keli organik kimyoning sof amaliy masalalari bilan shug‘ulanayotgada, 1857-
yilda daraxtlar deb nomlangan muhim graflar sinfini kashf etdi. U ma’lum
miqdordagi uglerod atomlari bilan to‘yingan uglevodorodlarning izomerlarini
sanab o‘tishga harakat qildi. Albatta, Keli, birinchi navbatda, masalani mavhum
shakllantirdi: har birining 1 va 4 darajali uchlari bo‘lgan r uchli barcha daraxtlar
sonini topish. Lekin masala birdaniga yechilmadi va u masala bayonini : a) ildizli
daraxtlar; b) barcha daraxtlar; v) uchlari darajalari 4 dan oshmaydigan daraxtlar va
nihoyat, d) uchlari darajalari 1 va 4 ga teng daraxtlarni sanab o‘tish haqidagi yangi
masalani yechish mumkin bo‘lgan qilib o‘zgartirdi.
1869 yilda Jordan, hatto kimyo sohasidagi o‘z kashfiyotining ahamiyatiga
e’tibor qilmasdan, daraxtlarni sof matematik ob’ektlar sifatida kiritdi va o‘rgandi.
1859 yilda ser Uilyam Gamilton "Dunyo bo‘ylab" o‘yinini o‘ylab topdi.
O‘yinda 20 ta uchining har biriga mashhur shahar nomi berilgan dodekaedr
qo‘llaniladi. O‘yinchi har bir uchidan bir marta o‘tadigan ko‘pyoqning qirralari
bo‘ylab yopiq yo‘lni topib, "dunyo bo‘ylab" ni aylanib o‘tishi kerak. Gamilton o‘z
g‘oyasini 25 gvineya uchun bitta o‘yinchoq ishlab chiqaruvchiga sotdi, bunda u
shafqatsizlik qildi, chunki bu o‘yin hech qanday moliyaviy muvaffaqiyat
keltirmaydi[2].
Bu masala graflar nazariyasi tilida quyidagicha ifodalanadi: dodekadr grafda
asosiy siklni toping. Asosiy siklning mavjudligi aniq.
1878 yilda ingliz matematigi A. Keli to‘rt rangning mashhur hal qilinmagan
muammosini nashr etdi. Har qanday matematik bu ajoyib masalani har birimizga
atigi besh daqiqada tushuntirib bera oladi, lekin hamma muammoni tushunadi,
lekin uni hal qilishning iloji yo‘q.
Oradan roppa-rosa bir yil o‘tgach, V.Kempe gipotezaning birinchi isbotini
keltirdi, o‘n bir yildan so‘ng P.Xivud bu isbotda xatolikni topdi va shu bilan birga
undan muhim narsani chiqarib, har qanday xarita, hatto eng murakkab
konfiguratsiyaga rang berish uchun beshta rang yetarli ekanligini isbotladi.
Birinchi noto‘g‘ri isbotdan keyin boshqa isbotlar paydo bo‘ldi. O‘tmishdagi
ko‘plab mashhur matematiklar to‘rtta rang muammosini o‘rganishgan, ammo
8

ularning hech biri gipoteza sirini ochib bermagan. Har qanday sondagi
mamlakatlar uchun farazni isbotlash uchun ko‘plab muvaffaqiyatsiz urinishlar
bo‘lgan, keyin matematiklar buni kichik natural sonlardan boshlab isbotlashga
qaror qilishgan. Shunday qilib, P. Franklin 1913 yilda 25 dan ortiq davlat
bo‘lmagan xarita uchun gipotezani isbotladi, vaqt o‘tishi bilan u bu raqamni 38
taga ko‘paytirdi. Mamlakatlar sonining ko‘payishi bilan ularning nisbiy joylashuvi
uchun turli xil variantlar soni va xaritalarni bo‘yash variantlar soni oshib bordi.
To‘rt rang muammosi butunlay yechib bo‘lmaydigan muammo bo‘lib qoldi.
Matematiklar yuz yildan ko‘proq vaqt davomida isbot topa olmadilar. Faqat
1976 yilda Illinoys universitetidan K. Appel va V. Xaken gipotezani isbotlay
olishdi. Ammo ular bu muvaffaqiyatga innovatsion qadam - matematik teoremani
isbotlashda kompyuterdan foydalanish tufayli erishdilar. Ularning isboti g‘oyasi
quyidagicha edi: dastlab, rang berish imkoniyati bir qator p ta davlat ?????? ≥ ??????
0 , bo‘lgan
xaritalar uchun isbotlanadi, so‘ngra kompyuter yordamida ?????? < ??????
0 uchun xaritalarni
bo‘yash imkoniyati tasdiqlangan. Ko‘p sonli variantlardan o‘tgandan so‘ng, isbot
kompyuterning ming soatdan ko‘proq vaqtini oldi, kompyuter gipotezaning
haqiqiyligini tasdiqladi. Shunday qilib, to‘rt rangning azaliy muammosi hal qilindi.
1936 yilda psixolog Levin shaxsning "yashash maydoni"ni planar xarita
yordamida tasvirlash mumkinligini taklif qildi. Bunday xaritada joylar insonning
turli xil faoliyat turlarini, masalan, ishda, uyda nima qilayotganini yoki sevimli
mashg‘ulotlarini aks ettiradi[3].
Ilmiy-tadqiqot guruh dinamikasi markazi psixologlari grafning boshqa
psixologik talqiniga olib keldi
Ushbu talqindagi odamlar uchlar, ularning munosabatlari esa qirralar sifatida
ifodalanadi. Bunday munosabatlarga misollar, masalan, sevgi, nafrat, muloqot,
bo‘ysunish.
Nazariy fiziklar o‘z fanlarining ichki ehtiyojlari uchun graflar nazariyasini
bir necha marta "kashf qildilar".Sof matematika doirasida graflar nazariyasi
birinchi marta Veblen tomonidan topologiya bo‘yicha klassik kitobida o‘rganilgan.
9

20-asrda matematikaning: algebra, ehtimollar nazariyasi, sonlar nazariyasi,
topologiya va boshqalar bo‘limlarda graflar bilan bog‘liq muammolar paydo
bo‘ldi.
Bu bo‘limlarning usullari graflar nazariyasi masalalarini yechishda
muvaffaqiyatli qo‘llanila boshlandi. "Graf" atamasi bilan bir qatorda 20-asr
boshida sinonim sifatida boshqa atamalar ham ishlatilgan, masalan, xarita,
kompleks, diagramma, tarmoq, labirint.
20-asrning 50-yillaridan boshlab kompyuter texnikasining rivojlanishi va
kibernetikaning paydo bo‘lishi munosabati bilan graflar nazariyasi yanada
rivojlandi.
1.2- §. Graflar nazariyasining asosiy tushunchalari
Graf bo‘sh bo‘lmagan nuqtalar to‘plami va ikkala uchi ham berilgan nuqtalar
to‘plamiga tegishli kesmalar to‘plamidan iborat. Sxemalar va rasmlarda kesmalar
to‘g‘ri chiziqli yoki egri chiziqli bo‘lishi mumkin va kesmalarning uzunligi va
nuqtalarning joylashuvi ixtiyoriydir. Nuqtalar grafning uchlari, kesmalar esa
qirralar deyiladi. Hech qanday qirraga tegishli bo‘lmagan uchlar deb ataladi.
Ajralgan uchlardan tashkil topgan graf - nol graf (1.1-rasm).
1.1-rasm- Nol graf
Agar grafning har ikki turli uchi bitta va faqat bitta qirra bilan bog‘langan
bo‘lsa, bunday graf to‘liq deb ataladi (1.2-rasm). To‘liq grafda har bir uch bir xil
sondagi qirralarga tegishli. To‘liq grafni aniqlash uchun uning uchlari sonini bilish
kerak. Bir qirra bilan bog‘langan ikkita uch qo‘shni deyiladi. Umumiy uchiga ega
bo‘lgan ikkita qirra (bu uchga tutashgan) ham qo‘shni deyiladi.
10

1.2-rasm – To‘liq graf
Bitta uchdan chiqadigan qirralarning soni uchning darajasi deyiladi
Uchlar juft (juft darajaga ega bo‘lsa) va toq (agar ular toq darajaga ega
bo‘lsa) bo‘lishi mumkin. Grafning uchlarining darajalari haqida faqat graf haqida
umumiy tasavvurga ega bo‘lish orqali bilib olish mumkin, masalan, to‘liq grafning
har bir uchining darajasi uning uchlari sonidan bittaga kam .
Agar grafning uchlari harflar, raqamlar yoki boshqa ma’lumotlar bilan
bog‘langan bo‘lsa, unda bunday graf belgilangan graf deyiladi. Agar grafning
qirralariga ma’lum og‘irliklar berilgan bo‘lsa, bunday graf vaznli graf deb
ataladi. Agar yo‘nalishni ko‘rsatadigan o‘qlar grafning chetlariga qo‘llanilsa, u
holda grafning bu yo‘naltirilgan qirralari yoylar deb ataladi.
Agar grafning barcha qirralari yo‘naltirilgan bo‘lsa, unda bunday graf
yo‘naltirilgan yoki orgraf deb ataladi. Graflar ro‘yxatlar, jadvallar va ifodalar
ko‘rinishida ham taqdim etilishi mumkin.
Grafning uchlari nuqtalar, doiralar,uchburchaklar, qirralari esa - kesmalar,
tekis yoki majoziy ma’nodagi egri chiziqlar bilan tasvirlanishi mumkin. Ushbu
xilma-xillikni hisobga olgan holda, ikkita graf tasviri qachon ekvivalentligini
(izomorf) aniqlash imkoniyatiga ega bo‘lish muhimdir.
Ekvivalent graf tasvirlari bir xil uchlarni va ular orasidagi bir xil
bog‘lanishlarni o‘z ichiga oladi. Boshqacha qilib aytganda, ikkita tasvirning
uchlari va qirralari o‘rtasida o‘zaro bir qiymatili moslik bo‘lishi kerak, shunda
ikkala holatda ham uchlarning darajalari bir xil bo‘ladi.(1.3-rasm).
11

1.3-rasm Bitta grafning turli xil ko‘rinishlari
Graflar nazariyasida graflarning uch turi mavjud: oddiy , multigraflar va
psevdograflar (1.4-rasm).
1.4-rasm. Uch turdagi graflar
Agar graf oddiy bo‘lsa, unda uning uchlarini faqat bitta qirra bilan ulash
mumkin, lekin bir nechta qirralar bo‘lsa, bu graf multigraf bo‘ladi. Multigrafning
uchi o‘z-o‘zidan ulanishi mumkin bo‘lgan holatdagi graf psevdograf deb ataladi,
agar qirraning boshi va oxiri bir uchda bo‘lsa, u tugun deyiladi .
Grafdagi yo‘l - bu har ikki qo‘shni uch bir qirra bilan bog‘langan uchlarning
har qanday ketma-ketligi. Yo‘lning uzunligi - undagi qirralarning soni. Agar
yo‘lning birinchi va oxirgi uchlari ustma-ust tushsa va undagi barcha qirralar har
xil bo‘lsa, bunday yo‘l sikl deb ataladi . Har qanday siklni ko‘pburchak sifatida
graf tasvirlash mumkin (1.5-rasm).
1.5-rasm. Sikllarga misollar
12

1.3- §. Eyler va Gamilton graflari
Eyler yo‘li - bu grafning barcha qirralarini o‘z ichiga olgan yo‘l va Eyler
sikli yoki Eyler zanjiri - bu grafning barcha qirralari faqat bir martadan o‘z ichiga
olgan sikl. Bunday siklni o‘z ichiga olgan graf Eyler grafi deyiladi. Tekislikda
yopiq egri chiziqlarni har bir bo‘limni bir marta aylanib o‘tish bilan chizish kerak
bo‘lgan jumboq muammolari Eyler graflariga doir masalalarga misollardir. Graf
Eyler chizig‘iga ega bo‘lishi uchun u bog‘langan bo‘lishi kerak. Har bir Eyler
chizig‘i har bir uchga kirishi va chiqishi bir xil sonda bo‘lishi lozim, shuning
uchun grafning barcha uchlari darajalari juft bo‘lishi kerak . Bularning barchasi
Kyonigsberg ko‘priklari muammosida mavjud. Graf Eyler chizig‘iga ega bo‘lishi
uchun ikkita zarur shart bajarilishi kerak. 1) Bu grafning barcha uchlarining
bog’liqligi va 2) darajalarining juftligidir. Eyler bu shartlar ham yetarli ekanligini
isbotladi . [2]
Eylerning Kyonigsberg ko‘prigidagi muammosini umumlashtirish mumkin:
"Qaysi graflar uchun grafning har bir qirrasi ishtirok etadigan va faqat bir marta
qatnashadigan siklni topishimiz mumkin?" Bu savolga javob quyidagi teorema
orqali beriladi.
Teorema . Graf Eyler grafi bo‘ladi faqat va faqat u bog‘langan va uning
har bir uchining darajasi juft bo‘lsa
Isbot. Agar graf Eyler grafi bo‘lsa, u holda u bog‘langan va uning har bir
uchining darajasi juft bo‘ladi (Kyonigsberg ko‘priklari masalasidagi kabi). Har bir
uchining darajasi juft bo‘lgan bog‘langan graf Eyler grafi ekanligining teskarisini
isbotlaylik.
Har safar yangi qirralardan o‘tib, qandaydir p uchidan grafani aylanib
o‘tishni boshlaylik. Har bir uchining darajasi juft bo‘lgani uchun, bu o‘tish faqat p
da tugaydi. Bu grafning sikli borligini bildiradi. Uni c
1 deb belgilaymiz. Ushbu
siklning qirralarini o‘chirib tashlaymiz. Graf qismlarga bo‘linadi, ularning har biri
bog‘langan graf va olib tashlangan c
1 sikl bilan umumiy uchga ega.
13

Har bir uchning darajasi ham juft. Olingan grafning qirralari bo‘lmasa, unda
teorema isbotlangan. Aks holda, unga yuqoridagi fikrlarni qo‘llaymiz. Shu tarzda
harakat qilib, berilgan grafni sikllarga ajratamiz. c
1 sikli bilan v uchga ega bo‘lgan
c
2 siklni ko‘rib chiqaylik. V dan boshlanuvchi c
1 sikldan va darhol keyingi c
2
siklidan iborat bo‘lgan yo‘l yopiq va bu ikki siklning qirralarini o‘z ichiga oladi.
Ushbu protsedurani davom ettirsak, biz bir martadan grafning barcha
qirralarini o‘z ichiga olgan siklni qurishimiz mumkin. Binobarin, ko‘rib
chiqilayotgan graf Eyler grafi bo‘ladi, shuni isbotlash talab qilingan edi.
Eyler graflariga misollar:
1. Ko‘rgazma rejasi, agar uning eksponatlari zallarning ikki tomoniga
joylashtirilsa, ya’ni yopiq marshrutni yaratish mumkin, uning yordamida tashrif
buyuruvchi har bir zaldan ikki martadan - har tomondan har xil yo‘nalishlarda bir
martadan yurishi mumkin.
2. Har bir ko‘cha bo‘ylab roppa-rosa ikki marta - har bir yo‘nalishda bir
martadan yurib, istalgan shaharni aylanib chiqish mumkin.
Gamilton grafi, sikli, yo‘li Irland matematigi Uilyam Gamilton nomi bilan
bog‘langan .U1859 yilda dodekaedrda "dunyoni aylanib o‘tish" muammosini
tadqiq qilganda, bu sinflarni aniqladi.Bu muammoda dodekadrning uchlari
Bryussel, Yedinburg, Frankfurt va boshqalar kabi mashhur shaharlarni ifodalagan,
qirralari esa ularni bog‘laydigan yo‘llar edi. Sayohatchi barcha uchlardan bir marta
o‘tadigan yo‘lni topib, "dunyo bo‘ylab" borishi kerak. Vazifani yanada qiziqarli
qilish uchun shaharlardan o‘tish tartibi oldindan belgilanadi. Allaqachon
bog‘langan shaharlarni eslab qolishni osonlashtirish uchun dodekadrning har bir
uchiga mix qo‘yilgan va yotqizilgan yo‘l mixga o‘ralishi mumkin bo‘lgan kichik
arqon bilan belgilangan. Ammo bu dizayn juda mashaqqatli bo‘lib chiqdi va
Gamilton o‘yinning yangi versiyasini taklif qildi, dodekaedrni dodekaedrning
qirralarida qurilgan grafga izomorf planar graf bilan almashtirdi .[1]
Har bir uchidan aniq bir marta o‘tadigan yo‘lga Gamilton yo‘li deyiladi va
agar bu yo‘l yopiq bo‘lsa, u Gamilton siklidir. Gamilton siklini o‘z ichiga olgan
graf – Gamiltonian.
14

Berilish usullari bo‘yicha Eyler va Gamilton yo‘llari va sikllari o‘xshashdir.
Eyler yo‘llari va sikllari barcha qirralarni o‘z ichiga oladi va har birini bir martadan
o‘tadi, gamilton yo‘llari esa barcha uchlarini o‘z ichiga oladi va har birida bir
martadan o‘tadi.Grafda Eyler yo‘li yoki sikli borligini bilish uchun uning har bir
uchining darajasini aniqlash, lekin grafning Gamilton yo‘li yoki sikli borligini
aniqlashning hech qanday usuli yo‘q. Bu muammoning yechimi amaliy
ahamiyatga ega, chunki Gamilton o‘yini bir nechta nuqtalarni aylanib, qaytib
kelishi kerak bo‘lgan sayohatchi sotuvchining taniqli muammosi yaqin. U har bir
nuqtaga aniq bir marta tashrif buyurishi shart va sayohatga imkon qadar kamroq
vaqt sarflashdan manfaatdor. Va buning uchun shaharlarga tashrif buyurish barcha
variantlarni aniqlashi kerak va har bir holatda sarflangan vaqtni hisoblash talab
etiladi.
Graflar nazariyasida grafda Gamilton sikllarining mavjudligining bir qancha
yetarli shartlar mavjud:
1. Har bir to‘liq grafik Gamiltoniandir, chunki u berilgan grafning barcha
uchlarini o‘z ichiga olgan oddiy siklni o‘z ichiga oladi.
2. Agar grafda uning barcha uchlari orqali o‘tuvchi oddiy sikldan tashqari
boshqa qirralar ham bo‘lsa, bu graf ham Gamiltonian bo‘ladi.
Agar grafda bitta Gamilton sikli bo‘lsa, unda boshqa Gamilton sikllari ham
bo‘lishi mumkin.
Grafda Gamilton siklining mavjudligi haqidagi savolga mashhur Dirak
teoremasi javob beradi.
Teorema. Agar n ( ≥ 3) uchli oddiy grafda har bir uchning lokal darajasi
kamida n/2 bo‘lsa, u holda graf gamiltonian.
1.4- §. Labirintlar
Labirintlar haqidagi muammolar qadimgi davrlarda paydo bo‘lgan. O‘sha
paytda qal’alar atrofida faqat qal’a egasi biladigan reja bo‘yicha inshootlar
(labirintlar) qurilgan. Urush paytida bu inshootlar boshpana yoki zargarlik
buyumlari saqlanadigan joy bo‘lib xizmat qilgan. Ba’zan ular jazo uchun
15

ishlatilgan, u yerda o‘lim jazosiga hukm qilingan odamlarni joylashtirishgan.
Labirintning tuzilishini bilmagan holda, odam undan chiqish yo‘lini topa olmadi va
uzoq vaqt sarson bo‘lgach, ochlikdan vafot etgan . Ammo, aslida, umidsiz
labirintlar yo‘q, uni aniqlash va eng chalkash labirintdan chiqish yo‘lini topish
unchalik qiyin emas;
Labirint so‘zining ma’nosi nima? "Labirint" so‘zi "Labrys" so‘zidan kelib
chiqqan - qurol bo‘lib qo‘sh pichoqli bolta qadimgi Yunonistonda shunday
nomlangan. Qadimgi xudo Ares-Dionis osmondan Yerga tushdi, unda hali hech
narsa yo‘q edi, faqat zulmat. Ares-Dionis o‘ziga labris bilan zulmatni kesib,
jo‘yaklarni kesib yo‘l ochdi. U doiralar bo‘ylab yurdi. Va u ochgan yo‘l tobora
yorug‘roq bo‘la boshladi, ya’ni "labirint " shunday paydo bo‘lgan. Odamlar turli
xil murakkab va "umidsiz" labirintlarni ixtiro qilishga harakat qilishdi. Ammo
umidsiz labirintni qurish yoki hatto chizish mumkinmi? Bu savolga javob 18-
asrning atoqli matematigi Eyler tomonidan berilgan. Uning tadqiqotlari umidsiz
labirintlar yo‘q degan xulosaga keldi. Labirintlar–tor yo‘laklari, kirish va
chiqishlari chalkashbo‘laklar yo‘laklar.
Labirint muammosining geometrik qo‘ylishi quyidagicha: yo‘llar,
xiyobonlar, yo‘laklar, shaxtalar, galereyalar va boshqa labirintlar cho‘zilib ketgan,
har tomonga, turli yo‘nalishlarda tarmoqlanib ketadi, kesishadi, berk yuklaklarni
hosil qiladi va hokazo.[1]
Labirint - bu graf va uni o‘rganish - bu graf yo‘lni topishdir.
Grafning barcha qirralarini aylanib o‘tish usuli, masalan, labirintdan
chiqishga imkon beradigan yo‘lni topish uchun ishlatilishi mumkin. Labirintlardagi
marshrutlar graflar bilan ifodalanishi mumkin. Grafning qirralari koridorlar,
uchlari esa kirishlar, chiqishlar, chorraxalar va berk yo‘llar oxiri. Agar labirintning
sxemasi grafga aylantirilsa, unda bu labirintni tushunish ancha oson bo‘ladi.
Taqdim etilgan labirintlarning graflarida maqsadga olib boradigan to‘g‘ridan-
to‘g‘ri yo‘lni ko‘rish oson.
Labirint bilan bog‘liq muammolarni ikki guruhga bo‘lish mumkin:
16

a) harakatning boshlang‘ich va tugash nuqtalari ko‘rsatilgan bo‘lsa,
labirintda yo‘l topish kerak bo‘lgan masalalar;
b) labirintdan chiqish yo‘lini topish zarur bo‘lgan masalalar .
Bunday masalalarni yechish uchun fransuz matematigi M. Tremot quyidagi
qoidalarni belgiladi:
1. Biz tanlangan uchdan (birinchi chorraha) boshlaymiz va yo berk yo‘lak
oxiriga (uchgacha) yoki yangi chorrahaga (uchga) kelgunimizcha istalgan qirra
bo‘ylab yuramiz. U holda:
a) Agar biz boshi berk ko‘chaga yetganimiz aniqlansa, orqaga qaytamiz va
o‘tgan qirrani allaqachon tashlab yuborish kerak, chunki uni ikki marta (u yerga va
orqaga) bosib o‘tdik.
b) Agar biz yangi chorrahaga kelsak, u holda biz har safar kelgan yo‘lni va
keyingi yo‘lni belgilashni unutmasdan, yangi ixtiyoriy qirra bo‘ylab boramiz.
2. Yangi yo‘l bo‘ylab bizga ma’lum bo‘lgan chorrahaga yetib borganimizdan
so‘ng, darhol bu yo‘lni ikki chiziq bilan belgilab, darhol orqaga qaytishimiz kerak
(1.6-rasm).
1.6-rasm – 2-qoida
3. Agar biz bir marta bosib o‘tgan yo‘l bo‘ylab ma’lum chorrahaga kelsak, u
holda bu yo‘lni ikkinchi chiziq bilan belgilab, hali o‘tmagan yo‘l bo‘ylab, agar
shunday yo‘l mavjud bo‘lsa. Bu holat rasmda ko‘rsatilgan (1.7-rasm).
1.7-rasm – 3.1-qoida
Agar bunday yo‘l bo‘lmasa, u holda bir marta bosib o‘tgan yo‘lni tanlaymiz.
Bu holat rasmda ko‘rsatilgan (1.8-rasm).
17

1.8-rasm – 3.2-qoida
4. Bir qo‘l qoidasi. Bu devordan bir qo‘lni (o‘ng yoki chap) olmasdan
labirint orqali harakat qilishdan iborat.
1882 yilda Tremo murakkab, ko‘p bog‘lamli labirintga kirish yoki undan
chiqish usulini ishlab chiqdi. U quyidagi qoidalardan iborat: labirintning istalgan
nuqtasini tark etgandan so‘ng, uning devoriga belgi qo‘yish va ixtiyori berk
yo‘lakka yoki chorrahaga o‘tish kerak; birinchi holda, orqaga qaytiladi, yo‘l ikki
marta - u yerda va orqada bo‘lganligini va bir marta ham bosib o‘tmagan yoki bir
marta bosib o‘tgan yo‘nalishga borishni bildiradigan ikkinchi belgi qo‘ying,;
ikkinchisida - kirish va chiqishdagi har bir chorrahani bitta belgi bilan belgilab,
ixtiyoriy yo‘nalishda borish; agar chorrahada allaqachon bitta belgi bo‘lsa, unda siz
yangi yo‘lni bosib o‘tishingiz kerak, agar bo‘lmasa, siz bosib o‘tgan yo‘lni
ikkinchi belgi bilan belgilang.
Tremo algoritmini bilib, siz afsonaviy Teseyaning xatti-harakatlarini
to‘g‘rilashingiz mumkin. Sevimli Ariadnaning sovg‘asidan ilhomlanib, u labirint
bo‘ylab ishonch bilan yuradi. To‘satdan uning oldida o‘tish joyi paydo bo‘ladi,
uning bo‘ylab ip allaqachon tortilgan.
Nima qilish kerak? Hech qanday holatda siz uni kesib o‘tmasligingiz kerak,
lekin allaqachon ma’lum bo‘lgan yo‘l bo‘ylab qaytib, boshqa bosib o‘tilmagan
harakatni topmaguningizcha, ipni ikki barobarga oshirib boring. Demak, siz ipni
yer ostida ishlatishni bilishingiz kerak.
1. 5- §. Qirralari rangli graflar va ularning xossalari
Rangli qirralari bo‘lgan graf - qirralari bir nechta ranglarda bo‘yalgan graf.
Graflar nazariyasida qirraga chekka rang berish masalalari muhim o‘rin tutadi.
Bunday graflardan foydalanish ko‘plab muammolarni ko‘rgazmali qiladi va ularni
18

hal qilishni soddalashtiradi. Bir qator amaliy muammolar rang berishni qurish
bilan bog‘liq .
Rangli qirralarga doir muammolarning o‘ziga xos xususiyati - bu yoki
boshqa sabablarga ko‘ra bir guruhga birlashtirib bo‘lmaydigan ob’ektlarning
mavjudligi. Misol tariqasida, shashka turniri ishtirokchilari orasida bir vaqtning
o‘zida bir-biri bilan o‘ynagan ishtirokchilar va hali o‘ynamagan ishtirokchilar
paydo bo‘lgan vaziyatni ko‘rib chiqishimiz mumkin.[4] Qulaylik uchun grafning
bir munosabatga mos keladiganlar qirralari bir rangga, boshqa munosabat yesa
ikkinchi rangga bo‘yalgan. Rasmda ikkita rangning beshta uchi va qirralari bo‘lgan
graf ko‘rsatilgan, ammo bu graf boshqa o‘xshash bo‘lmagan chizmalar bilan
tasvirlanishi mumkin (1.9-rasm).
1.9-rasm - Rangli qirralari bo‘lgan graf
Rangli qirralari bo‘lgan graflarning xususiyatlari:
1 . Ikki rangdagi oltti yoki undan ortiq uchlari va qirralari bo‘lgan grafdagi
har qanday uchi bir xil rangdagi kamida uchta qirraga ega.
2. Ikki rangli olti yoki undan ortiq uchlari va qirralari bo‘lgan har qanday
grafda kamida bitta rangdagi tomonlari bo‘lgan uchburchak mavjud.
2.Agar ikkita rangli beshta uchi va qirralari bo‘lgan grafda tomonlari bir xil
rangdagi uchburchak bo‘lmasa, u holda grafni qizil tomonlari va ko‘k diagonallari
bo‘lgan "beshburchak" sifatida tasvirlash mumkin.
4. Ikki rangli olti yoki undan ortiq uchlari va qirralari bo‘lgan har qanday
grafda har doim bir xil rangdagi ikkita uchburchak bo‘ladi. Ushbu ikki
uchburchakning umumiy uchi yoki hatto umumiy qirrasi bo‘lishi mumkin.
5. 17 yoki undan ortiq uchlari va qirralari 3 rangdan iborat bo‘lgan to‘liq grafda har
doim bir xil rangdagi kamida bitta uchburchak bo‘ladi.
19

II BOB. “GRAFLAR NAZARIYASI ELEMENTLARI” KURSINING
METODIK TA’MINOTI
2. 1- §. Maktabda graflar nazariyasi elementlarini o‘qitish xususiyatlari.
Graflar chekli (uning qirralari soni chekli) va cheksiz (qirralari soni cheksiz)
bo‘lishi mumkin. Boshlang‘ich maktab va 5-6-sinflarda cheksiz grafli masalalar
taklif etilmaydi, lekin kattaroq bolalar uchun bunday grafning misolini keltirish
mumkin. Misol uchun, grafning har bir uchi natural songa to‘g‘ri kelganda, ya’ni.
grafning uchlari 1, 2, 3 raqamlari raqamlangan.
Lekin natural sonlar qatori cheksiz bo‘lgani uchun graflar ham cheksizdir.
Albatta, cheksiz grafni to‘liq tasvirlash mumkin emas, lekin uni qisman tasvirlash
mumkin.

2.1-rasm
Uch darajasi - bu grafning bir uchidan chiqadigan qirralarning soni. Agar
qirra tugun bo‘lsa, u ikki marta hisoblanadi. Biz ta’rifni misollar bilan
mustahkamlaymiz .
Ba’zan uchning darajasi jadval shaklida yoziladi, ba’zan esa uchning o‘zi
yonida yoziladi. Shuni ta’kidlash kerakki, bitta qirra ikki marta (bir uch uchun bir
marta, ikkinchisi uchun) sanaladi, chunki u ikkita uchni bog‘laydi.
Uchlar juft (uch darajasi juft) va toq (uch darajasi toq) bo‘ladi.
Graflar mavzusi bo‘yicha taklif qilinishi mumkin bo‘lgan birinchi vazifalar
aynan shu tushunchalar bilan bog‘liq: graf tuzing, chizma bo‘yicha grafning
qancha uchi va qirralari borligini, grafdagi uch darajasi qanday ekanligini aniqlang,
nechta juft va toq uchlari borligini sanash va shunga o‘xshash vazifalar.
Topshiriq: Rasmdan aniqlang: grafikning nechta uchi va qirralari bor va
grafning har bir uchining darajasi qanday?
20

2.2-rasm
Yechish: Birinchidan, uchlari sonini hisoblaymiz. Aniqlik uchun dastlab ular
boshqa rangda ta’kidlanishi mumkin-8ta uch.Qirralarni hisoblash uchun
Hisoblangan qirrani ikki marta hisoblamaslik uchun chiziq bilan belgilash qulay –
9 ta qirralar 2.2-rasm).
2.3-rasm 2.4-rasm 2.5-rasm
Graf uchining darajasini aniqlash uchun barcha ularni harflar bilan belgilash
yaxshidir (2.5--rasm), so‘ngra natijalarni jadvalga yozing.
Biz bolalarga isbotsiz tanishtiradigan birinchi xossa: "Grafning toq uchlari
soni juftdir". Bundan tashqari, barcha xossalar va teoremalar qat’iy isbotsiz
berilgan. Bu xossani mustahkamlashda muammolarni hal qilishda ham sodir
bo‘ladi.[2]
Topshiriq: Uchlari quyidagi darajalarga ega bo‘lgan graf tuzing:
a) A – 7, B – 3, C – 1; b) A – 5, B – 1, C – 4.
Yechish: Graflarni tuzishga oid masalalarni yechishda o’quvchilarga birinchi
navbatda berilgan grafni tuzish hatto mumkin yoki yo‘qligini tekshirish kerakligini
tushuntirish kerak.
Buning uchun o’quvchilar birinchi xossani qo‘llashlari kerak.
O’quvchilar:
21

a) grafni qurishga qanchalik urinmasin, muvaffaqiyatga erisha olmaydi.
b) grafni qurish mumkin emas, chunki uning barcha uchlari , soni toq.
Ammo
c) grafigini qurish mumkin, chunki uning ikkita toq uchi bor. Bundan
tashqari, o’quvchilar turli xil konfiguratsiyaga ega graflarni ishlab chiqishi
mumkin (2.6-2.7-2.8-rasm). Aynan shunday vazifalarda grafning toq uchlari soni
juft ekanligi aniqlanadi.
Ushbu muammolarning o‘rgatuvchi tomoni - bu muammoni hal qilishning
o‘zi hal qilinishidan oldin uni hal qilish mumkinmi yoki yo‘qligini tekshirish.
Grafini qurish uning barcha uchlari tasviridan boshlanishi kerak va shundan
keyingina ularni qirralar bilan bog‘lang. qirralari bilan eng kichik va eng katta
darajali uchlarni ulashdan boshlash qulay.[1]
2.6--rasm 2.7--rasm 2.8-rasm
Keyinchalik, quyidagi topshiriqlar berish yaxshidir: "graf tuzmasdan,
grafning qirralari sonini aniqlang."
2-xossa: Grafdagi qirralarning sonini topish uchun uchlarning darajalarini
yig‘ib, natijani ikkiga bo‘lish kerak.
Topshiriq: Graf uchlari darajalari berilgan: A – 2, B – 5, C – 1, D – 4. Graf
tuzmasdan, graf qirralarning sonini aniqlang.
Yechish: Bolalar birinchi navbatda bunday grafni qurish mumkinmi yoki
yo‘qligini tekshirishlari kerak. Buni tekshirish uchun siz toq uchlari sonini
hisoblashingiz kerak - juft son bo‘lishi kerak. Muammoning shartlariga ko‘ra, B va
C 2 ta toq uchlari mavjud, ya’ni qurish mumkin.
E ndi masalaning savoliga ikkinchi xossadan foydalanib javob berish
mumkin: (2+5+1+4):2=6.
Muammoni hal qilgandan so‘ng, bolalardan ushbu grafni tuzishni va
yechimni tekshirishni so‘rashingiz mumkin. Bundan tashqari, chizmalar qaysi
22

uchlari ulanishiga qarab butunlay boshqacha bo‘lishi mumkin (2.9-2.10-2.11-
rasm). E ng muhimi, uchlarning darajalari muammoning shartlariga mos keladi.

2.9-rasm 2.10-rasm 2.11-rasm
Bog‘langan graf - bu shunday grafki, uning istalgan ikkita uchi qirralarning
uzluksiz ketma-ketligi bilan bog‘lanishi mumkin. Boshqacha qilib aytadigan
bo‘lsak: har qanday uchidan siz qirralar bo‘ylab boshqa uchiga o‘tishingiz mumkin
(2.11-2.12-rasm).
Ajralgan graf - bu bir nechta qismlardan iborat bo‘lgan graf, ularning har
biri bog‘langan grafik yoki alohida uchlardir (2.13-rasm).
2.11-rasm 2.12-rasm 2.13-rasm
Yuqorida taklif qilingan grafiklar bo‘yicha nazariy materiallar 5-6 sinf
o‘quvchilari uchun juda qulaydir. Quyida biz matematikadan tanlov kursi
qurishimiz mumkin bo‘lgan asosiy vazifalarni ko‘rib chiqaylik.. Bunday masalalar,
qoida tariqasida, matematika olimpiadalarida yoki yulduzlar bilan bog‘liq
masalalar bo‘limida uchraydi.
1. O‘n kishi qo‘l berib salomlashdi. Besh kishi yetti marta qo‘l siqishdi,
uchtasi beshta, ikkitasi to‘rtta qo‘l siqishdi. Qancha qo‘l siqish qilindi?
Yechim: Birinchidan, siz bolalar bilan birgalikda graflar tilida qo‘l siqish
tushunchasini to‘g‘ri tushunishlarini aniqlashingiz kerak. Bitta qo‘l siqish - bu bir
qirra bilan bog‘langan ikkita uch. Ya’ni, ikki kishi va ular o‘rtasida bitta qo‘l
siqish. Bu masalani graflar tiliga quyidagicha qayta shakllantirish mumkin: 10 ta
uch berilgan bo‘lsa, har bir uchning darajalari ma’lum bo‘ladi va bu grafda qancha
qirralar borligini aniqlash kerak. grafdagi qirralarning sonini Bilish uchun har bir
23

uchning darajalari bilan qo‘shilishi va yarmiga bo‘linishi kerak - ikkinchi xossa
qo‘llaniladi. Besh kishi yettita qo‘l siqishgandan beri bu beshta uchdan yettita qirra
chiqishini bildiradi va qirralarning umumiy soni: 5+5+5+5+5+5+5=5 ∙ 7.
Qolgan uchlari bilan ham xuddi shunday fikr yuritamiz:
(5*7+3*5+2*4):2=(35+15+8):2=29
2. Har bir jamoa to‘rtta o‘yin o‘tkazishi uchun to‘qqizta jamoadan iborat
futbol turnirini tashkil qilish mumkinmi?
Yechish: Muammoni graflar tiliga o‘tkazamiz: 9 ta uch bo‘lgan va har bir
uchning darajasi 4 ga teng bo‘lgan graf qurish mumkinmi? Ikkinchi x’ossaga
ko‘ra, qirralarning sonini topamiz, agar u butun son bo‘lsa, unda Bunday turnirni
tashkil qilish mumkin, aks holda bu mumkin emas.
(9 *4):2=18. Ha, 18 ta o‘yin o‘ynash mumkin va o‘ynaladi.
3. 15 ta telefonni har biri aniq 11 ta telefonga ulash mumkinmi?
Yechish: Masalani graflar tiliga qayta shakllantiramiz: 15 ta uchi bo‘lgan va
har bir uchining darajasi 11 ga teng bo‘lgan graf qurish mumkinmi? Ikkinchi
xossani qo‘llaymiz: ( 15*11 ) :2=82,5. Siz olgan son natural son emas, demak siz
telefonlarni ulana olmaysiz
4. Davlatda 100 ta shahar bo‘lib, har biridan 4 ta yo‘l chi q adi. Davlatda
nechta yo‘l bor?
Yechim: Bitta yo‘l ikki shaharni bog‘laydi, ya’ni. ikkita uch bir qirra bilan
bog‘langan. Ikkinchi xossani qo‘llaymiz: (100 * 4):2 =200.
5. Har bir shahardan tashqariga chiqadigan 3 ta yo‘l bo‘lgan davlatda roppa-
rosa 100 ta yo‘l bo‘lishi mumkinmi?
Yechish: Masalani tenglamani tuzib yechamiz: (x *3): 2=100, bu yerda x -
davlatdagi shaharlar soni. x*3=200, x=66, (6) natural son emas, demak, bunday
holatda aniq 100 ta yo‘l bo‘lishi mumkin emas.
Muammolar bo‘yicha yuqoridagi materialni mashq qilgandan so‘ng, siz
graflar mavzusi bo‘yicha nazariy materialni qo‘shimcha o‘rganishni boshlashingiz
mumkin. Sikl - bu grafdagi yopiq yo‘l. Graflar sikl bilan (2.14-rasm, sikl ko‘k
rangda ta’kidlangan) va siklsiz (2.15-rasm) bo‘ladi.
24

2.14-rasm 2.15-rasm 2.16-rasm
Daraxt - bu bog‘langan graf bo‘lib, unda sikllar yo‘q (2.16-rasm). Ushbu
ta’rifni kiritishdan oldin bog‘langan graf tushunchasini takrorlash kerak. Quyidagi
turdagi vazifalarni taklif qilamiz:
Topshiriq: Taklif etilgan graflar orasidan (2.17-2.20-rasm) daraxt graflari va
siklli graflarni toping.Siklga nechta uch kiritilganligini ko‘rsating.
2.17-rasm 2.18-rasm 2.19-rasm 2.20-rasmga
Yechish: Daraxt graflari 2.18-rasm va 2.19-rasmda ko‘rsatilgan; siklli
grafiklar – 2.17-rasm (sikl 3 ta uchdan iborat) va 2.20-rasm (sikl 4 ta uchdan
iborat).
Keyinchalik, biz mantiqiy muammolarni hal qilishda juda tez-tez
ishlatiladigan yana bir muhim xossanii taqdim yetamiz.
3-xossat: Agar graf bog‘liqli bo‘lsa va 0 yoki 2 ta toq uchlari bo‘lsa, u holda
har bir qirradan faqat bittasini o‘tkazish orqali uni kesib o‘tish mumkin. Boshqa
aytganda: Agar graf bog‘langan bo‘lsa va 0 yoki 2 ta toq uchga ega bo‘lsa, u holda
qalamni qog‘ozdan ko‘tarmasdan va ikki marta qirradan o‘tmasdan grafni chizish
mumkin.
Agar siz qalamni qog‘ozdan ko‘tarmasdan yoki istalgan qirradan ikki marta
o‘tmasdan graf chizishingiz mumkin bo‘lsa, unda bunday graf unikursal yoki
Eyler grafi deb ataladi.
Odatda, ushbu xossa bo‘yicha vazifalar bolalarda katta qiziqish uyg‘otadi.
Topshiriq: Taklif etilgan grafiklardan (2.21-2.27-rasm) bitta urinish bilan tasvirlash
mumkin bo‘lganlarini toping (ya’ni, qalamni qog‘ozdan ko‘tarmasdan va
25

ikki marta hech qanday qirradan o‘tmasdan) va ularni daftarga chizing.
2. 21 -rasm 2 . 2 2 -rasm 2. 23 -rasm 2. 24 -rasm
2.25-rasm 2.26-rasm 2.27-rasm
Yechish: Bu vazifani hal qilish uchun siz barcha uchlarning darajalarini
hisoblashingiz, toq uchlarini aniqlashingiz va ularning sonini hisoblashingiz kerak.
Agar 2 yoki 0 bo‘lsa, u holda graf qurish mumkin, aks holda - yo‘q. Graflarni
daftarda tasvirlashdan oldin, siz bolalarga tezroq va to‘g‘ri tasvirlash usulini
aytishingiz kerak.
Graflar haqida bilishingiz kerak: agar grafning ikkita toq uchi bo‘lsa, uning
tasviri bir toq uchi boshlanib, ikkinchisi bilan tugashi kerak. Agar grafning barcha
uchlari juft bo‘lsa, grafning boshi va oxiri bir-biriga to‘g‘ri keladi. 2.21, 2.22, 2.27-
rasmda ko‘rsatilgan graflarni siz chizishingiz mumkin emas, lekin qolganlari
mumkin.
Uy vazifasi sifatida bolalardan rus alifbosining bosma harflarini tahlil
qilishni so‘rashingiz mumkin va ular orasida bitta urinish bilan yozilishi mumkin
bo‘lganlarini yozing va nima uchun mumkin emasligini tushuntiring?
Agar siz ozgina fantaziya va tasavvurni qo‘llasangiz, unda bir urinish bilan
siz ko‘plab noodatiy chizmalarni tasvirlashingiz mumkin (2.28-2.30-rasm).
26

2.28-ras m 2.29-rasm 2.30-rasm
Eyler grafigi tushunchasini mashq qilish uchun quyidagi turdagi topshiriqni
berish foydali bo‘ladi:
Topshiriq: Graflarni E yler graflarigacha to‘ldiring (2.31-2.33-rasm) rasm.
2.31 - rasm 2.32-rasm 2.33-rasm
Yechish: Bu masalani yechish uchun avvalo har bir uchning darajasini
hisoblab, ikkita toq uch bo‘lishi yoki yo‘qligi uchun grafga qirralar qo‘shish
kerak.. 2.34-2.36-rasmlarda yechim variantlaridan biri keltirilgan.
2.34-rasm 2.35-rasm 2.36-rasm
Yuqorida taklif qilingan amaliy materialni tahlil qilib, biz graflar nazariyasi
yordamida muammolarni hal qilish uchun quyidagi bosqichlarni ajratish mumkin
degan xulosaga keldik:
1. Muammo shartlarini tahlil qilish va graflar tiliga o‘tkazish;
2. Shartning geometrik talqini, grafni qurish. Aynan shu bosqichda
ijodkorlik elementi juda muhim, chunki shart elementlari va grafning mos
keladigan elementlari o‘rtasidagi mosliklarni topish oson emas;
27

a) Nuqtalar masala ob’ektlarini (graf uchlarini) bildiradi. Agar masalalar bir
nechta ob’ektlar guruhini o‘z ichiga olgan bo‘lsa, unda ularni turli tekisliklarda va
turli ranglarda tasvirlash yaxshiroqdir;
b) Chiziqlar (kesmalar, yoylar) ob’ektlar orasidagi munosabatlarni bildiradi
(graf qirralari). Aloqalar ikki xil bo‘lishi mumkin: tegishli va tegishli emas. Agar
munosabat "tegishli" bo‘lsa, unda chiziqlar qalin bo‘ladi, "agar tegishli bo‘lmasa"
– punktir chiziqlar bo‘ladi;
3. Masalalarning asosiy iboralarini tanlaymiz va ularni tahlil qilib, qirralarni
chizamiz;
4. Masalani yechish uchun tayanch iboralar yetarli bo‘lmasa, u holda grafni
tahlil qilamiz va yetishmayotgan qirralarni chizamiz;
5. Kerakli munosabatlarni (qalin chiziqlar) tanlang va javobni yozing.
Graflardan qandaydir yordamchi vosita sifatida foydalanish o‘quv jarayonini
osonlashtirish va o‘quvchilarni maktab matematika kursidagi murakkab
mavzularni idrok etishga tayyorlashga imkon beradi.. Graf masalalar, shubhasiz,
nafaqat matematika to‘garaklarida, olimpiadalarga tayyorgarlik jarayonida
o‘quvchilarning zehnini rivojlantirish uchun, balki grafiklar nazariyasidan
matematika, algebra,geometriya, informatika fanidan ta’lim sifatini oshirishning
tili sifatida foydalanish lozim.
Shunday qilib, maktab matematika kursida graflar nazariyasidan
foydalangan holda, ko‘plab matematik masalalarni yechish va isbotlashlar
soddalashtiriladi, ularga ko‘rgazmalilik va oddiylik bag‘ishlaydi.
2.2- §. Sinfdan tashqari mashg‘ulotlarning matematika o‘qitish
shakli sifatidagi o‘rni
Tanlov kursi (fransuzcha facultative - imkoniyat) oliy o‘quv yurtlari
o‘quvchilari va o‘rta ta’lim muassasalari o‘quvchilari ilmiy-nazariy bilimlarini
chuqurlashtirish va kengaytirish maqsadida o‘z xohishiga ko‘ra o‘rganadigan
o‘quv kursi yoki fanidir .
28

Allaqachon 19-20-asrlar oxirida. o‘qituvchilar umumta’lim maktabida har
qanday fanni dastur bo‘yicha o‘qitish, agar u guruhlarda dasturdan tashqari
mashg‘ulotlar bilan shug‘allanuvchi o‘quvchilar uchun ixtiyoriy fanlar sikli bilan
to‘ldirilsa, yanada muvaffaqiyatli bo‘lishini ta’kidladilar.
Ushbu guruh mashg‘ulotlari, birinchi navbatda, "mahalliy sharoitlar" ni
hisobga olishi kerak edi, masalan: ma’lum bir o‘quvchilar guruhining haqiqiy
ehtiyojlari va manfaatlari, o‘qituvchining majburiy dasturda nazarda tutilmagan
muayyan fanning muhim jihatlariga o‘quvchilarda qiziqish uyg‘otish va
rivojlantirish real imkoniyatlar. Shunday qilib maktabda sinfdan tashqari
mashg‘ulotlarni tashkil etish g‘oyasi paydo bo‘ldi .
Fakultativ darslarning maqsadi o‘quvchilarning qobiliyatlari, qiziqishlari
umumiy ta’lim bilan uyg‘unlikda, matematikaga qiziqishning boshlang‘ich
bosqichda paydo bo‘lishi va uni kognitiv darajaga qadar rivojlantirish va shu bilan
profilni tanlash uchun asosni shakllantirish.
Fakultativ darslar tabaqalashtirilgan ta’lim shakllaridan biri hisoblanadi.
Sinfdan tashqari mashg‘ulotlarni tashkil etishdan maqsad o‘quvchilarning
dunyoqarashini kengaytirish, matematik tafakkurini rivojlantirish, fanga faol
kognitiv qiziqishni rivojlantirishdan iborat.
Matematikadan fakultativ darslar dasturi o‘rta maktab uchun asosiy
matematika kursi dasturi bilan birgalikda ushbu sinf o‘quvchilari uchun yuqori
darajadagi dasturni tashkil etadi.
O‘quvchilar o‘z xohishiga ko‘ra ixtiyoriy darslarga qatnashadilar,shuning
uchun o‘qituvchi qobiliyatli o’quvchilar o‘z imkoniyatlarini ro‘yobga chiqarishlari
uchun sharoit yaratishi kerak, qolganlari yesa o‘zlari uchun mumkin bo‘lgan yoki
qiyin vazifalarni, lekin o‘qituvchining yordami bilan hal qila oladilar.
Sinfdan tashqari mashg‘ulotlar samarali bo‘lishi uchun ularni quyidagi
joylarda tashkil etish tavsiya etiladi:
1) darslarni yuqori ilmiy va uslubiy darajada olib borishga qodir yuqori
malakali o‘qituvchilar;
29

2) kamida 10 kishidan iborat ushbu tanlov kursini o‘rganishni istagan
o‘quvchilar .
O‘quvchilar soni kam bo‘lgan umumiy ta’lim muassasalarida fakultativ
sinflar bo‘yicha o‘quvchilar guruhlari parallel ravishda yoki qo‘shni sinflar
o‘quvchilaridan (5-6-sinflar, 8-9-sinflar va va boshqalar.) qamrab
olinadi.Fakultativ darslarga o‘quvchilarni ro‘yxatga olish ixtiyoriylik asosida va
ularning qiziqishlarini inobatga olgan holda, o‘quvchilarni ixtiyoriy fanlarni
majburiy o‘qishga majburlamasdan amalga oshiriladi. Biz qiyinchiliklarga duch
kelgan o‘quvchilarga ko‘proq e’tibor qaratishimiz kerak, matematikani o‘rganish
yoki maktabni boshqa faoliyat bilan birlashtirish (sport, musiqa va boshqalar)
lozim.
Fakultativ kursni tugatgandan so‘ng, o‘quvchilar test (baho bilan)
topshiradilar, bu sertifikatda qayd yetiladi.
Tanlov kursining o‘ziga xos xususiyati shundaki, har bir sinf uchun kurs
dasturi bir qancha asosiy mavzulardan (bir-biridan mustaqil) tuzilgan bo‘lib,
ularning mazmuni umumiy matematika kursiga bevosita tutashgan. Biroq,
fakultativ darslarda o‘quvchilarning o‘quv ishlarining mazmuni nafaqat
o‘rganilayotgan mavzular va bo‘limlarning matematik mazmuni, shuningdek, turli
xil uslubiy omillar bilan belgilanadi:
- o‘qituvchining tushuntirish xarakteri;
- o‘quv mashqlari va nazariya o‘rtasidagi munosabat;
- kognitiv savollar va topshiriqlar mazmuni;
- mustaqil ish va har bir o‘quvchi tomonidan olingan natijalarni jamoaviy
muhokama qilish kombinatsiyasi.
Matematika bo‘yicha fakultativ mashg‘ulotlarni o‘tkazish sinfdan tashqari
ishlarning boshqa shakllaridan (matematika to‘garaklari, kechki mashg‘ulotlar,
olimpiadalar va boshqalar) voz kechishni anglatmaydi. Sinfdan tashqari ishlar
matematikaga qiziquvchi o‘quvchilar bilan ishlash shakllarni to‘ldirishi kerak .
Sinfdan tashqari mashg‘ulotlarga quyidagi talablar qo‘llaniladi:
30

1. Matematika darslarining mazmuni, tashkil etish usullari va shakllaridagi
uzluksizlik matematikani o`qitish, o`quvchilarni har tomonlama rivojlantirish va
tarbiyalash maqsadlari bilan belgilanishi kerak.
2.Matematikadan darslar va fakultativ darslarning o‘zaro bog‘langan
tuzilishi matematika o‘qitishda didaktik tamoyillarga zid kelmasligi kerak.
3. Ilmiy asoslangan psixologik-pedagogik talablarga qarama-qarshiliklar
bo‘lmasligi kerak, masalan: ma’lum tushunchalar asosida yangi tushunchalarni
o‘rganish; matematik abstraksiyalarni o‘rganishda aniq modellarga tayanish;
matematika tadbiqlaridan amaliy imkoniyatlaridan nafaqat ushbu masalani
o‘rganishning rivojlanish bosqichida, balki ushbu bo‘lim va masalani o‘rganish
zarurligini asoslovchi motiv sifatida foydalanish.
4. Umumta’lim maktabi ishini tashkil etish me’yorlariga hech qanday
nomuvofiqlik bo‘lmasligi kerak. Masalan, 24 ta fakultativ darsga ajratilgan
soatlardan darsdan tashqari mashg‘ulotlarga yoki matematikadan qo‘shimcha
darslarga foydalanish mumkin emas.
5. Bir-biri bilan uzviy bog`liq bo`lgan o`rganish, rivojlanish va tarbiya
jarayonlarining natijaviyligi matematika fani bo`yicha o‘zaro bog`liq holda
fakultativ mashg‘ulotlarni qurish samaradorligi mezoni bo`lishi kerak.
6. Matematika fani bo‘yicha fakultativ mashg‘ulotlarni mashg‘ulotlarni
ularning vazifalari – rivojlantiruvchi, tarbiyaviy va o‘quv vazifalarini hisobga
olgan holda o‘tkazish maqsadga muvofiqdir .
Fakultativ mashg‘ulotlarni mashg‘ulotlarni tashkil etish bo‘yicha uslubiy
tavsiyalar:
1. Tarbiyaviy ishlar va sinfdan tashqari ishlarni tashkil etish mazmuni,
shakllari va usullarining o`zaro bog`liqligi.
2. Dars va sinfdan tashqari mashg‘ulotlarning o‘zaro bog‘liqligini
(mazmunida) ta’minlash.
3 Fakultativ mashg‘ulotlarni mazmunili va turli matematika bo‘limlari
o‘rtasidagi birlik .
4. O’quvchilarning mustaqil ishlarini faollashtirish.
31

5. O‘quv jarayonini o‘quvchilarning birgalikdagi tadqiqot faoliyati sifatida
qurish.
6.Ma’ruza davomida ko‘rgazmali qurollar va referat jadvallardan
foydalanish.
7. Fakultativ darslarda mavzular bo‘yicha tayanch masalalar tizimidan
foydalanish.
8.Tarixiy-matematik materiallardan foydalanish
9. Mashg‘ulotlarning qiziqarlik tamoyillari.
10.Mashg‘ulotlarni muammoli o‘rganishni tashkil etish.
Fakultativ darslar, eng avvalo, talabalar uchun qiziqarli va hayajonli bo‘lishi
kerak. Shu munosabat bilan o‘qituvchining asosiy maqsadi
- o‘quvchilarda ular murakkab masalalar ustida ishlashga tayyor
ekanliklarini tushunishga erishish, lekin bu hali ham fanga qiziqish, mashaqqatli
mehnat, ko‘nikmalarni egallash va o‘z ishini tashkil etishni talab qiladi.
Sinfdan tashqari mashg‘ulotlar uchun ishning turli shakllari, masalan,
ma’ruzalar, seminarlar, suhbatlar (munozaralar), muammolarni hal qilish, tezislar,
o’quvchilarning hisobotlari va boshqalar. Biroq, o‘qituvchi taqdimotning biron bir
shakli yoki uslubiga ustunlik bermasligi kerak, u ko‘proq muammolarni hal qilish,
tezislar, hisobotlar va hokazolardan foydalanishi kerak;
Matematikadan fakultativ darslarni o‘tkazishning mumkin bo‘lgan
shakllaridan biri har bir darsni ikki qismga bo‘lishdir. Birinchi qism yangi
materialni o‘rganishga va talabalarning nazariy va amaliy xarakterdagi topshiriqlar
bo‘yicha mustaqil ishlariga bag‘ishlangan. Buning oxirida
Darsning bir qismida talabalarga nazariya va uning qo‘llanilishini o‘rganish
uchun uy vazifasi beriladi. Har bir darsning ikkinchi qismi o‘ta qiyin bo‘lgan
muammolarni hal qilishga va ayniqsa qiyin yoki qiziqarli muammolarni hal qilish
yo‘llarini muhokama qilishga bag‘ishlangan. Sinfdan tashqari mashg‘ulotlarning
bu shakli maktabda o‘qitishning shakl va usullaridan oliy o‘quv yurtlarida
o‘qitishning shakl va uslublariga muvaffaqiyatli o‘tishga hissa qo‘shish.
Matematika fani fani fakultativ darslarda muammoli ta’lim shakli ishlatilishi
32

mumkin. Agar o‘rganilayotgan tanlov kursi ketma-ket topshiriqlar qatori sifatida
taqdim etilsa, ularni mustaqil ravishda yoki o‘qituvchining ozgina yordami bilan
hal qilsa, o’quvchilar kursni asta-sekin katta muvaffaqiyat bilan o‘rgansa, shaxsiy
ishtirok etish, faollik va mustaqillikni ko‘rsatish, matematik fikrlash texnikasini
o‘zlashtirishni amalga oshirish mumkin. Muammoli xarakterdagi muammolarni
keng qo‘llash ham juda foydali.
Fakultativ darslarda o‘quvchilar o‘qituvchi tomonidan tavsiya etilgan turli
qo‘shimcha adabiyotlardan foydalanadigan ma’ruzalar taqdimotidan foydalanish
tavsiya etiladi. Ammo ma’ruzalar ko‘p bo‘lmasligi kerak, aks holda o‘qituvchi
ma’ruzachilarni yaxshi tayyorlash uchun yetarli vaqtga ega bo‘lmaydi.
Shunday qilib, o‘quvchilarning matematika fani bo‘yicha tanlashlari
matematikaga yoki uning qo‘llanilishiga bo‘lgan jiddiy qiziqishiga asoslanadi. Bu
qiziqish katta umumiy madaniy yoki amaliy ahamiyatga ega bo‘lgan mavzularni
ko‘rib chiqishda, xususan, graflar nazariyasi masalalarini o‘rganishda qondiriladi
va rivojlanadi.
Fakultativ darslarga qo‘yiladigan talablarga muvofiq, birinchi bobdagi
materialdan kelib chiqib, 9-sinf o‘quvchilari uchun “Graflar nazariyasi
elementlari” fakultativ kurs dasturini ishlab chiqildi. Afsuski, 5-8-sinflarda
ishlaganim uchun bu o‘quv yilida tanlov darslarini tashkil etish menda imkoniyat
bo‘lmadi
Kelgusi o‘quv yilida men tanlov kursini tashkil etishni
rejalashtirmoqdaman. Umid qilamanki, talabalar graflar nazariyasi bo‘yicha
fakultativ darslarga qiziqishadi va qiziqish bildiradilar.
Tanlov kursi maktab islohoti tomonidan qo‘yilgan ta’lim, tarbiyaviy va
rivojlantiruvchi o‘quv vazifalarini hal etishga, maktab o‘quvchilarining matematik
tafakkurini rivojlantirishga, ularning madaniy saviyasini oshirishga, mustaqillikni
shakllantirishga o’quvchilarning ijodiy aqliy faoliyati, ularni olimpiadalarga va
universitetda o‘qishga tayyorlashga xizmat qiladi.
33

2.3- §. “Graflar nazariyasi elementlar” tanlov kursining dasturi
va mazmuni.
Tanlov kursi dasturi o‘quv mazmuniga ega bo‘lib, quyidagilarni o‘z ichiga
oladi:
- Tushuntirish xati.
-Kursning maqsadi, kurs vazifalari.
- Kurs mazmuni.
-Ko`nikma va malakalarga qo`yiladigan talablar.
- O `quv-tematik rejalashtirish.
- Ko‘rsatmalar.
-Ilovalar.
Tushuntirish xati
O`qituvchi o`quvchilarning ijodiy qobiliyatlarini, matematik tafakkurini,
matematikaga qiziqishini, kasbiy yo`l-yo`riqlarini tarbiyalash va rivojlantirishga
juda jiddiy e`tibor berishi kerak.
Tanlov kursi talabalarning matematik tayyorgarligi yanada
chuqurlashtirishga hissa qo‘shuvchi ta’lim jarayonini tashkil etish shakllaridan biri
hisoblanadi.
Ushbu mavzuning dolzarbligi zamonaviy maktablar rivojlanishining asosiy
tendensiyalaridan biri o‘quvchilarning kognitiv qiziqishlarini rivojlantirish uchun
maqbul shart-sharoitlarni yaratish ekanligi bilan izohlanadi. Shunday masalalardan
biri graflar nazariyasini o‘rganishdir.
Graflar nazariyasi yaqinda matematikaning eng faol rivojlanayotgan
sohalaridan biriga aylandi, chunki u keng ko‘lamli masalalar bilan bog‘liq
savollarni hal qilishning oddiy, qulay va kuchli vositasidir. Graflar ko‘rinishida,
masalan, yo‘l xaritalari va elektron sxemalar, kimyoviy birikmalar molekulalari va
geografik xaritalar, odamlar o‘rtasidagi aloqalar va boshqalar. Bularning barchasi
34

graflar nazariyasining turli fanlarda: biologiya, kimyo, fizika, iqtisod, statistika,
dasturlash va boshqalarda keng qo‘llanilishiga olib keldi.
Fakultativ kurs dasturi umumta’lim maktablarining sinflari talabalar uchun
mo‘ljallangan
Fakultativ kurs mazmuni kundalik, hayot, matematik vaziyatlarni aks
ettiruvchi maxsus topshiriqlar orqali o‘quvchilarning aqliy faoliyat usullarini
rivojlantirishga qaratilgan.
Muntazam bo‘lmagan vazifalarni o‘rganish o‘rganishning tarkibiy qismi
bo‘lib motivatsiyani o‘z ichiga oladi, umuman matematikaga qiziqishni oshiradi,
ya’ni matematika shaxsiy ahamiyatga ega bo‘lgan o‘quvchilar doirasini
kengaytirish uchun zarur shart-sharoitlar yaratiladi.
Ushbu tanlov kursining kasbiy tayyorgarlik tizimiga kiritilishi asosiy
dasturni yaxlitligini buzmagan holda to‘ldiradi va matematik tafakkurni
rivojlantirishga xizmat qiladi.
Kursning muhim jihati - olingan bilim va ko‘nikmalardan kundalik hayotda
amaliy muammolarni hal qilishda foydalanishdir.
Tanlov kursining maqsadi: o‘quvchilarning matematik bilimi
chuqurlashtirish va kengaytirish, matematik madaniyatini rivojlantirish,
matematikani o‘rganishga qiziqish, matematik fikrlash, diqqat, kuzatish va ijodiy
qobiliyatlarini rivojlantirish
Ushbu tanlov kursi quyidagi muammolarni hal qilishga qaratilgan:
- “Graflar nazariyasi elementlari” mavzusi bo‘yicha talabalarda bilim va
ko‘nikmalar tizimini shakllantirish;
- O‘zlashtirilgan va olingan bilim va ko‘nikmalarni amaliy faoliyatda va
kundalik hayotda qo‘llash qobiliyatini rivojlantirish;
- tadqiqot faoliyatida ko‘nikma va malakalarni shakllantirish;
- tahlil qilish, sintez qilish, umumlashtirish qobiliyatini rivojlantirish;
- maqsadlarga erishishda qat’iyat va matonatni tarbiyalash;
35

- muloqot qilish, jamoada ishlash qobiliyati, o‘zaro yordam, yetakchilik va
tashkilotchilik qobiliyatlarini rivojlantirish, o‘z nuqtai nazarini himoya qilish
qobiliyati kabi shaxsiy qobiliyatlarni rivojlantirish;
-matematik tafakkurni rivojlantirish;
- matematikaning boshqa fanlar orasidagi ahamiyati haqida tushunchani
shakllantirish.
Ushbu tanlov kursini o‘rganayotganda, talabalarning bilim faoliyati,
masalan: muammoni taqdim etish, o‘xshashlik, qisman izlash va o‘qitishning
tadqiqot usuli, individual va tabaqalashtirilgan yondashuvlar faollashtirishning turli
usullari va usullaridan foydalaning.
Ta’lim jarayoni samaradorligining muhim jihati - amaliy mashg‘ulot, suhbat
darsi, umumlashtiruvchi topshiriq bo‘yicha dars, guruhlarda ishlash, himoya kabi
o‘quv faoliyatining turli shakllarini tanlash.
ijodiy ishlar.
Kursni o‘rganish natijasida o’quvchilar bilishlari kerak:
- graflar nazariyasining asosiy tushunchalari va bayonlari;
- E yler va Gamilton graflari va ularning elementlarini aniqlash;
- labirintni aniqlash va labirint masalalarini yechish qoidalari;
- qirralari rangli graflar va ularning xossalarini aniqlash.
Ushbu tanlov kursini o‘rganish natijasida quyidagi umumiy akademik va
maxsus ko‘nikmalar shakllanadi: ko‘nikmalar:
- tarbiyaviy va tashkiliy;
- tarbiyaviy va intellektual;
- ta’lim va aloqa;
- o‘quv va axborot.
“Graflar nazariyasi elementlari” tanlov kursi 12 soatga mo‘ljallangan bo‘lib,
5 ta taklif qilingan mavzuni o‘z ichiga oladi (2.1-jadval tanlov kursi materialini
o‘zlashtirish natijasi talabalar tomonidan yakuniy dars uchun ijodiy ishlarni yozish
va himoya qilishdir). Tanlov kursini tamomlagandan keyin olingan bilimlar
36

Oliy matematika fanidan olimpiada masalalarini yechishda “Graflar
nazariyasi elementlari”ni o‘rta maktabda amaliy qo‘llash mumkin.
Tanlov kursining amaliy qismi uchun barcha topshiriqlar va ma’ruzalar
mavzulari bitiruv malakaviy ishidagi 1-ilovaga kiritilgan.

2-jadval
1 - O’quv tematik reja.
Mashg‘ulotlarni o‘tkazish bo‘yicha uslubiy tavsiyalar
37Dars mavzusi Soatlar
soni Mashg‘ulot shakli Nazorat shakli
Graflar nazariyasi
paydo bo‘lish tarixi.
Graflar nazariyasi
asosiy tushunchalari 2 Ma’ruza-suhbat.Amaliy
ish Masalalar
yechish.Mustaqil
ish
Eyler va G amilton
graflari 2 Ma’ruza-suhbat.Amaliy
ish Masalalar
yechish.Mustaqil
ish
Labirintlar 2 O‘quvchilar
ma’ruzasi.Suhbat.
Amaliy ish Berilgan ga doir
topshiriqlar
Amaliy ish
Rangli graflar va
ularning xossalari 2 O‘quvchilar
ma’ruzasi.Suhbat
Amaliy ish Berilgan ga doir
topshiriqlar
Amaliy ish
Graflar va mantiqiy
masalalar 2 Masalalar yechish Ijodiy topshiriqlar
Masalalar
yechish.Mustaq i l
ish
Sinov dars 2 Dars-konferensiya Ijodiy ishlar
himoyasi

1- dars.
Birinchi darsning shakli ma’ruza-suhbat, chunki Bu kirish, kirish darsi.
Birinchi dars ikki soatga mo‘ljallangan. Uni o‘tkazish uchun sizga kompyuter va
proyektor kerak bo‘ladi, chunki o‘qituvchiga ushbu tanlov kursiga qiziqishni
oshirish uchun taqdimot tayyorlash tavsiya etiladi. Bu yerda biz faol va interaktiv
o‘qitish usullaridan foydalanamiz: o‘quvchilar bilan suhbat (o‘qituvchi talabalarga
savollar beradi, ular esa o‘qituvchiga berishadi), ijodiy vazifalar, mikroguruhlarda
ishlash.
Birinchi dars boshida o‘quvchilarga fakultativ dars qanday o‘tkazilishi,
ularda qanday maqsadlar borligi, yakuniy dars qanday o‘tkazilishi haqida
ma’lumotlar berilishi kerak. Keyinchalik o‘qituvchi grafiklar tarixi, grafik
nazariyasi qanday paydo bo‘lganligi, bu nazariya faoliyatning qaysi sohalarida
qo‘llanilishi va undan nima uchun foydalanish mumkinligi haqidagi materialni
aytib beradi talabalarning o‘zlari uchun foydali bo‘ladi. Bu ushbu tanlov kursiga va
kelajakda grafiklar nazariyasini o‘rganishga qiziqish uyg‘otishga yordam beradi.
Keyin o‘qituvchi talabalar bilan birgalikda quyidagi masalani yechishda graflar
nazariyasining asosiy tushunchalarini shakllantiradi: Stol tennisi bo‘yicha sinf
birinchiligida 6 nafar ishtirokchi qatnashadi: Anvar, Botir, Sardor, Gulmira,
Davlat.va Yulduz. Chempionat dumaloq tizimda o‘tkaziladi - har bir ishtirokchi
qolganlari bilan bir martadan o‘ynaydi. Bugungi kunga qadar ba’zi o‘yinlar
allaqachon o‘ynalgan: Anvar Botir, Gulmira va Yulduz bilan o‘ynagan; Botir,
yuqorida aytib o‘tilganidek, Anvar va Gulmira bilan; Sardor - Gulmira, va Davlat
bilan ; Gulmira - Anvar va Botir bilan; Davlat - Sardor bilan; Yulduz Anvar va
Sardor bilan. Hozirgacha nechta o‘yin o‘tkazildi va qanchasi qoldi?
Keyin o‘qituvchi talabalarga egallagan bilimlar birlashtirish uchun
vazifalarni taklif qiladi
Mustaqil hal qilish uchun 1, 2-sonli masalalar berilishi mumkin. Hamma
yechgandan so‘ng, siz 2-3 o‘quvchini doskaga chaqirish mumkin (har bir masala
bo‘yicha), natijada ular olingan graflarni chizishadi. Yigitlar graflarning tasvirlari
hamma uchun har xil yekanligini va bu xato yemasligini ko‘radi. № 3,4 masalalar
38

O‘qituvchi uni mustaqil hal qilishni ham taklif qilishi mumkin, lekin yechimni
doskada tekshirmasdan. 5 va 6-sonli masalalarni o‘quvchilarni doskaga chaqirib
yechamiz. 7 va 8-sonli masalalarni yechish uchun o‘quvchilarni 3-4 o‘quvchidan
iborat mikroguruhlarga bo‘lish mumkin, masalani tezroq yechgan guruh “5” ball
oladi.
Uy vazifasini bajarish uchun siz o‘quvchilarni kartalarda bir-birlari uchun
bitta muammoni taklif qilishingiz mumkin (bir tomonda muammoning sharti,
ikkinchi tomonda yechim bo‘ladi) va keyingi darsning boshida ular kartalarni
almashtiradilar va ularni hal qiling.
Shunday qilib, bu dars juda jonli bo‘ladi, har bir talaba suhbatda qatnashish
va yangi tushunchani aniqlash imkoniyatiga ega bo‘ladi. Matematikadan zaif
o‘quvchilar unga qiziqish bildiradilar.
2-dars.
Ushbu darsning boshida o‘quvchilar uyda yasagan kartalar bo‘yicha
masalalarni yechib, ularni almashtiradilar. Bunga 20-25 daqiqa vaqt ajratishingiz
mumkin. Keyin o‘qituvchi yechim kartalarini yig‘adi.
Ushbu darsning shakli birlashtirilgan. Biz darsda ijodiy vazifalar, o‘qituvchi
bilan suhbat, yechimlarni izlash faol va interfaol o‘qitish usullaridan ham
foydalanamiz:
Aniqlik uchun o‘qituvchiga taqdimot tayyorlash tavsiya etiladi. Dars boshida
o‘qituvchi Kyonigsberg ko‘priklari haqida muammo tuzadi:
“Kyonigsberg ikkita orolda va Pregel daryosi qirg‘og‘ida joylashgan.
Shaharning bir qismi rasmda ko‘rsatilganidek, yettita ko‘prik bilan bog‘langan
(2.1-rasm). Yakshanba kunlari fuqarolar shahar bo‘ylab sayr qilishadi. Ulardan
birortasi uydan chiqib, har bir ko‘prikdan faqat bir marta o‘tib, uyiga qaytishi
mumkinmi?” deb o‘quvchilarni uni yechishga taklif qiladi. Rasmda L harfi chap
qirg‘oqni, P o‘ng qirg‘oqni, A va B orollarni bildiradi (2.2-rasm).
Bolalar har bir ko‘prikdan 1 marta o‘tishga harakat qilishlari va
muammoning yechimi yo‘qligiga ishonch hosil qilishlari kerak.
39

2.1-rasm - Kyonigsberg ko‘priklari muammosi uchun chizma
2.2-rasm – Kyonigsberg ko‘priklari muammosi uchun graf
O’quvchilar o‘z yechimlarini taklif qiladilar, doskaga chiqadilar va bu
muammoning yechimi yo‘q degan xulosaga kelishadi. Keyin o’quvchilarni
yechimlari bo‘lgan shunga o‘xshash muammolarni yaratishga taklif qiling. Keyin
o‘qituvchi Eyler yo‘li, Eyler sikli, Eyler grafining ta’rifini beradi. Keyin Eyler graf
teoremasini tuzadi va isbotlaydi.
Keyin o‘qituvchi talabalarni Irland matematigi Gamilton nomi bilan
tanishtiradi va o‘zining dodekaedrdagi "dunyo bo‘ylab sayohat qilish"
muammosini o‘rganishi bilan Gamilton yo‘li, Gamilton sikli, Gamilton grafi
tushunchalarini kiritadi. O ’quvchilarni. Gamilton sikllarining mavjudligi yetarli
shart-sharoitlar va Dirak teoremasi bilan tanishtiradi
Shundan so‘ng o‘qituvchi talabalarga mustaqil yechish uchun vazifalarni
taklif qiladi
Masalalarni yechgandan so‘ng, graflarning xossalari bo‘yicha frontal so‘rov
o‘tkazish tavsiya etiladi.
3-dars
Bu dars ikki soat davom etadi. Dars davomida o`qitishning interfaol
usullaridan foydalanish tavsiya etiladi: o`quvchi o`qituvchi rolida, suhbat, qidiruv
vazifalari, tanlovlar, ijodiy topshiriqlar.
Darsdan bir hafta oldin uchta talabaga topshiriq berish kerak
Sinfda o‘qituvchi o‘rniga nutq so‘zlash uchun ular taqdimot qilishlari va
ushbu mavzuni tahlil qilishlari kerak. Dars suhbat shaklida o‘tkazilishi kerak.
40

Birinchi o`quvchi labirintlarga oid masalalarning paydo bo`lish tarixi va ularning
geometriyasi haqida gapiradi
Yana ikkita talaba labirintdan o‘tish v a ikkita qoidani aytib beradi .
Tinglovchilar savollar berishadi. Nazariy qismdan so‘ng o‘qituvchi
masalalar yechishni taklif qiladi.
Bu vazifalar qidiruv xarakteriga ega.Labirintni kim tezroq bajarishi
mumkinligini bilish uchun raqobat tashkil etish mumkin.
O’quvchilar labirintlarni tugatgandan so‘ng, qaysi qoidalardan
foydalanganlari va qaysi biri ko‘proq yoqqanligi haqida o‘z fikrlarini bildirishlari
kerak. Har kimga o‘z labirintini yaratish uchun uyda ijodiy grafik topshiriq bering.
Keyingi darsda bolalar labirintlarni almashtiradilar va ular orqali o‘tadilar.
4- dars
Dars boshida talabalar uyda ixtiro qilingan labirintlar va ular orqali o‘tishga
harakat qiling kartalarni almashadilar.
Uyda ixtiro qilingan labirintlar va ular orqali o‘tishga harakat qiling. Bunga
5-10 daqiqa vaqt ajratishingiz mumkin. Keyin o‘qituvchi yechim kartalarini
yig‘adi.
Darsdan bir hafta oldin 5 nafar talabadan iborat guruhni tanlab, ularga
taqdimot tayyorlash vazifasini topshiring va dissertatsiyaning birinchi bobida
tasvirlangan qirralari rangli grafiklarning xossalariga doir masalalarni ko‘rib
chiqing. Dars ma’ruza-suhbat shaklida o‘tkaziladi. Har bir talaba 1 ta masala
yechadi. U tinglovchilarga berish uchun savollar tayyorlaydi.
Nazariy qism o‘rganilgandan so‘ng, sinfni 4 guruhga bo‘ling. Har bir
guruhda o‘qituvchi vazifasini bajaradigan o’quvchi bo‘ladi. Hammaga bir xil
masalalarni mustaqil yechish uchun bering va barcha masalalarni tezroq yechgan
guruh “5”, ikkinchi guruh “4” ball oladi.
Dars oxirida siz frontal so‘rovni tashkil qilishingiz mumkin, shu bilan
olingan bilimlarni mustahkamlaysiz.
5-dars
41

Ushbu dars mantiqiy muammolarni hal qilish bo‘yicha amaliy
mashg‘ulotdir. Ikki soat uchun taxmin qilingan. Biz interfaol o‘qitish usullaridan
foydalanamiz Birinchi va ikkinchi muammolarni hal qilish uchun siz o‘quvchini
doskaga chaqirishingiz mumkin. Muammoni butun sinf sifatida ko‘rib chiqing. Siz
bolalarni ikkinchi muammoning yechimini amalda tekshirishga taklif qilishingiz
mumkin. Doskaga avval 2, keyin 3, 4 va 5 o‘quvchini chaqiring va qo‘l berib
ko‘rishishni so‘rang. Butun sinf o‘yin elementlaridan foydalangan holda jami 10 ta
qo‘l siqish borligiga ishonch hosil qilishlari mumkin.
Keyin siz o‘quvchilardan muammolarni hal qilishni so‘rashingiz mumkin.
Birinchi ikkita vazifa o‘z qo‘lingizda. Muammoni to‘g‘ri hal qilgan birinchi besh
o‘quvchi baho oladi. Birinchi ikkitasi doskadagi 1 va 2-masalalarning yechimini
ko‘rsatadi. 5, 6 va 7 masalalarni yechish uchun sinfni 3 ta guruhga qatorga
ajratamiz. Kimning qatori tezroq hal qilsa, baho oladi.
Qayerda o‘qituvchi guruhdagi zaif o‘quvchidan muammoning yechimini
so‘rashi kerak. O’quvchilar 8 va 9-masalalarni mustaqil yechishlari kerak. Ehtimol,
ba’zi bolalar ilgari o‘tilgan muammolarni hal qilishning boshqa usullariga
qiziqishadi va bu matematikaga qiziqishni oshiradi.
6-dars
Ushbu dars yakuniy va konferensiya darsidir. Talabalar o‘qituvchidan
hisobot mavzularini oldindan olishlari va taqdimot tayyorlashlari kerak. Hisobotlar
qidiruv va tadqiqot topshiriqlari sifatida taqdim etiladi. Har bir ishning himoyasi 7-
10 daqiqaga mo‘ljallangan. Hisobotlar mavzulari quyidagicha tanlanadi:
matematikaning fanlar orasidagi ahamiyatini ko‘rsatish, grafiklar nazariyasi qaysi
sohalarda qo‘llanilishini ko‘rsatish. Ehtimol, bu dars ba’zi bolalarni keyingi
ta’limda matematik profilni tanlashga undaydi.
1- dars uchun topshiriqlar
1.n ta uchli to‘liq graf chizing, agar: n=2, n=3, n=5.
Yechish: (1-rasm).
42

1-rasm - 1-sonli masala yechimi
2. n ta uchli, n=3, n=5, n=k bo‘lgan to‘liq grafda uch nechta qirraga
tegishli?
Javob: ikkita qirraga.
3. Yetti qirrali to‘liq graf bormi?
Javob: ha, bor.
4. Agar n =3, n=4, n=5 bo‘lsa, n ta uchli to‘liq grafning nechta qirralari bor?
Javob: 3 qirra, 4 qirra, 5 qirra.
5. Barchasi turli darajalarga ega, ya’ni. teng 0, 1, 2,3,4 beshta uchga ega
bo‘lgan graf bormi,?
Javob: ha, bor.
6. Ikkitasi bir xil darajaga ega bo‘lgan 5 ta uchli graf chizing.
Yechish: (2-rasm).
2-rasm - 6-sonli masala yechimi
7. Malenkiy shahrida 15 ta telefon bor.Ularni simlar bilan ulash mumkinmi.
har bir telefon boshqa beshta telefonga ulash yerak bo‘lsa?
Yechim: Faraz qilaylik, telefonlar o‘rtasida bunday aloqa bo‘lishi mumkin.
Keyin uchlari telefonlarni, qirralari esa ularni bog‘laydigan simlarni ifodalovchi
grafni tasavvur qiling.
Jami nechta sim borligini hisoblaylik. Har bir telefonda aniq 5 ta sim
ulangan, ya’ni.grafikimizning har bir uchining darajasi 5 ga teng. Simlar sonini
topish uchun,
grafning barcha uchlarining darajalarini jamlashingiz va natijani 2 ga
bo‘lishingiz kerak (chunki har bir simning ikkita uchi bor, keyin darajalarni
43

yig‘ishda har bir sim 2 marta olinadi). Ammo u holda simlar soni 37,5 ga teng
bo‘ladi. Lekin bu son butun son emas. Bu shuni anglatadiki, har bir telefon boshqa
beshta telefonga ulanishi mumkin degan taxminimiz noto‘g‘ri bo‘lib chiqdi.
Javob. Telefonlarni bu tarzda ulash mumkin emas.
8. Rasmda ko‘rsatilgan grafni qalamni qog‘ozdan ko‘tarmasdan va har bir
qirrani aniq bir marta chizmib chizish mumkinmi (3-rasm).
3-rasm - 8-sonli masala uchun chizma
Yechim. Agar biz grafni shartda ko‘rsatilgandek chizsak, boshlang‘ich va
oxirgilardan tashqari har bir uchgaga, undan chiqqanimiz bilan bir xil sonda
kiramiz.Ya’ni, grafning ikkitadan tashqari barcha uchlari juft bo‘lishi kerak.
Grafimizda uchta toq uchi bor, shuning uchun uni shartda ko‘rsatilgan tarzda
chizish mumkin emas.
2- darsning masalalari
9. Uchlari (1,2,3,4,5) va qirralari (1,2), (2,3), (3,4), (3,1), (4,5) bo‘lgan graf
chizing. Bu Eyler grafimi? Yechish: (4-rasm).
Javob: ha, shunday.

4-rasm - 9-sonli masala yechimi
10. Uchlari (A, B, C, D) va qirralari (A, D), (A, B), (B, C) bo‘lgan graf
chizing.
bu Eyler grafimi?
Yechish: (5-rasm).
44

10 Javob: ha, shunday.
5-rasm - 10-sonli masala yechimi
11.Qalamni qog‘ozdan ko‘tarmasdan va bir xil qirra bo‘ylab ikki marta
chizmasdan quyidagi shakllarnichizishga harakat qiling (6-rasm).
6-rasm- 11 masala chizmasi
12. Qog‘ozdan qalam ko‘tarmasdan rus alifbosining qanday harflarini
chizish mumkin?
Javob: B, V, G, Z, I, L, M, O, P, R, S, F, b, b, I.
13. Pashsha shakar idishiga chiqdi. Idish kub shakliga ega. Pashsha bir
qirradan ikki marta o‘tmasdan kubning barcha 12 qirrasini ketma-ket aylana
oladimi?
Bir joydan ikkinchi joyga sakrash va uchish mumkin emas.
Yechish: Kubning qirralari va uchlari grafni tashkil qiladi, uning barcha 8 ta
uchlari 3 ga karrali ega va shuning uchun kerakli o‘tish mumkin emas.
14. Bola qog‘ozga uchta ko‘k va uchta qizil konturni chizdi, ular hech
qanday joyda kesishmaydi. Keyin chizilgan konturlardan biri butunlay qoplangan,
qolganlari esa qisman ko‘rinib turadigan bo‘lishi uchun qog‘oz varag‘i bilan
qoplanganyu. Rasmning yopiq qismini chizing (7-rasm).
Yechish: (8-rasm).
45

7-rasm - 14-sonli topshiriq uchun chizma
8-rasm - 14-sonli masala yechimi
15. To‘rt orol va o‘n to‘rt ko‘prik muammosi. To‘rt orol rasmda
ko‘rsatilganidek, bir-biri bilan va daryo qirg‘oqlari bilan bog‘langan. Bu
ko‘priklarning barchasini ularning har biriga bir marta tashrif buyurib piyoda
aylanib o‘tish mumkinmi? (9-rasm).
9-rasm- 15 masala chizmasi
Yechim: B va C ikkita toq uch bor. Shuning uchun bir yurishda barcha
ko‘priklarni aylanib, ularning har biriga bir marta tashrif buyurish mumkin. Shu
bilan birga, yurish B orolidan boshlanadi va C orolida tugaydi yoki aksincha (10-
rasm).
10-rasm –15 masala yechimi
3- darsning masalalari
46

16. Ushbu labirintga mos keladigan grafni chizing (11-rasm).
11-rasm — 16-sonli masala chizmasi
Yechish: (12-rasm).
12-rasm - 16-sonli masala yechimi
17. Rasmda ko‘rsatilgan labirintga kirganingizdan so‘ng, o‘ng qo‘lingiz
bilan devorga tegib, markazga yetib, orqaga qaytishingiz mumkinligiga ishonch
hosil qiling (11-rasm).
18. Labirintning istalgan nuqtasidan bir qo‘l qoidasi foydalanib, uning
markaziga borishingiz mumkinligiga ishonch hosil qiling (11-rasm).
19. 4 dan 4 metrgacha bo‘lgan kvadrat gulzorda 16 dahlia butalari o‘stirildi,
butalar orasidagi masofa bir metr edi. Butalar gullaguncha bog‘bon eng qisqa yo‘l
bo‘ylab, gullaganda esa eng uzun yo‘l bo‘ylab aylanib yurdi.Eng qisqa va eng uzun
yo‘l qanday ko‘rinishga ega edi (13-rasm)?
13-rasm- 19 topshiriq uchun chizma
Yechish: Eng qisqa yo‘l: 1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 16, 15, 14, 13.
Eng uzun yo‘l: 5, 9, 13, 10, 7, 4, 3, 2, 1, 6, 11, 16, 12, 8, 15, 14.
20. Yuqori o‘ng burchakda joylashgan kirishdan pastki o‘ng burchakda
joylashgan chiqishga labirint orqali o‘ting
47

14-rasm
15-rasm
21. Labirintni yuqoridan pastga qarab o‘ting, hech qachon o‘z yo‘lingizni
kesib o‘tmasdan, yigirmatagacha bo‘lgan raqamlarni yig‘ishda (16-rasm).
Yechish: (16-rasm).
16-rasm - 21-sonli topshiriq uchun chizma
16-rasm – 21-sonli masala yechimi
4-sonli darsning maqsadlari
2 2. Bir turda o‘tkazilayotgan shaxmat turnirida olti nafar maktab
o‘quvchisi ishtirok etmoqda. Ular orasida har doim uchta turnir ishtirokchisi
48

bo‘lishini isbotlang. Ular barcha o‘yinlarda allaqachon bir-biri bilan bo‘lib
uchrashgan yoki ular hali bir-birlari bilan bitta o‘yin o‘tkazmagan.
Yechim. Turnirning har qanday ikki ishtirokchisi, albatta, bir-biri bilan
ikkita munosabatlardan birida bo‘ladi: ular allaqachon bir-biri bilan o‘ynagan yoki
hali o‘ynamagan.
Biz har bir ishtirokchiga grafning uchini tayinlaymiz. Uchlarini ikkita
rangning qirralari bilan juft-juft qilib bog‘laymiz. Qizil qirra ikkalasi allaqachon
bir-biri bilan o‘ynaganligini, ko‘k qirra esa ular o‘ynamaganligini bildirsin. Biz
6 uchli va qirraga ega ikkita rangli grafni olamiz. Endi, masalani hal qilish
uchun, bunday grafda, albatta, bir xil rangdagi tomonlari bo‘lgan "uchburchak"
bo‘lishini isbotlash kifoya.
E’tibor bering, bizning grafmizning ixtiyoriy uchidan bir xil rangdagi
kamida uchta qirra, albatta, qolgan beshtasiga o‘tadi (buni isbotlang). Masalan, A
uchidan uchta qizil qirra chiqsin (17-rasm). Qanday rangdagi qirralarg B, C va D
uchlarini birlashtira oladi Agar ulardan kamida bittasi 18-rasmdagi kabi qizil bo‘lib
chiqsa, z qizil tomonlari bo‘lgan uchburchakni olasiz. Agar bularning barchasi
qirralari ko‘k bo‘lsa, 19-rasmda bo‘lgani kabi, u holda ular ko‘k tomonlari bilan
uchburchak hosil qiladi. Muammo butunlay hal qilindi. Bundan tashqari, uni hal
qilish birinchi ikkita xossa isbotlandi.
17-rasm 18-rasm 19-rasm
2 3. Geografik xaritada beshta shahar tanlangan. Ma’lumki, ularning
uchtasidan ikkitasi aviakompaniyalar tomonidan bog‘langan va ikkitasi
ulanmagan. U holda buni isbotlang:
1. Har bir shahar aviakompaniyalar tomonidan ikkita va faqat ikkita boshqa
shaharlar bilan bog‘langan.
2. Istalgan shahardan chiqib, beshta boshqa shahar bo‘ylab uchib, har biriga
bir martadan tashrif buyurib, orqaga qaytishingiz mumkin.
49

Yechim. Har ikki shahar ikkita munosabatlardan birida joylashgan - ular yo
aviakompaniyalar bilan bog‘langan yoki bog‘lanmagan. Grafikning uchlari
shaharlarga, qizil chekka aviakompaniya mavjudligiga va ko‘k chekka uning
yo‘qligiga mos kelsin.
Shartga ko‘ra, har qanday uchta uchni bog‘laydigan uchta qirralarning biri
qizil, ikkinchisi ko‘k rangga ega va bu grafda bitta rangli tomonlar bitta
uchburchak yo‘qligini anglatadi.
Beshta kuch va ikki rangning qirralari bo‘lgan grafda har bir uch ikkita qizil
va ikkita ko‘k qirralarga tegishli ekanligini ko‘rsatish kerak,qizil qirralar har bir
uchdan faqat bir marta o‘tadigan yopiq chiziqni hosil qiladi, yoki aks holda,
bunday grafda barcha tomonlari qizil va barcha diagonallari ko‘k bo‘lgan
"beshburchak" mavjud.
Grafning har bir uchidan ikkita qizil va ikkita ko‘k qirralar borligi aniq,
chunki aks holda tomonlari bir xil rangdagi uchburchak hosil bo‘ladi.
Shuning uchun har bir shahar aviakompaniyalar tomonidan ikkita va faqat
ikkita shahar bilan bog‘langan.
Endi chuchlardan birini tanlaymiz, masalan, A, va aytaylik, AB va AC
qirralari qizil bo‘ladi (20-rasm). CB qizil bo‘lishi mumkin emas, shuning uchun
CD yoki CE qirralarning biri qizil bo‘ladi; Qizil CD bo‘lsin. Agar biz endi qizil
rangda ulansak
B va D uchlarining qirrasi, keyin E tepasi allaqachon ikkita qizil qirralarga
tegishli bo‘lgan uchlari bilan qizil qirralar bilan bog‘langan bo‘lishi kerak. Shartga
ko‘ra, bu mumkin emas. D va E, B va E uchlarini qizil qirralar bilan ulash qoladi.
Qolgan qirralar ko‘k bo‘lishi kerak (20-rasm).
20-rasm – 23-masala uchun chizma
Masalani yechish bilan birgalikda grafning 3-xossasi olindi.
50

2 4.Bir kun davomida har oltita telefon abonentidan ikkitasi bir-biri bilan
telefonda gaplashishi yoki gaplashmasligi mumkin. Siz har doim ikkita uchlik
abonentlarni topishingiz mumkinligini isbotlang, ularning har birida hamma bir-
biri bilan gaplashgan yoki hamma gapirmagan.
Yechim. Oltita A, B, C, D, E, F uchlari bo‘lgan grafikning qizil qirralari
telefonda bir-biri bilan gaplashgan abonentlar juftligiga, ko‘k qirralar esa
gapirmaganlarga mos kelsin. Keyin tomonlar, bir xil rangdagi kamida bitta
uchburchak mavjud,masalan, qizil tomonlari bo‘lgan ABF uchburchagi. Keling,
uning bir uchini, deylik, A ni undan chiqadigan qirralari bilan vaqtincha ko‘rib
chiqaylik.
Beshta uchli qolgan grafda tomonlari bir xil rangdagi uchburchak bormi?
Agar topilsa, u asl grafikda ham mavjud. Aks holda biz qizil tomonlari va ko‘k
diagonallari bo‘lgan beshburchakni olamiz (6-rasm). Endi oltinchi A uchini
qirralari bilan tiklaymiz. AF va AB qirralari qizil rangda. Agar qirra AE yoki AC
ham qizil bo‘lsa, AEF yoki ABC qizil tomonlari bilan kamida yana bitta
uchburchak hosil bo‘ladi. Agar bu qirralarning ikkalasi ham ko‘k bo‘lsa, u holda
ko‘k tomonlari bo‘lgan uchburchak ACE paydo bo‘ladi.
Qirralari rangli bo‘lgan grafning 4-xususiyati o‘rnatildi.
25. Shaharda n ta aholi bor. Ularning har ikkisi do‘st yoki dushmandir. Har
kuni ulardan birortasi yangi hayot boshlay oladi: barcha do‘stlari bilan
janjallashish va barcha dushmanlar bilan do‘stlashish.. Ma’lumki, har qanday uchta
rezident do‘st bo‘lishi mumkin.
Barcha rezidentlar do‘stlashishlari mumkinligini isbotlang.
yechim. Biz har bir rezidentga grafning uchiini belgilaymiz. Ko‘k ыirra ikki
do‘st yekanligini, qizil rang yesa do‘st yemasligini bildirsin. Biz n ta uchli va
ыirrali ikki rangli grafni olamiz, ular quyidagi o‘zgarishlarga duchor bo‘lishi
mumkin:
uchni tanlang va u tegishli bo‘lgan barcha qizil qirralarni ko‘k rangga,
barcha ko‘k qirralarni qizil rangga o‘zgartiring. Shartga ko‘ra, har bir uchburchak
ko‘k rangga aylanishi mumkin
51

Grafda faqat ko‘k tomonlari bo‘lgan uchburchaklar yoki bir tomoni ko‘k va
ikki tomoni qizil bo‘lgan uchburchaklar bo‘lishi mumkin. Har qanday bunday
grafda shunday uch borki qizil darajasi uning ko‘k darajasidan kattaroqdir. Agar
siz har safar grafda yeng katta qizil darajaga yega uchni tanlasangiz va uning
tegishli bo‘lsa qirralarini qayta bo‘yasangiz, har bir qadamda ko‘k qirralarning soni
ortadi. n ta uchli grafning qirralari soni chekli, shuning uchun chekli qadamlardan
so‘ng grafning barcha qirralari ko‘k rangga aylanadi.
5- darsning masalalari
26 . Uch do‘st uchrashdi: Belova, Krasnova va Chernova. Ulardan biri qora
ko‘ylakda, ikkinchisi qizil ko‘ylakda, uchinchisi oq ko‘ylakda yedi. Qizil libosdagi
qiz Chernovaga aytadi
"Biz ko‘ylaklarni almashtirishimiz kerak, aks holda liboslarimizning rangi
familiyalarimizga mos kelmaydi." Qaysi qiz qaysi libosda yedi?
Yechim. Bu yerda biz ikkita teng to‘plamga yegamiz: familiyalar to‘plami
va liboslar ranglari to‘plami. Ushbu to‘plamlar o‘rtasida o‘zaro bir qiymatli moslik
o‘rnatilishi kerak. Buning uchun graf tuzamiz. B, K va Ch oq doiralar birinchi
to‘plamning yelementlarini (Belov, Krasnov va Chernov), qora doiralar b, k va ch
ikkinchi to‘plamning yelementlarini – oq, qizil va qora ranglarni ifodalasin.agar
ular o‘rtasidamoslik bo‘lmasa, bu doiralarni ingichka chiziq bilan bog‘lang. Agar
doiralar orasidagi moslik to‘g‘ri o‘rnatilgan bo‘lsa, biz ularni qalinchiziq bilan
bog‘laymiz. Shuning uchun Belova qora ko‘ylakda, Chernova qizil ko‘ylakda va
Krasnova oq ko‘ylakda.
27. Shahardan o‘rmonga borish uchun stansiyada bir necha bola
uchrashishdi. Ular uchrashganlarida hamma bir-birlari bilan qo‘l berib
ko‘rishishdi. Agar jami 10 ta qo‘l siqish bo‘lsa, nechta o‘g‘il shahar tashqarisiga
chiqdi?
Yechim. Biz bu muammoni graf tarzda hal qilamiz. Birinchidan, A va B
nuqtalarini belgilang va ularni kesma bilan bog‘lang. Biz o‘g‘il bolalarni nuqta
bilan ifodalaymiz va kesma qo‘l siqish degani bo‘ladi. yana bir C nuqtani
52

qo‘shamiz va uni A va B nuqtalari bilan bog‘laymiz. Biz jami uchta kesmani
olamiz (2 4 -rasm).
24-rasm – 27-sonli topshiriq uchun chizma
Keyingi D nuqtasini belgilaymiz va uni A, B va C uchta nuqtaga
kesmalarbilan bog‘laymiz. Yendi bizda oltita kesma bo‘ladi. Nihoyat, beshinchi
Ye nuqtasini belgilang va uni avval belgilangan barcha nuqtalar bilan ulang.. Bu
10 ta kema, ya’ni 10 ta qo‘l siqish bo‘lib chiqdi.
Demak, 5 nafar o‘g‘il vokzalda uchrashgan.
28. Quyosh tizimining 9 ta sayyorasi o‘rtasida kosmik aloqa o‘rnatildi.
Raketalar quyidagi yo‘nalishlarda uchadi: Yer-Merkuriy, Pluton-Venera, Yer-
Pluton,Pluton-Merkuriy, Merkuriy-Venera, Uran-Neptun, Neptun-Saturn, Saturn-
Yupiter, Yupiter-Mars va Mars-Uran. Yerdan Marsga borish mumkinmi?
Yechim. Uchlarisayyoralar, qirralari yesa marshrutlar bo‘lgan graf chizamiz
(25-rasm).
25-rasm - 28-sonli masala uchun chizma
Yendi Yerdan Marsga uchib bo‘lmasligi aniq.
29. Petya, Gena, Dima va Vova bolalar sport maktabida turli bo‘limlarda
shug‘ullanadilar: gimnastika, basketbol, voleybol va yengil atletika. Petya, Dima
va Voleybolchi bir shu sinfda o‘qishadi . Petya va Gena mashq qilish uchun birga
yurishadi, gimnastikachi yesa avtobusda. Yengil atletikachii basketbolchini ham,
voleybolchini ham tanimaydi. Qaysi yigitlar qaysi bo‘limda shug‘ullanadi?
53

Yechim: Petya basketbolchi, Gena voleybolchi, Dima gimnastikachi, Vova
yesa Yengil atletikachii (26-rasm).
26-rasm – 29-sonli masala uchun chizma
30. Marina, Larisa, Janna va Katya turli xil asboblarni (piano, violonchel,
gitara, skripka) chalishlari mumkin, lekin har birida bittadan. Ular chet tillarini
(ingliz, fransuz, nemis, ispan) bilishadi, lekin har biri faqat bitta (27-rasm).
Ma’lum:
1) gitara chalayotgan qiz ispan tilida gapiradi;
2) Larisa skripka yoki violonchel chalaolmaydi va ingliz tilini bilmaydi;
3) Marina skripka yoki violonchel chalaolmaydi va na nemis, na ingliz tilini
biladi;
4) nemis tilini biladigan qiz violonçel chalaolmaydi;
5) Janna fransuz tilini biladi, lekin skripka chalaolmaydi. Kim qaysi asbobda
chaladi va qaysi chet tilini biladi?
27-rasm – 35-sonli topshiriq uchun chizma
Yechim. Janna fransuz tilini bilishining beshinchi shartidan biz strelkani
chizamiz.
Uchinchi shartdan, Marina na nemis tilini biladi, naIngliz tilini, Janna esa
frantsuz tilini biladi, keyin Marina ispan tilini biladi va birinchi shartni hisobga
olgan holda gitara o'ynaydi.
54

N2 shartdan biz Larisa pianino chalayotganini ko'ramiz, chunki Marina
gitara chaladi, lekin u boshqa asboblarni qanday chalishni bilmaydi, demak u
nemis tilida gapiradi (28-rasm).
28-rasm – 35-sonli masala yechimi
Janna skripka chalaolmaydi, shuning uchun u o‘ynashi mumkin bo‘lgan
faqat bitta asbob qoldi - violonchel. U holda Katya skripka chaladi va ingliz tilini
biladi (28-rasm).
3 1 . Uch do‘st: Alyosha, Borya va Vitya - bir sinfda o‘qiydilar. Ulardan biri
maktabdan uyga avtobusda, biri tramvayda, biri trolleybusda boradi. Bir kuni
darsdan keyin Alyosha do‘stini avtobus bekatiga kuzatib bordi. Ularning yonidan
trolleybus o‘tib ketganda, uchinchi do‘st derazadan qichqirdi: "Borya, sen
maktabda daftaringni unutding!" Kim nimada uyga boradi?
Javob: Alyosha tramvayda, Borya avtobusda, Vitya trolleybusda.
32.Klounlar Bam, Bim, Bom arenaga qizil, ko‘k va yashil ko‘ylaklarda
kirishdi. Ularning poyafzallari ham shu uch rangda yedi. Bimning tuflisi va
ko‘ylagi bir xil rangda yedi. Bomda qizil hech narsa yo‘q yedi . Bamning tuflisi
ko‘k yedi, lekin ko‘ylagi yemas yedi. Bom va Bimning poyabzali va ko‘ylaklarida
qanday ranglar bor yedi?
Yechim:
Qizil poyabzal, qizil ko‘ylak - Bam
Moviy tufli, ko‘k ko‘ylak - Bim
Yashil tufli, yashil ko‘ylak - Bom
55

Javob: Bom - ko‘k ko‘ylak va yashil tufli, Bam - yashil ko‘ylak va ko‘k
tufli.
33 . Shisha, stakan, ko‘za va bankada sut, limonad, kvas va suv mavjud.
Ma’lumki, suv va sut shishada yemas, ko‘za bilan ko‘za o‘rtasida limonad solingan
idish turadi. kvasli idish, bankada na limonad, na suv mavjud. Stakan idish va sutli
idish yonida turadi. Har bir suyuqlik qaysi idishga quyiladi?
Javob: Sut - ko‘zada, limonad - shishada, kvas - idishda, suv - stakanda.
Ijodiy ishlar mavzulari :
1. Boshqotirmalardagi graflar.
2. Shaxmat taxtasidagi graflar va o‘yinlar.
3. Labirintlar haqidagi geometrik masala.
4. Graflar va izomerlar sonini hisoblash.
5. Genetikadagi graflar.
6. Tarmoq graflarini hisoblash.
7. Graflar va transport tarmoqlari.
XULOSA
Graflar nazariyasi hozirgi vaqtda diskret matematikaning jadal
rivojlanayotgan sohasi hisoblanadi. Bu ko‘plab ob’ektlar va vaziyatlarning grafik
modellar shaklida tasvirlanganligi bilan izohlanadi.
Bitiruv malakaviy ishini yozish jarayonida tadqiqot mavzusi bo‘yicha o‘quv,
uslubiy va psixologik-pedagogik adabiyotlar o‘rganildi va tahlil qilindi. Natijada
graflar nazariyasining asosiy tushunchalari va bayonotlari aniqlandi, graflardan
muammolarni yechishni o‘rgatish vositasi sifatida foydalanish imkoniyati, sinfdan
tashqari mashg‘ulotlarning matematika o‘qitish shakli sifatidagi o‘rni aniqlandi,
Talablar va uslubiy tavsiyalarga muvofiq “Graflar nazariyasi elementlari”
fakultativ kursi dasturi ishlab chiqildi.
9-sinf o‘quvchilari uchun kursning matematik mazmuni tanlab olindi, har bir
mavzu bo‘yicha topshiriqlar tizimi ishlab chiqildi, o‘qituvchilarga fakultativ
fanlarni o‘tkazish bo‘yicha uslubiy tavsiyalar tuzildi.
56

Tadqiqot natijalari shuni ko‘rsatdiki, tanlov kursida graflar nazariyasi
elementlarini o‘rganish foydali va uslubiy jihatdan maqsadga muvofiqdir.
Kurs maktab islohoti tomonidan qo‘yilgan muammolarni hal qilishga
yordam beradi
Maktab o‘quvchilarini tayyorlashning ta’lim, tarbiyaviy va rivojlantiruvchi
vazifalari, maktab o‘quvchilarining matematik tafakkurini rivojlantirish,
o‘quvchilarning madaniy darajasini oshirish, o‘quvchilarning mustaqil ijodiy aqliy
faoliyatini shakllantirish, ularni olimpiadalarga va o‘qishga tayyorlaydi.
Binobarin, bitiruv malakaviy ishining maqsadi amalga oshirildi, muammolar
hal qilindi.
Kelgusida 10-11-sinf o‘quvchilari uchun mo‘ljallangan tanlov kurslarini
yaratish maqsadga muvofiq bo‘ladi.
Foydalanilgan adabiyotlar ro‘yxati
1.Diskret matematika.Toshkent,2015
2.A’zamov A. Qiziqarli matematika,Toshkent 2019
3.Fizika, matematika va informatika jurnali.2021-2023-yillar
4.Mirzaahmedov M.A olimpiadalarga o’quvchilarni tayyorlash.Toshkent 2004
Ruscha adabiyotlar
1.Балк М.Б., Балк Г.Д. Математический факультатив - вчера, сегодня, завтра
// Математика в школе. - 2007. - №3. - С.14-17.
2.Барболин М. Головоломки и графы // Квант.- 1975.- № 2.-С.59-60.
3. Белов В.В. Теория графов.- М.: Высшая школа, 1976.- 392 с.
4.Березина Л. Ю. Графы и их применение. - М.: Просвещение, 1979.- 143 с.
5.Берж К. Теория графов и её применение.- М.: Иностранная литература,
1962.- 320 с.
57

6. Донец Г.А. Алгебраический подход к проблеме раскраски плоских
графов.- М.: Наукова думка, 1982.-144с.
7. Журбенко И.Г. О материалах для факультативных занятий // Математика в
школе.- 2009.-№2.- С.52-53
8. Зыков А.А. Основы теории графов. - М.: Вузовская книга, 2004.-664 с.
9.Калугин Н.А. Элементы теории графов. – Самара: Издательство СГАУ,
2013. – 48 с.
10. Керн Г. Лабиринты мира. СПб.: Изд-во "Азбука-классика", 2007.- 448с.
INTERNETDAN FOYDALANILGAN SAYTLAR
1. www.college.ru 2. www.mathnet.ru 3. www.referat.ru 4. www.uff.u z
5. www.pedagog.uz 6. www.laliga.com 7. www. edu.uz 8. www.ziyonet.uz
58

Graflar nazariyasi elementlari va ularning masalalar yechishga tadbiqlari

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish