O’zbekiston Respublikasi Raqamli Texnologiyalar Vazirligi Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti
Diskret tuzilmalar fani bo’yicha
Mustaqil ish
Bajardi : Olimjonov Otabek
Tekshirdi : Turg'unov Abrorjon
Toshkent – 2024
Reja :
1. Kirish
2. Qo’shnilik matritsalari va ularga doir misollar
3. Intsidentlik matritsalari
4. Xulosa
5. Foydalanilgan adabiyotlar
Graflar nazariyasi – diskret matematikaning bir bo’limi bo’lib, unda ob’yektlarni o’rganish masalalarida geometrik yondashuv asosiy o’rin tutadi. Graflar nazariyasi temir yo’l tarmoqlari, telefon yoki kompyuter tarmoqlari, irrigatsiya sistemalari kabi murakkab sistemalarning funktsiyalarini analiz qilish uchun qo’llaniladi. Shuningdek, ushbu nazariya iqtisodiy va rejali ishlab chiqarish sohalarida, ishlab chiqarishni boshqarishni avtomatlashtirishda juda ham samaralidir. XVIII asrda mashhur shvetsariyalik matematik L.Eyler (1707- 1783) Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta grafdan foydalanadi. Hozirda bu masala klassik yoki Eyler masalasi nomi bilan mashhur: Shu davrda Kyonigsberg shahrida 2 ta orol bo’lib, ular Pregol daryosining 7 ta ko’prigi bilan birlashtirilgan edi. Masala quyidagicha qo’yilgan: “Shahar bo’ylab shunday sayr uyushtirish kerakki, bunda har bir ko’prikdan bir martadan o’tib, yana sayr boshlangan joyga qaytib kelish kerak”.
Grafning geometrik ifodalanishi. Graflarning turlicha berilish usullari mavjud. Grafning abstrakt matematik ta’rifi uning berilish usullaridan biridir. Grafning abstrakt matematik ta'rifi uni tasavvur qilish, www.ziyouz.com kutubxonasi anglash, uning xossalarini o‘rganish va bu xossalarni amalda qo’llash jarayonida ba’zi qiyinchiliklar tug'dirishi tabiiydir. Shuning uchun grafning boshqa berilish usullaridan ham foydalaniladi. Masalan, grafning elementlarini, ya’ni uchlari va qirralarini (yoylarini) yozish yoki aytish grafning berilish usuli sifatida qaralishi munkin. Albatta, grafning yana boshqa berilish usullari ham mavjud. Quyida bu usullaming bir nechasi bilan tanishamiz. Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini (yoylarini) esa mos uchlarni tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diagrammaga - grafning ko‘rgazmali tasviriga ega bo‘lamiz. Agar uchlar to‘plami va bu uchlaming tutashishlarini ko‘rgazmali qilib taqdim qilish kerak bo'lsa, grafning geometrik tasvirlanishiga mos shaklni qog‘ozda chizib grafni tasvirlash mumkin. Shuni ta’kidlaymizki, ba’zi hollarda diagrammada graf uchlari doirachalar yordamida yoki qandaydir boshqa usulda ifodalanadi. Grafning qirralariga (yoylariga) mos chiziqlarning to‘g‘ri yoki egri bo‘lishi va ulaming uzunligi ahamiyatga ega emas. Muhimi, bu chiziqlar uzluksiz bo‘lib, grafning qandaydir ikkita uchlarini tutashtirishi lozim. Agar qirra yo‘nalishga ega bo‘lsa (ya’ni u yoy bo‘lsa), u holda bunday qirrani ifodalovchi chiziqda yo‘nalish biror usul bilan, masalan, strelka bilan ko‘rsatiladi. Ixtiyoriy graf uchun bunday diagrammalarni istalgancha tuzish mukinligi ravshan. Agar biror diagrammada grafning uchlariga mos keluvchi nuqtalar ustma-ust tushmasa, qirralarga mos keluvchi chiziqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalarga ega boMmasa, bunday diagramma grafning geom etrik ifodalanishi deyiladi. Shuni ta’kidlash kerakki, bitta graf turlicha geometrik ifodalanishi mumkin. Graflar izomorfligining ta’rifi va grafni geometrik ifodalashning mohiyatidan kelib chiqib, abstrakt ta’rif yordamida ifodalangan graf va uning geometrik ifodalanishi o ‘zaro izomorf bo‘ladi. Tabiiyki, izomorf graflar turlicha geometrik ifodalanishlari mumkin.
Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a va b uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut deb ataladi. Tabiiyki, agar qandaydir uchlarni bog‘lovchi marshrut biror at uchdan bir necha marta o‘tsa, u holda marshrutning siklik qismini olib tashlab (bunda siklik qismning o‘rniga marshrutda faqat ai uch qoldiriladi) yana o‘sha uchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo'glangan bo‘ladi, degan xulosaga kelamiz. Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi. Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bogMangan) deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo'yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentlar (qisqacha, komponentlari) deb ataluvchi bog‘lamli qismlaming birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog'lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentlarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog'lamlilik komponentlariga bo‘laklanishi bir qiymatli aniqlanadi.
Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko'paytirish, grafni qismlarga ajratish va hokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo'ladi. Bu amalni qo'llash berilgan grafning uchlari to‘plamidan birorta element yo'qotishni (olib tashlashni) anglatadi. Natijada uchlari soni bittaga kamaygan yangi graf hosil bo‘ladi. Albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi. Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. Bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan birorta element yo‘qotiladi (olib tashlanadi). Berilgan grafdan qirrani (yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish ham mumkin. Bu yerda vaziyatga qarab ish yuritiladi.
Graflar ustida shunday amallarni bajarish mumkinki, ular elementlari soni berilgan grafdagidan ko'proq bo‘lgan boshqa graflarning hosil bo‘lishiga olib keladi. Bunday amallar qatoriga uchni qo'shish amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin.
Qo’shnilik matritsasi
1) Faraz qilaylik, G yo’naltirilmagan graf bo’lsin. Ustunlariga ham qatorlariga ham grafning uchlarini mos qo’yish bilan quyidagi qoida asosida tuzilgan Aij matritsaga grafning qo’shnilik matritsasi deyiladi:
Misol. Quyidagi yo’naltirilmagan grafning qo’shnilik matritsasini tuzing:
Har bir qatordagi qirralar yig’indisi mos uchning darajasini bildiradi. Masalan, deg(A)=3, deg(B)=5.
Teorema . n ta v1 ,v2 ,...,vn uchga ega bo’lgan G graf qirralarini e bilan belgilasak, uchlar darajalari yig’indisi qirralarning ikkilanganiga teng:
Chizmada ko’rsatilgan graf uchlarining darajalar yig’indisi= 4 + 5 + 2 + 5 = 16. Demak, qirralar soni 16/2 = 8.
2) G yo’naltirilgan graf uchun ustunlariga ham qatorlariga ham grafning uchlarini mos qo’yish bilan quyidagi qoida asosida tuzilgan Aij matritsaga grafning qo’shnilik matritsasi deyiladi:
Qo’shnilik matritsasining diagonalida turgan birlar grafning ilmoqlariga mos keladi. Izolyatsiyalangan uchga nollardan tashkil topgan satr va ustun mos keladi. Qo’shnilik matritsasidagi birlar soni grafdagi qirralar soniga teng.
Misol. Uchlari U {1;2;3;4;5} va qirralari V {(1;2),(1;4),(2;3),(3;4),(2;5),(4;5)} bo’lgan G(U,V) grafni yasang.
Intsidentlik matritsasi
Yo’naltirilmagan, uchlari { v1,...,vn} bo’lgan chekli G grafning intsidentlik matritsasi || Aij || ( i 1,...,m, j 1,...,n ) deb, m ta qator va n ta ustundan iborat quyidagi matritsaga aytiladi:
a) Aij matritsaning satrlariga G ning uchlari, ustunlariga esa qirralari mos qo’yiladi;
Yo’naltirilgan, uchlari { v1,..., vn} bo’lgan chekli G grafning intsidentlik matritsasi || Aij || ( i 1,...,m, j 1,...,n ) deb, m ta qator va n ta ustundan iborat quyidagi matritsaga aytiladi:
a) Aij matritsaning satrlariga G ning uchlari, ustunlariga esa qirralari mos qo’yiladi;
Misol. Rasmda tasvirlangan graf uchun intsidentlik matritsasini yozing:
Yechilishi: Intsidentlik matritsasining ko’rinishi quyidagicha bo’ladi.
Xulosa
Graflar bilan hozirda keng qo’llaniladi. Masalan, hozirgi zamonaviy ijtimoiy tarmoqlar ham shu usuldan foydalanadi. Ya’ni foydalanuvchilarni graf uchlari deb olsak, uning qirralari foydalanuvchilar o’rtasidagi aloqani ta’minlaydi. Masalan, bir-birini kuzatish, xabarlashish kabi. Shuningdek graflar eng mas’uliyatli sohalardan biri bo’lgan havo yo’llarida ham qo’llaniladi. Samolyotlar bir-biriga to’qnash kelib qolmasligi uchun graflar va ularning xossalaridan foydalaniladi.
Foydalanilgan adabiyotlar:
1. Oliy ta’lim muassasalarining talabalari uchun darslik: 11 jildlik. H.T. To‘rayev, 1. Azizov; H.T. To'rayevning umumiy tahriri ostida; 0 ‘zR oily va o‘rta-maxsus ta’lim vazirligi. - Toshkent: Tafakkur-Bo‘stoni, 2011. - 288 bet
2. S.S.Sadaddinova. Diskret matematika. 1-qism. O‘quv qo‘llanma. – Toshkent: TATU, 2019. – 221 b.
3. rk.tuit.uz
4. kompy.info
5. ziyouz.com
6. natlib.uz
|
