|
Al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti
|
| Sana | 27.05.2024 | | Hajmi | 0,76 Mb. | | #254826 |
Bog'liq abbosbekdiskretmi34
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD
AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI
Diskret tuzilmalar fanidan
Mustaqil ish
Bajardi : Jaloliddinov Abbosbek
Toshkent – 2024
Mavzu : Chekli grafda qirralar va uchlar soni orasidagi munosabat
Reja
1. Kirish
2. Graf matritsalari
3. Graflar ko’rinishi
4. Xulosa
Graflar nazariyasi – diskret matematikaning bir bo‘limi bo‘lib, unda ob’yektlami o‘rganish masalalarida geoinetrik yondashuv asosiy o‘rin tutadi. Graflar nazariyasi temir yo‘1 tarmoqlari, telefon yoki kompyuter tarmoqlari, irrigatsiya sistemalari kabi murakkab sistemalarning funktsiyalarini analiz qilish uchun qoMlaniladi. 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 boMib, 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 hcrilish usuliari mavjud. Grafning abstrakt matematik ta’rifi uning bcrilish usullaridan biridir. Grafning abstrakt matematik ta’rifi uni tasawur qilish, anglash, uning xossalarini o‘rganish va bu xossalaml amalda qo‘llash jarayonida ba’zi qiyinchiliklar tug‘dirishi lahiiydir. Shuning uchun grafning boshqa berilish usullaridan ham loydulaniladi. Masalan, grafning elementlarini, ya’ni uchlari va qirralarini (yoylarini) yozish yoki aytish grafning berilish usuli siliitida qaralishi mumkin. Albatta, grafning yana boshqa berilish usuliari ham mavjud. Quyida bu usullaming bir nechasi bilan lauishamiz. Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini (yoylarini) esa mos uchlami tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diagrammaga — grafning ko‘rgazmali tusviriga ega bo‘lamiz. Agar uchlar to‘plami va bu uchlarning lulashishlarini ko‘rgazmah qihb taqdim qilish kerakbo‘lsa, grafning geometrik tasvirlanishiga mos shaklni qog‘ozda chizib grafni lasvirlash mumkin. Shuni ta’kidlaymizki, ba’zi hollarda diagrammada graf uchlari doirachalar yordamida yoki qandaydir boshqa usulda ifodalanadi. (iiafning qirralariga (yoylariga) mos chiziqlaming to‘g‘ri yoki cnii bo‘Ushi va ulaming uzunligi ahamiyatga ega emas. Muhimi, bu chiziqlar uzluksiz bo‘lib, grafning qandaydir ikkita uchlarini lulashtirishi lozim. Agar qirra yo‘nahshga ega bo‘lsa (ya’ni u yoy bo’lsa), u holdabunday qirrani ifodalovchi chiziqdayo‘nalishbiron usul bilan, masalan, strelka bilan ko‘rsatiladi. Ixtiyoriy graf uchun bunday diagrammalami istalgancha tuzish inukinligi ravshan. Agar biron diagrammada grafning uchlariga mos kcluvchi nuqtalar ustma-ust tushmasa, qirralarga mos keluvchi « hi/iqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalaiga сца boMmasa, bunday diagramma grafning geometrik ifodalanishi deyiladi. Shuni ta’kidlash kerakki, bitta graf turlicha geometrik llbilalanishi mumkin. (i raflar izomorfligining ta’rifi va grafni geometrik ifodalashning inohiyatidan kelib chiqadiki, abstrakt ta’rif yordamida ifodalangan цгпГ va uning geometrik ifodalanishi o‘zaro izomorfbo‘ladi. Tabiiyki, l/omorf graflar turlicha geometrik ifodalanishlari mumkin.
Eyler bunday sayr marshrutining yo‘qligini 1736 yildayoq chizmalar tarzida isbotlab berdi.
Eyler maqolasi e’lon qilingandan 100 yil o‘tganidan keyin XIX asming o’rtalarida elektr tarmoqlarini, kristall panjaralami, molekula tuzilishini tadqiq qilishda graflar nazariyasining o‘rganish ob’yektlari paydo bo‘la boshladi.
Keyinchalik 1936 yilda vengeriyalik matematik D. Kyonig o‘zining graflar nazariyasiga bag‘ishlangan monografiyasida yuqoridagi sxemalami “graf’ deb nomlaydi. Umuman olganda, qo‘yi!gan masalani yechish uchun qurilgan model – grafdir. Graf uchlar to‘plami va uchlami tutashtiruvchi qirralar to‘plamidan iborat bo‘ladi.
Eyler masalasida (3.2-chizma) A, B, C, D uchlar orol va daryo qirg“oqlarini ifodalaydi, 1 dan 7 gacha raqamlar bilan belgilangan qirralar esa 7 ta ko‘prikni bildiradi. Bir uchdan chiqib, har bir qirradan rosa bir martadan o‘tib, yana shu uchga qaytib keluvchi marshrut chizmasiga Eyler grafi deyiladi. XX asming elliginchi yillaridan boshlab kibemetika va hisoblash texnikasining rivojlanishi bilan umumiy graflar nazariyasiga doir ishlanmalar ham yaratila boshlandi. Shu davrdan graflar nazariyasining masalalari va o’rganish metodlari shakllandi.
Eyler masalasida (3.2-chizma) A, B, C, D uchlar orol va daryo qirg“oqlarini ifodalaydi, 1 dan 7 gacha raqamlar bilan belgilangan qirralar esa 7 ta ko‘prikni bildiradi. Bir uchdan chiqib, har bir qirradan rosa bir martadan o‘tib, yana shu uchga qaytib keluvchi marshrut chizmasiga Eyler grafi deyiladi. XX asming elliginchi yillaridan boshlab kibemetika va hisoblash texnikasining rivojlanishi bilan umumiy graflar nazariyasiga doir ishlanmalar ham yaratila boshlandi. Shu davrdan graflar nazariyasining masalalari va o’rganish metodlari shakllandi.
Yo‘naltirilgan va yo‘naltirilmagan graflar
Bitta uchdan chiqib, yana shu uchga kiruvchi
qirraga ilmoq deyiladi va (a1,a2)kabi belgilanadi:
Grafning ikkita uchi umumiy qirra biian o‘zaro bog‘langan bo‘Isa, ular qa‘shni uchlar deyiladi. Agar grafning ikkita qirrasi umumiy uchga ega bo‘lsa, ular qo‘shni qirralar deyiladi, Quyida turli ko‘rinishdagi graflar keltirilgan:
Agar grafning barcha qirralarida yo‘nalish ko‘rsatilgan bo‘lsa, unga yo‘naltirigan graf deyiladi. Yo‘naltirilgan graflarda uchlami tutashtiruvchi qirralarga yoyiar deyiladi.
Qo’shnilik matritsasi
1) Faraz qilaylik, G vo‘naltirilmagan graf boisin. Ustunlariga ham qatorlariga ham grafning uchlarini mos qo‘yish bilan quyidagi qoida asosida tuzilgan Av matritsaga grafning qo‘shni)ik 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.
Graflar ustida shunday amallami bajarish mumkinki, ular elementlari soni berilgan grafdagidan ko’proq boshqa- graflarning hosil bo‘lishiga olib keladi. Bunday amallar qatoriga uchni qo‘shish amali yoki qirrani (yoyni) qo ‘shish amalini kiritish mumkin. Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin. Masalan, yangi Щ uchni berilgan grafga qo‘shish shu grafning v, va v2 uchlariga insident bo‘lgan qandaydir и qirrasiga qo‘shish orqali quyidagicha ikki bosqichda bajarilishi mumkin: 1) и qirra berilgan grafdan olib tashlanadi; 2) hosil bo’lgan grafga ikkita yangi qirralar: v va v, uchlarga insident ux qirra hamda v va v2 uchlarga insident u2 qirra qo‘shiladi. Bu jarayon grafda qirraga darajasi 2 bo ‘Igan yangi uchni qo ‘shish (kiritish) yoki qirrani ikkiga bo‘lish amali, deb ataladi. Agar G graf G’ grafdan qirrani ikkiga bo‘lish amalini chekli marta ketmarket qo’llash f|»sitasida hosil qilingan bo‘lsa, u holda G graf G’ grafning’tbo ‘linish graft, deb ataladi. Bo‘linish graflaa izomorf bo‘lgan graflar gomeomotf graflar, deb ataladi. A 3-shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki bu graflarning har biri 4-shaklda tasvirlangan bo‘linish grafiga ega.
Foydalanilgan adabiyotlar
Андерсон Дж. Дискретная математика и комбинаторика. — М. Вильямс. 2006. — 960 с.
Зыков А.А. Основы теории графов. - М: Вузовская книга, 2004. - 664 с.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с.
Оре О. Теория графов. — 2-е изд. — М.: Наука, 1980. — С. 336.
Grigoryan A. Analysis on Graphs. University of Bielefeld, WS 2009/10.
6. А.Н. Колмогоров, С.В. Фомин, Элементы теории функций и функционального анализа. Москва, 1976.
7. rk.tuit.uz
8. natlib.uz
9. ziyouz.com
10. cyberleninka.uz
|
| |
