Graflar nazariyasi yordamida mantiqiy masalalarni

GRAFLAR NAZARIYASI YORDAMIDA MANTIQIY MASALALARNI 
YECHISH 
Xoljigitov Dilmurod Xolmurod o’g’li
Jizzax davlat pedagogika inistituti o’qituvchisi 
Isroilov Ilyos G’ulomoddin o’g’li
Jizzax davlat pedagogika inistituti 1-bosqich magistranti. 
Annotasiya. Ushbu maqolada biz graflar nazariyasining paydo bo’lish tarixi 
haqida qisqacha ma’lumotlar keltirganmiz. Graflar yordamida mantiqiy 
masalalarni yechishning qulayligiga misollar keltirganmiz.
Kalit so’zlar: Graf, graflar nazariyasi, mantiqiy masala. 
Аннотация. В этой статье мы даем краткий обзор истории теории 
графов. Мы привели примеры простоты решения логических задач с 
помощью графов. 
Ключевые слова: граф, теория графов, логическая задача. 
Annotation. In this article, we give a brief overview of the history of graph 
theory. We have given examples of the ease of solving logical problems using 
graphs. 
Keywords: graph, graph theory, logic problem. 
XIX asming o‘rtalaridalar aniqrog’i 1736-yilda L. Eyler tomonidan o‘sha 
davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko'priklari 
haqidagi masalaning qo‘yilishi va uning yechilishi graflar nazariyasining paydo 
bo‘lishiga asos bo‘ldi. Keyinchalik G. Kirxgof va A. Keli ham graflar nazariyasi 
bilan bog‘liq tadqiqot ishlarini olib borishgan. «Graf» iborasini birinchilardan 
bo’lib D. Kyonig 1936- yilda graflar nazariyasiga bag‘ishlangan dastlabki
darslikni ishlab chiqdi. 
Graflar nazariyasi bo‘yicha tadqiqotlar natijasida insonning oldidagi turli 
masalalar va boshqotirmalarga yangicha yechim topila boshlandi va amaliyotda 
qo‘lianildi.Masalan: boshqotirmalarni hal qilish; qiziqarli o'yinlar; yo‘llar, elektr
zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; 

avtomatlar, blok-sxemalar va kompyuter uchun programmalami tadqiq qilish va 
hokazo. 
Graf deb shunday juftlikka aytiladiki, bu yerda V≠
∅ va
)
,
(
,
2
1
2
1
V
V
U









ko‘rinishdagi juftliklar korteji bo’lib,
V
V

to‘plamning 
elementlaridan tuzilgan juftlikka aytiladi.
Bir uchdan chiquvchi qirralar soni, uchning darajasi deyiladi. Grafning uchi 
toq darajaga ega bo’lsa “toq”, juft darajaga ega bo’lsa “juft” deb ataladi.
Teorema. Har qanday grafda toq darajali uchlar soni juftdir.
Isbot. Grafning qirralarining soni uning uchlari darajasi yigindisining
yarmiga teng. Qirralar soni butun son bo’lgani uchun uchlar darajalari yig’indisi
butun son bo’lishi shart. Bunday holatda esa faqat grafning toq darajali uchlar soni 
juft bo’lgandagina yuzaga keladi. 
1-masala (Qadimiy boshqotirma). Kimdir, juda boy odam, quyidagi
chizmani chizganlarning barchasiga ming dinor berdi. Ammo chizmani chizishda
bitta shart qo’ydi. Ushbu chizmani chizishda qalamni varaqdan uzmasdan va 
ustma-ust chiziq hosil qilmasdan chizish kerak edi. Boy bo’lish umidida odamlar 
juda ko’p qog’ozlarni isrof qilib yubordi, ko’p vaqtni behuda sarf qilishdi va 
afsonada aytilganidek, ko’plab boshlar uzilgan. 
Yechish. Ta’rifga ko’ra bu shaklni shartni buzmay turib chizib bo’lmaydi.
Chunki Eyler graflarini chizish uchun har bir uchidan o’tuvchi qirralar soni juft
bo’lishi kerak, chunki bu grafni chizishda uchlarga kirishlar soni bilan chiqishlar 
soni bir xil bo’ladi, albatta boshlang’ich va yakunlovchi uchlar bundan istisno. 
2-Masala. Qishloqda 9 ta uy bor.Farmon-Ilyos va Amonning qo’shnisi, 
Mirshod-Ilyos va Sanjarning qo’shnisi, Vali-Dilshod va Naimning qo’shnisi, 

Elyor-Naimning qo’shnisi ekanligi aniq va boshqa qo’shnilar mavjud bo’lmasa, 
Farmon kechasi o’zining bog’i orqali o’tib, Naimlarnikidan olma olib bo’ladimi?
Yechish. Muammo haqidagi savolga darhol javob berish oson emas. Keling, o’g’il 
bolalarning ismlarini yozamiz va qo’shnilarni chiziqlar bilan bog’laymiz: 
3-shakldagi grafdan ko’rinib turibdiki Farmon bilan Naim qo’shni emas. Demak, 
Farmon kechasi o’zining bog’i orqali o’tib, Naimlarnikidan olma olib bo’lmaydi. 
Xulosa qilib aytganda graflar nazariyasi va kombinatorika elementlariga oid
olimpiada masalalarini yechishda tadbiqlarini o’rganganimizda, maktab 
olimpiadasida ayrim masalalarni graflar nazariyasi yordamida osonnva tez 
yechish mumkin. Graflarni birlashtirish, biriktirish, ko’paytirish, grafni 
qismlarga ajratish va ba’zi o’yinlarda doim golib bo’lish konbinasiyalarini 
tuzishga doir masalalar yechimlarini keltirib chiqarish mumkin. 
Foydalanilgan adabiyotlar 
1. H.To’rayev va boshqalar, nazariyasi> Toshkent-,,ilm ziyo”-2009.y 
2. Umida Umarovna Umarova. "Science and Education" Scientific Journal / 
ISSN 2181-0842 November 2021 / Volume 2 Issue 11.
3. 
GEOMETRIYANING ALGEBRAIK TENGLAMALARNI 
YECHISHGA BAZI TATBIQLARI
.
 D Xoljigitov - Журнал 
математики и информатики, 2021 
4. 
Dilmurod Xoljigitov, 
GEOMETRIYANING ALGEBRAIK 
TENGLAMALARNI YECHISHGA BAZI TATBIQLARI. , Журнал 
математики и информатики: Том 1 № 3 (2021): MATEMATIKA VA 
INFORMATIKA