O’zbekiston respublikasi oliy ta‟lim, fan va innovatsiyalar vazirligi

1.2.Grafning abstrakt ta’rifi va u bilan bog'liq boshlang'ich tushunchalar
Shuni ham ta’kidlash kerakki, 1-teoremadagi 3 ni 2 ga almashtirib bo‘lmaydi, chunki tekislikda qirralari (yoylari)ni ifodalovchi kesishmaydigan (aniqrog‘i, chetki nuqtalaridan boshqa umumiy nuqtalari bo‘lmagan) chiziqlar yordamida tasvirlash imkoniyati faqat ba’zi graflargagina xos, ya’ni har qanday grafning 2 o‘lchovli Evklid fazosida (tekislikda) geometrik ifodalanishi mavjud bo‘lavermaydi. fGraflaming geometrik ifodalanishiga doir misollar keltiramiz. 1-misol. 1-shaklda tasvirlangan grafni G=(V,U) deb belgilaymiz. Berilgan G graf belgilangan graf bo‘lib, 4 ta uch va 6 ta qirraga ega. Demak, u (4,6)-grafdir. Bu graf uchun: V— {1,2,3,4}, U — , u = ( 1, 2), 1-shakl. 1 Evklid eramizdan oldingi III asrda yashagan) — qadimgi yunon olimi. 2 n o‘lchovli Evklid fazosida ikkita x = (x vx2,...,xt) e R" va y = ( y 1,y2,—,yJeK ‘ f n \1'2 » . ^ „ \2 vektor orasidagi masofa (metrika) d(x,y)= aniqlanadi. ^ ( ч - У к ) 2 k=l formula bo'yicha 166 и = и = ( 1,3), и = (2,3), ы5=(3,4), и =(2, 2). G grafning barcha и. (/= 1,6) qirralari oriyentirlanmagan (chunki uchlarini tutashtiruvchi chiziqlarda yo‘nalish ko‘rsatilmagan) bo‘lgani uchun G oriyentirlanmagan grafdir. Grafning qirralaridan biri, aniqrog‘i, u6 sirtmoqdir, u2 va u: esa karrali qirralardir. Bu grafda, masalan, 1 va 2 uchlar qo‘shni, 1 va 4 uchlar esa qo‘shni emas. Undagi 2 va 3 uchlar u4 qirraga insident va, aksincha, uA qirra 2 va 3 uchlarga insidentdir. Bu yerda, uA va us qirralar qo‘shni qirralardir, chunki ular umumiy uchga (3 uch) ega, m, va us qirralar esa qo'shni emas. ■ 2-misol. Geometrik ifodalanishi 2-shakldagi ko‘rinishda bo‘lgan oriyentirlangan grafni qaraymiz. Bu grafda o‘n bitta element bor: 5 ta uch va 6 ta yoy, ya’ni shaklda 1 ,j 2 и 5 (5,6)-orgraf berilgan. Bu grafni G=(V,U) bilan belgilaymiz, bu yerda F={1,2,3,4,5}, U= yoki U = . Berilgan G orgrafda sirtmoq ham, karrali yoylar ham yo‘q. Bu grafning (1,3) yoyi uchun 1 boshlang‘ich, 3 uch esa oxirgi uchdir/B 3-misol. XVIII asrda Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va L. Eyler tomonidan yechlishi graflaming matematik nazariyasi paydo bo‘lishiga xizmat qilganligi yuqorida ta’kidlangan edi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 3-shaklda tasvirlangan (bu shakl L. Eyleming birinchi sahifasi ushbu bobning 1-paragrafda keltirilgan ilmiy ishidan olindi). Kyonigsberg ko‘priklari haqidagi masalada quyidagi savolga javob berish so‘raladi: «Shahaming to‘rt А, В, С va D qismidan birida joylashgan uydan а щ-------------------------- q chiqib, yetti ko‘prikning har biridan faqat bir marta o‘tgan holda yana o‘sha uyga qaytib kelish mumkinmi?» Bu savolga javob izlash maqsadida ko‘priklardan o‘tishlar muhimligini e’tiborga olgan holda qo'yilgan masalani tahlil qilish uchun 4-shaklda tasvirlangan grafni qaraymiz. Bu grafning uchlari shahaming A, B, CvaD qismlariga, qirralari esa ko‘priklarga mos keladi. Qaralayotgan graf oriyentirlanmagan graf bo‘lib, 4 ta uch va 7 ta qirradan tashkil topgan. Uning qirralari orasida karralilari bor, lekin sirtmoqlar yo‘q. Kyonigsberg shahridagi ko‘priklardan faqat bir marta o‘tgan holda yurish boshlangan joyga qaytib kelish muammosi, 4-shakldagi grafdan foydalangan holda ushbu bobning 5-paragrafida hal qilinadi. ■ 4-misol.0-shaklda tasvirlangan graflar bir-biriga izomorfdir. ■ 5-misol. 6-shaklda tasvirlangan graflaming har biri olti uch va yetti qirraga ega bo‘lib, ular izomorf emas. ■ 5-shakl. 6-shakl. Hammasi bo‘lib, beshta qavariq muntazam ко ‘pyoqli mavjudligi qadimdan ma’lum (Evklid isbotlagan): tetraedr, kub, oktaedr, dodekaedr va ikosaedr. Bu ko‘pyoqlilaming umumiy nomi ham bor — Platon1jismlari. Shunisi qiziqki, barcha Platon jismlariga 1 Platon (ГШтгау, eramizdan oldingi 428 yoki 427-yil — eramizdan oldingi 348 yoki 347-yil) — yunon faylasufi. 168 mos graflar tekislikda geometrik ifodalanadi. Masalan, tetraedr va kubga mos graflaming geometrik ifodalanishi 7-shaklda tasvirlangan. Darvoqe, Platon jismlaridan tetraedr, kub va dodekaedr kubik grafga misol bo‘ladi. Petersen1graft1 deb ataluvchi 8-shaklda tasvirlangan graf ham k u b it orafH ir Agar graf tekislikda geometrik ifodalanishga ega bo‘lsa, u holda bunday graf tekis (yassi) graf, deb ataladi. Bunday graf tekislikda yotmchi graf deb ham atalishi mumkinj Boshqacha aytganda, tekis grafning barcha uchlari bir tekislikda yotadi hamda barcha qirralari (yoylari) o‘sha tekislikda yotuvchi o‘zaro kesishmaydigan uzluksiz chiziqlar bo‘lib, ular faqat o‘zlari insident bo‘Igan uchlardagina "umumiy nuqtalarga ega. ^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? 1 Petersen (Julius Peter Christian, 1839—1910) — Daniya matematigi. 2 Bu graf haqidagi dastlabki ma’lumot 1891-yilda e’lon qilingan. J. Petersen, Die Theorie der regularen graphs, Acta Math. 15 (1891) 193—220. 7-shakl. 8-shakl. Qog‘ozda masala shartini qanoatlantiradigan grafni chizishga urinishlar muvaffaqiyatsiz tugaydi. Shunday urinishlardan biri 9-shakl9-shakl. 169 Darvoqe, uch uy va uch quduq haqidagi boshqotirma masalaga mos graf har bir bo‘lagida uchtadan uchi bo‘lgan ikki bo‘lakli to‘la grafga misol bo‘la oladij Tekis bolmagan grafga yana bir misol beshta uchga ega bo‘lgan to‘la graf — K5 grafdir. Bu grafning o‘nta qirralari borligi ravshan. Bu yerda ham K5 grafni hech qaysi ikkita qirralari kesishinaydigan qilib tekislikda chizish muvaffaqiyatsiz tugaydi. 10-shaklda K5 grafning to‘qqizta qirrasi kesishmaydigan uzluksiz chiziqlar qilib chizilgan, lekin o‘ninchi chiziq esa uzilishlarga ega, unga tekislikda «joy yo‘q»! 2.2.fGrafiiing maxsus turdagi ко ‘phadyordamida berilishi. Grafni maxsus turdagi ko‘phad yordamida ham berish mumkinligini ta’kidlaymiz. Uchlari to‘plami V= {vpv2, v j bo‘lgan G graf berilgan bo‘lsin. G grafning yakkalangan uchlari yo‘q deb faraz qilamiz. Bugraf m ta xpx2,...xm o‘zgaruvchilarga bog‘liq л о = « . . < - П м ' i< 2n tengsizlik o‘rinlidir. Lekin bu tengsizlik 188 К33 graf uchun 20< n < ------------------- Isboti. Awal qirralar soni n bo‘yicha matematik induksiya usulini qo‘llab, m—k < n tengsizlikni isbotlaymiz. Agar grafda qirralar bo‘lmasa (ya’ni matematik induksiya usulining bazasi sifatida n=0 deb olinsa), u holda grafdagi uchlar soni uning bog‘- lamlilik komponentalari soniga tengdir: k=m. Demak, n=0 bolganda, m—k< n munosabat to‘g‘ridir. Induksion о ‘tish.