Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalri universiteti 2-kurs talabasi bo’riyev husanning diskrit tuzilmalar fanidan yozgan Mustaqil ishi Bajardi: Bo’riyev husan Tekshirdi: Begimov o’ktam

Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalri universiteti 2-kurs talabasi bo’riyev husanning diskrit tuzilmalar fanidan yozgan Mustaqil ishi Bajardi: Bo’riyev husan Tekshirdi: Begimov o’ktam

Reja: I.kirish II.Asosiy qism 1. Planar graflari haqida. 2. Pontryagin-Kuratovskiy teoremasi haqida. 3. Planar grafning xromatik sonini baholash. III.xulosa

Graf, orgraf, uch, qirra, yoy, sirtmoq, karrali qirralar, uchning lokal darajasi, multigraf, ko‘phad, grafning uchlari qo‘shniligi matritsasi, oriyentirlanmagan multigrafning uchlari qo‘shniligi matritsasi, oriyentirlangan grafning uchlari qo‘shniligi matritsasi, sirtmoqsiz orgraf uchlari qo ‘shniligi matritsasi, grafning qirralari qo‘shniligi matritsasi, insidentlik matritsasi Grafning geometrik ifodalanishi. Graflaming turlicha berilish usullari mavjud. Grafning abstrakt matematik ta’rifi uning berilish usullaridan biridir. Grafning abstrakt matematik ta’rifi uni tasawur qilish, anglash, uning xossalarini o‘rganish va bu xossalami 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 mumkin. Albatta, grafning yana boshqa berilish usullari ham mavjud. Quyida bu usullarning bir nechasi bilan tanishamiz.

Platon jismlariga mos barcha graflar tekis graflardir. Tekis grafga izomorf graf planar graf, deb ataladi. Tekis bo‘Imagan grafga ajoyib misol uch uy va uch quduq haqidagi boshqotirma masalaga mos grafdir. Uchta uv u2,u3 uy va uchta qv q2,q3 quduq bor. Har bir uydan har bir quduqqa ixtiyoriy ikkitasi kesishmaydigan qilib uzluksiz yo‘lakchalar o‘tkazish mumkinmi? Qog‘ozda masala shartini qanoatlantiradigan grafni chizishga urinishlar muvaffaqiyatsiz tugaydi. Shunday urinishlardan biri 9-shaklda berilgan

1930-yilda K. Kuratovskiy1 bu tasdiqqa teskari tasdiqni isbot qildi: agar graf tekislikda yotuvchi bo ‘Imasa, и holda и K5 yoki K33grafga gomeomorf bo ‘Igan qism grafga ega bo ‘ladi. Umuman olganda, graflaming planarligi haqidagi bu asosiy natija K. Kuratovskiydan oldin 1922-yilda L.S.Pontryagin2 tomonidan isbotlangan, lekin bu natija o‘sha vaqtda matbuotda e’lon qilinmagan edi. 6-teorema (Pontryagin-Kuratovskiy). Graf planar bo‘lishi uchun и K5 yoki K33grafga gomeomorf qism graflarga ega bo ‘lishi zarur va yetarlidir. Isboti topshiriq sifatida o‘quvchiga havola qilinadi. 7-teorema. Agar karrali qirralari bo‘Imagan sirtmoqsiz grafda m ta uch, n ta qirrali va k ta bog‘lamlilik komponentalari bo‘Isa, и holda quyidagi munosabat o ‘rinlidir