Muhammad al-Xorazmiy nomidagi tatu qarshi filiali tt va kt fakulteti ax 12-22 guruh talabasi Xushvaqtov Abbosning Diskret Tuzilmalar fanidan tayyorlagan

3-MAVZU: Planar graflar. Pontryagin-Kuratovskiy teoremasi

Planar grafik bo'lgan grafik nazariyasi bir grafik bir-biriga sodir qirralarning har qanday holda tekisligida chizilgan mumkin. Planar bo'lmagan grafikni bunday usulda chizish mumkin emas. A tekislik grafik bir emas samolyot grafik tekislikda chiziladi. Tekis grafikni chorak burchakdan ikki o'lchovli fazodagi nuqtagacha va har bir chetidan tekislik egri chizig'igacha bo'lgan tasvirga ega tekis grafik sifatida belgilash mumkin , shunda har bir egri chiziqning so'nggi nuqtasi oxiri pozitsiyalariga mos keladi. burchak va barcha egri chiziqlar so'nggi nuqtalardan tashqari bir- biridan ajralib turadi .
Graflar nazariyasining shakllanishi Kyonig-sberg ko'priklari haqidagi masala bilan bog'liq ekanligi yaxshi malum. L. Eyler 1736-yilda bu masalaning yechimga ega
emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog'lamli grafda barcha qirralardan faqat bir marta o'tadigan sikl mavjud bo'ladi?
Grafning har bir qirrasidan faqat bir marta o'tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya'ni Eyler sik~ liga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo'lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi.
1-teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo 'lishi zarur va yetarlidir.
Isboti.Zarurligi.G Eyler grafida C—Eyler sikli bo'lsin. U holda Сsikl bo'ylab harakatlanganda grafning har bir uchidan o'tish uchun bir juft qirradan foydalaniladi — bu qirralardan bin uchga kirish uchun, ikkinchisi esa uchdan chiqish uchun zarur bo'ladi. Bu yerda har bir uch darajasining juftligi Сsikldagi har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi.
Yetarliligi.Endi G grafning har bir uchi darajasi juft bo'lsin, deb faraz qilamiz.G graf bog'lamli bo'lgani uchun undagi har bir uchning darajasi ikkidan kichik emas.Ma'lumki, agar grafda har bir uchning darajasi ikkidan kichik bo'lmasa, u holda bunday graf tarkibida sikl mavjud (ushbu bobning 4-paragrafidagi 1-teore-maga qarang).
Demak, G grafning qirralaridan tashkil etilgan qandaydir C2 sikl bor. Bu siklni uning ixtiyoriy v, uchidan boshlab quramiz.Dastlab v, uchga insident bo'lgan ixtiyoriy bir qirrani tanlab, bu qirra bo'ylab harakatlanamiz va uning boshqa uchiga o'tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o'tib, uning boshqa uchiga boramiz. Shuni ta'kidlash zarurki, bunday o'tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalgancha takrorlanishi mumkin.
Har bir uchga insident qirralar soni juft bo'lgani uchun Cxsiklni qurish jarayoni faqat vxuchga borgandagina tugaydi. Bu yerda ikki hoi bo'lishi mumkin:


Cxsikl G grafning barcha qirralaridan o'tadi yoki


Cxsikl G grafnir.p barcha qirralaridan o'tmaydi.


Birinchi holda teorema isbotlandi deyish mumkin. Ikkinchi holda G grafdan Cxsiklga tegishli barcha qirralarni olib tashlaymiz vanatijada hosil bo'lgan grafni Cxdeb belgilaymiz. Bu yerda yakkalanib qolgan uchlarni olib tashlash yoki olib tashlamaslik muhim emas.Agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog'lamli bo'lmagan Gxgrafni hosil qilishimiz ham mumkin.Grafdan qirralarni bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin grafdagi uchlarning darajalari juftligi xossasini o'zgartirmaydi.
G grafning bog'lamliligiga ko'ra, Cxsikl va Gxgraf hech bo'lmasa, bitta umumiy uchga ega bo'lishlari kerak. Shu sababli, C, siklda Gxgrafning qirralariga ham insident bo'lgan qandaydir v2 uch bor. Bu v uchdan boshlab faqat Gxgrafning qirralaridan tashkil topgan yangi Сsiklni qurish mumkin.Сsiklni qurish jarayoni faqat v2 uchga kelib tugashi mumkin.
Oldin qurilgan Cxsiklni ikki qismga ajratamiz:


Cj siklning Vj uchidan boshlanib v2 uchida tugovchi qismi (bu oddiy zanjirni C,(Vj,v2) bilan belgilaymiz) va


Cj siklning v2 uchidan boshlanib, v} uchida tugovchi qolgan qismi (CfavJ).


Agar C2 sikl Eyler sikli bo'lsa, teoremaning tasdig'i isbotlandi desa bo'ladi.Aks holda yuqorida bayon etilgan jarayonni takrorlaymiz.
Berilgan G grafdagi qirralar soni chekli bo'lganligidan, bu jarayon chekli jarayondir.Bu jarayonni yetarlicha takrorlagandan so'ng, albatta, u Eyler siklini qurish bilan yakunlanadi.■


Xulosa
Xulosa qilibaytganda Graflar nazariyasi xozirgi zamon
matematikasining asosiy qismlaridan biridir. turli
paytlarda turli xil ABT va diskret xususiyatlariga ega bo'lgan
xisoblash jihozini loyixalashda (yasashda) graflarning
axamiyati oshamiyati yanada kengaytirildi. Bu kurs ishini yozish davomida oʻtilgan mavzularni takrorladim va graflar haqida toʻliq umumiy tasavvurga ega boʻldim.