O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Diskret tuzilmalari fanidan MUSTAQIL ISH MAVZU: Planar graflar. Pontryagin-Kuratovskiy teoremasi Bajardi:072-21 guruh talabasi Axmadjanov Tulanboy
Toshkent – 2022 Reja: 1. Planar graflari. 2. Pontryagin-Kuratovskiy teoremasi. 3. Planar grafning xromatik sonini baholash.
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.
