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

O’ZBEKISTON RESPUBLIKASI OLIY TA‟LIM, FAN VA INNOVATSIYALAR VAZIRLIGI

OSIYO XALQARO UNIVERSITETINING
IJTIMOIY FANLAR VA TEXNIKA FAKULTETI

KOMPYUTER ILMLARI VA DASTURLASH

TEXNOLOGIYALARI YO`NALISHI

S6 - KT – 22 GURUH TALABASI

TO’LAYEVA MUXLISANING

ALGARITMLAR VA MA`LUMOTLAR STRUKTURASI

FANIDAN “YO’NALTIRILGAN GRAFLAR VA ULAR USTIDA AMALLAR” MAVZUSIDA YOZGAN

KURS ISHI

MAVZU:

MUNDARIJA

Graflar nazariyasi haqida umumiy ma’lumotlar........................1

Grafning abstrakt ta’rifi va u bilan bog'liq boshlang'ich tushunchalar……….................................................................…2 Graflaming berilish usullari....................................................3 Grafning geometrik ifodalanishi.........................................4 Grafning maxsus turdagi ko'phad yordamida berilishi.................5 Qo‘shnilik matritsalari............................................................6 Insidentlik matritsalari...............................................................7 Graflar ustida amallar.................................................................8

1. 
   Graflar nazariyasi haqida umumiy ma’lumotlar
   

Graflami ko'paytirish Graflaming berilish usullari 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. 164 2. l.fGrafning 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. Grafning uchlarini tekislikda yoki fazoda nuqtalar bilan, qirralarini (yoylarini) esa mos uchlami tutashtiruvchi uzluksiz chiziqlar bilan ifodalab, qandaydir diagrammaga — grafning ko‘rgazmali tasviriga ega bo‘lamiz. Agar uchlar to‘plami va bu uchlarning tutashishlarini ko‘rgazmali qilib taqdim qilish kerak bo‘lsa, grafning geometrik tasvirlanishiga mos shaklni qog‘ozda chizib grafni tasvirlash mumkin. Shuni ta’kidlaymizki, ba’zi hollarda diagrammada graf uchlari doirachalar yordamida yokr qandaydir boshqa usulda ifodalanadi. Grafning qirralariga (yoylariga) mos chiziqlarning to‘g‘ri yoki egri bo‘lishi va ularning uzunligi ahamiyatga ega emas. Muhimi, bu chiziqlar uzluksiz bo‘lib, grafning qandaydir ikkita uchlarini tutashtirishi lozim. Agar qirra yo‘nalishga ega bo‘lsa (ya’ni u yoy bo‘lsa), u holda bunday qirrani ifodalovchi chiziqda yo‘nalish biron usul bilan, masalan, strelka bilan ko‘rsatiladi. Ixtiyoriy graf uchun bunday diagrammalami istalgancha tuzish mukinligi ravshan. Agar biron diagrammada grafning uchlariga mos keluvchi nuqtalar ustma-ust tushmasa, qirralarga mos keluvchi chiziqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalarga ega bo‘lmasa, bunday diagramma grafning geometrik ifodalanishi deyiladi. Shuni ta’kidlash kerakki, bitta graf turlicha geometrik ifodalanishi mumkinj Graflar izomorfligining ta’rifi va grafni geometrik ifodalashning mohiyatidan kelib chiqadiki, abstrakt ta’rif yordamida ifodalangan graf va uning geometrik ifodalanishi o‘zaro izomorf bo‘ladi. Tabiiyki, izomorf graflar turlicha geometrik ifodalanishlari mumkin. 165 1-teorema. Har qanday chekli grafni 3 о ‘Ichovli Evklid1 fazosida2 geometrik ifodalash mumkin. Isboti. Teoremaning quyidagi konstruktiv isbotini keltiramiz. Grafning abstrakt ta’rifiga binoan, uning hech bo‘lmasa, bitta uchi mavjud. Agar grafda faqat bitta uch bo‘lsa, u holda uni 3 o‘lchovli Evklid fazosining biron nuqtasi sifatida ifodalaymiz. Agar grafda uchlar bittadan ko‘p bo‘lsa, u holda ulami uch о‘Ichovli Evklid fazosidagi biror to‘g‘ri chiziqning (hech qaysi ikkitasi ustma-ust tushmaydigan) nuqtalariga mos keladi deb hisoblaymiz. Shu to‘g‘ri chiziqdan qirralaming (yoylaming) har biriga mos keluvchi turU yarimtekisliklami o‘tkazamiz (graf chekli bo‘lgani uchun buning imkoniyati bor). Har bir qirrani (yoyni) unga mos yarimtekislikda, chetlari mos uchlami ifodalovchi nuqtalarda bolgan hamda bu to‘g‘ri chiziq bilan boshqa umumiy nuqtasi bo‘lmagan qandaydir chiziq vositasida ifodalaymiz. Yarimtekisliklarning tuzilishiga ko‘ra, bu chiziqlar, chetki nuqtalami hisobga olmaganda, umumiy nuqtalarga ega emas. ■
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.
3.Graflaming berilish usullari
Grafdagi qirralar sonini nQ bilan belgilab, bu son minimal bolsin, ya’ni grafdan istalgan qirrani olib tashlash amali boglamlilik komponentalari soni o‘zgargan graf hosil qilsin, deb faraz qilamiz. Bundan tashqari, matematik induksiya usuli talabiga binoan n=n0 uchun isbotlanishi kerak bolgan tengsizlik o‘rinli bolsin, deb faraz qilamiz. Tabiiyki, bu holda grafdan istalgan qirrani olib tashlasak (bunda olib tashlangan qirraning chetlaridagi uchlar grafga tegishli bo lib qolaveradi), hosil bolgan grafning 1 Kuratovskiy (Kuratowski Kazimej, 1896—1980) — polyak matematigi. 2Pontryagin Lev Semyonovich (П онтрягин Лев С еменович, 1908— 1988) — ms matematigi, akademik. 189 uchlari soni m ga, qirralari soni (n0—1 )ga, bog‘lamlilik komponentalari soni esa (k+\ )ga teng boladi. Induksiya faraziga binoan m—(k+1)< n(—1 tengsizlik o‘rinlidir. Bu tengsizlikdan m—k< n tengsizlik isbotlandi. ( ffl_ Endi n<------------------- tengsizlikni isbotlaymiz. Buning uchun grafning har bir boglamlilik komponentasi tola graf bolsin deb faraz qilamiz. Berilgan grafning uchlari soni, mos ravishda, mj va m. bolgan ikkita boglamlilik komponentalari D. va D graflardan iborat bolsin, bu yerda, m.>m> 1. Tushunarliki, D. va Dj graflaming uchlari umumiy soni {m.+ m) ga tengdir. Bu D. va D] graflami uchlari sonlari, mos ravishda, (m;.+1) va (m -l) bolgan tola graflar bilan almashtirsak, uchlar umumiy soni o‘zgarmaydi, lekin qirralaming umumiy soni (C^+i+C* )-(C^,+С„ ) miqdorga o‘zgaradi. Oxirgi ifodaning ko‘rinishini quyidagicha o‘zgartiramiz: K , + c l J ~ K + c l ) = = ~ [(/И,.+ 1)m/+ (rrij - 1)(mj - 2) - - 1) - - 1)] = =^ (mf+nil+m2j - ntj - 2mj+2 -m f+ - m2 + m})= -m i-m j +1>0. Shunday qilib, uchlari soni m va boglamlilik komponentalari soni к bolgan grafda maksimal sondagi qirralar bolishi uchun u (&-—1) ta yakkalangan uchlar va (m—k+l) ta uchga ega tola graf birlashmasidan tashkil topishi kerak ekan. Bu yerdan isbotlanishi kerak bolgan tengsizlik kelib chiqadi. ■ 7-teoremaning tatbiqi sifatida quyidagi tasdiqni keltiramiz. о , .... (m -l)(m -2) , , 3-natija. m ta uchga ega, qirralari soni-------^------- dan katta, karrali qirralari bo ‘Imagan sirtmoqsiz graf bog ‘lamlidir. Isboti. Birinchidan, agar sirtmoqsiz va karrali qirralari bo‘1- magan grafning boglamlilik komponentalari soni к ga teng bolsa (ke IV), u holda, 7-teoremaga binoan, bunday grafning qirralari 190 som . (m -k )(m -k + l) 1 2 dan katta emas. Ikkinchidan (m -l)(m -2) (m -k)(m -k+1) 2 < 2 tengsizlik faqat &=1 bolsagina to‘g‘ridir. ■ Tabiiyki, boglamli grafdan qirrani yoki bir necha qirralami olib tashlash natijasida hosil bolgan graf boglamli bolishi ham, bolmasligi ham mumkin. Agar boglamli grafdan qirrani olib tashlash amali grafning boglamlilik xususiyatini buzsa, u holda bunday qirrani ajratuvchi qirra, deb ataymiz. Ravshanki, berilgan boglamli grafda ajratuvchi qirralar ko‘p bolishlari mumkin. Ajratuvchi qirralar to‘plamining hech qaysi qism to‘plami elementlari ajratuvchi qirralar bolmasa, bu qirralar to‘plamini kesim deb ataymiz. Grafdan kesimga tegishli qirralar olib tashlansa, natijada ikki boglamli komponentalari bolgan graf hosil bolishi ravshandir.
4.Grafning geometrik ifodalanishi
Agar kesim yagona qirradan iborat bo Isa, u holda bu qirra ко ‘prik, deb ataladi. 3-misol. 1-shaklda tasvirlangan (15,14)-grafni G bilan belgilaymiz. Bu graf boglamli graf emas, uning to£rtta boglamli komponentalari bor: G -G x UGjUG^UG^bu yerda Gx — uchlari to‘plami {1,2,3,4,5,6} bolgan oriyentirlanmagan (6,7)-graf, G2 — bitta 7 belgili uchga ega oriyentirlanmagan (1,0)-graf, G3 ham bitta 10 belgili uchga ega oriyentirlanmagan (1,0)-graf, GA esa uchlari to‘plami {8,9,10,11,12,13,14,15} bolgan oriyentirlanmagan (7,7)-grafdir. Agar G grafning GA boglamli komponentasini alohida graf deb qarasak, bu grafda {(8,9), (14,15)} ko‘rinishdagi ajratuvchi qirralar to‘plamini ko‘rsatish mumkin. Bu qirralar kesimni tashkil 5 8 1 1-shakl. 191 etadi. G grafning G{ va G4 bog‘lamli komponentalari ko‘priklarga egadir. Masalan, (2,5) va (5,6) qirralar Gt graf uchun ko‘priklardir. ■ Endi D. Kyonig tomonidan 1936-yilda isbotlangan ushbu teoremani grafning ikki bolakli bolishi yoki bolmasligini tekshirish alomati (mezoni) sifatida keltiramiz. 8-teorema (D. Kyonig). Grafning ikki bo‘lakli bolishi uchun uning tarkibida uzunligi toq son bilan ifodalanuvchi sikl bo ‘Imasligi zarur va yetarlidir. Isboti o‘quvchiga havola qilinadi. ■ Berilgan G—( V, U) grafning ikki bolakliligini aniqlashning sodda usuli bor. Bu usul ko‘ndalangiga izlash, deb ataluvchi soddagina izlash g‘oyasiga asoslangan. Ko‘ndalangiga izlash usuliga ko‘ra, grafning uchlari 0,1,2,3,... raqamlar bilan quyidagi qoida bo‘yicha belgilanadi. Dastlab grafning ixtiyoriy uchi 0 raqami bilan belgilab olinadi. Shu 0 belgili uchga qo‘shni barcha uchlarga 1 belgisi qo‘yiladi. Endi 1 belgili har bir uchga qo‘shni uchlami aniqlab, ular orasidagi belgisi yo‘q uchlarga 2 belgisini qo‘aymiz. Keyin 2 belgisiga ega barcha uchlami aniqlab, ular uchun ham yuqoridagiga o‘xshash ish yuritamiz. Bu jarayonni mumkin bolgan qadar davom ettiramiz. Tushunarliki, agar G graf boglamli bolsa, u holda ko‘ndalangiga izlash usuli grafning barcha uchlarini raqamlab chiqish imkonini beradi. Boglamli graf uchlarini belgilash jarayoni tugagandan so‘ng, uning uchlari to‘plami Vm ikkita Kva К to‘plamga quyidagicha ajratamiz: juft raqamli uchlami V to'plamga, qolgan uchlami esa V to'plamga kiritamiz (0 raqamli uch V to‘plamga kiritiladi). G grafning ikkala uchi ham V to‘plamga tegishli barcha qirralari kortejini Uj bilan, uning ikkala uchi ham V to‘plamga tegishli barcha qirralari kortejini esa U bilan belgilaymiz. Agar Ц va Uq kortejlar bo‘sh bolsa, u holda berilgan G graf ikki bolaklidir, aks holda, u ikki bolakli emas. Hozirgacha k>2 bolgan hoi uchun grafning к bolakliligini aniqlash bo‘yicha oddiy usul topilmagan. Muammoli masala va topshiriqlar 1. Elementlari siz yashayotgan aholi punktidagi chorraha va yo‘llarga mos keluvchi grafni geometrik ifodalab, bu grafda marshrutlar, zanjirlar, oddiy zanjirlar va sikllami aniqlang. 192 2. Ixtiyoriy graf uchun yo shu grafning o‘zi, yoki uning toldiruvchi grafi bo‘g‘lamli bolishini isbotlang. 3. Agar G boglamli graf va uning qandaydir sikliga tegishli qirrasi и bolsa, u holda G grafdan и qirrani olib tashlash natijasida hosil bolgan graf boglamli bolishini isbotlang. 4. 2-shaklda tasvirlangan graf uchun uchlar, qirralar va yoqlar sonini aniqlang hamda Eyler formulasi va Eyler teoremasining 2-natijasidagi tengsizlik o‘rinliligini tekshiring. 5. Eyler teoremasining 1-natijasida ifodalangan tengsizlikni 1-shaklda tasvirlangan graf uchun tekshirib ko‘ring. 6. Pontryagin-Kuratovskiy teoremasini isbotini o‘rganing. 7. Agar 1-topshiriqni bajarish natijasida hosil bolgan grafda ajratuvchi qirra(lar), kesim(lar) va ko‘prik(lar): a) topilsa, u holda ulami aniqlang; b) topilmasa, u holda bu grafga yangi elementlami shunday qo‘shingki, natijada ajratuvchi qirra(lari), kesim(lari) va ko‘prik(lari) topiladigan graf hosil bolsin. Eyler va Gamilton graflari Graf, uch, qirra, sikl, Eyler zanjiri, Eyler sikli, Eyler graft, yarim Eyler graft, oriyentirlangan Eyler yo ‘li, oriyentirlangan Eyler graft, Flyori algoritmi, Gamilton zanjiri, Gamilton sikli, Gamilton graft, yarim Gamilton graft, kommivoyajer masalasi. 5.1. Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lum. 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 boMadi? Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga) 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 uchlaming darajalari juft bo‘lishi zarur va yetarlidir. 194 Isboti. Zarurligi. G Eyler graflda C — Eyler sikli bo‘lsin. U holda С sikl bo‘ylab harakatlanganda grafning har bir uchidan o‘tish uchun bir juft qirradan foydalaniladi — bu qirralardan biri 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-teoremaga qarang). Demak, G grafning qirralaridan tashkil etilgan qandaydir Cj sikl bor. Bu siklni uning ixtiyoriy Vj uchidan boshlab quramiz. Dastlab v, uchga insident bolgan 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 mum kin. Har bir uchga insident qirralar soni juft bo‘lgani uchun C, siklni qurish jarayoni faqat v, uchga borgandagina tugaydi. Bu yerda ikki hoi bo‘lishi mumkin: 1) Cj sikl G grafning barcha qirralaridan o‘tadi yoki 2) C, sikl G grafning barcha qirralaridan o‘tmaydi. Birinchi holda teorema isbotlandi deyish mumkin. Tkkinchi holda G grafdan Cl siklga tegishli barcha qirralami olib tashlaymiz va natijada hosil bo‘lgan grafni Cx deb belgilaymiz. Bu yerda yakkalanib qolgan uchlami olib tashlash yoki olib tashlamaslik muhim emas. Agar yakkalanib qolgan uchlar olib tashlanmasa, natijada bog‘lamli bo'lmagan Gl grafni hosil qilishimiz ham mumkin. Grafdan qirralami bunday olib tashlash amali, tabiiyki, grafning qirralari sonini kamaytiradi, lekin grafdagi uchlaming darajalari juftligi xossasini o‘zgartirmaydi.
5.Grafning maxsus turdagi ko'phad yordamida berilishi
С grafning bog‘lamliligiga ko‘ra, C, sikl va G] graf hech bo‘lmasa, bitta umumiy uchga ega bo‘lishlari kerak. Shu sababli, C, siklda G] grafning qirralariga ham insident bo‘lgan qandaydir v2 uch bor. Bu v2 uchdan boshlab faqat Gx grafning qirralaridan tashkil topgan yangi C' siklni qurish mumkin. C' siklni qurish jarayoni faqat v2 uchga kelib tugashi mumkin. 195 Oldin qurilgan Cl siklni ikki qismga ajratamiz: 1) C, siklning v, uchidan boshlanib v2 uchida tugovchi qismi (bu oddiy zanjimi Cj(vpv2) bilan belgilaymiz) va 2) Cj siklning v2 uchidan boshlanib, v, uchida tugovchi qolgan qismi (C,(v2,vj)). U holda v, uchdan boshlab Cj(vpv2) zanjiming qirralari bo‘ylab v2 uchga boruvchi, keyin C' siklning barcha qirralaridan o‘tuvchi va, nihoyat, C,(v2,vj) zanjiming qirralari bo‘ylab v[ uchga qaytib keluvchi yangi C2=Cl(vl,v2)\JC'\JCl(v2,vl) siklni hosil qilish mum kin. 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 yetarUcha takrorlagandan so‘ng, albatta, u Eyler siklini qurish bilan yakunlanadi. ■ 1-natija. Bog ‘lamli graf yarim Eyler graft bo‘lishi uchun undagi ikkitadan ко ‘p bo ‘Imagan uchning darajalari toq bo ‘lishi zarur va yetarlidir. Isboti 1-teoremaning isbotidan ba’zi o‘zgartirishlar natijasida hosil qilinishi mumkin. ■ 1-teorema asosida Kyonigsberg ko‘priklari haqidagi masalaning (ushbu bobning 1-paragrafiga qarang) yechimi mavjud emas, degan xulosaga kelamiz, ya’ni Kyonigsberg shahrining ixtiyoriy qismida joylashgan uydan chiqib, Pregel daiyosi ustiga qurilgan yetti ko‘prikdan faqat bir martadan o‘tgan holda yana o‘sha uyga qaytib kelish mumkin emas. Oriyentirlangan graflarda oriyentirlangan Eyler yolini izlash bilan shug‘ullanish mumkin. Har bir yoydan faqat bir marta o‘tadigan yo‘l oriyentirlangan Eyler yo‘li, deb ataladi. Tarkibida oriyentirlangan Eyler yo‘li bor bo‘lgan oriyentirlangan graf oriyentirlangan Eyler grafi, deb ataladi. Endi qirralari soni n ga teng bo‘lgan berilgan Eyler grafida Eyler zanjirini tuzishning Flyori algoritmini1 keltiramiz. Bu 1 Bu algoritm E. Lyuka tomonidan e ’lon qilingan. (Lucas, E. Recreations Mathematiqques. Paris: Gautheir-Villas, 1891). 196 algoritmga ko‘ra, grafning qirralari Eyler siklida uchrashi tartibi bo‘yicha 1 dan n gacha raqamlab chiqiladi. Berilgan Eyler grafi uchun Flyori algoritmiga binoan quyidagi ikkita qoida asosida ishlar ketma-ket bajariladi: 1. Grafning ixtiyoriy v uchidan boshlab, bu uchga insident bo‘lgan istalgan qirraga (rnasalan,vv/ qirraga) 1 raqami beriladi. Bu qirra grafdan olib tashlanadi va v uchdan V uchga (ya’ni olib tashlangan qirraga insident uchga) o‘tiladi. 2. Oxirgi o‘tishdan oldingi o‘tish natijasida hosil bo‘lgan uch w bo‘lsin va oxirgi o‘tishda biror qirraga к raqami berilgan deylik. w uchga insident istalgan qirra imkoniyati boricha shunday tanlanadiki, bu qirrani olib tashlash grafdagi bog‘lamlilikni buzmasin. Tanlangan qirraga navbatdagi ( k + 1) raqami beriladi va bu qirra grafdan olib tashlanadi. ■ Flyori algoritmiga ko‘ra, ish yuritish Eyler grafi uchun doimo chekli jarayon ekanligi va bu jarayon doimo grafdan barcha qirralarning olib tashlanishi, ya’ni Eyler zanjirini tuzish bilan tugashi isbotlangan. Shuni ham ta ’kidlash kerakki, Flyori algoritmini qo‘llash jarayonida qirralami tanlash imkoniyatlari ko‘p bo‘lgani uchun, bunday vaziyatlarda, algoritmni qo‘llash mavjud Eyler sikllaridan birjni topish bilan cheklanadi. Tushunarliki, Flyori algoritmini takror qo‘llab (bunda qirralami tanlash jaroyoni algoritmini awalgi qo‘llashlardagidek aynan takrorlanmasligi kerak) grafda mavjud bo‘lgan barcha Eyler sikllarini topish mumkin. 1-misol. 1-shaklda tasvirlangan grafni qaraymiz. Awalo, bu grafning Eyler grafi bo‘lishi shartini, ya’ni 1-teorema shartlarining bajarilishini tekshiramiz. Berilgan grafda to‘qqizta uch bo‘lib, 1, 3, 7, 9 belgili uchlaming darajasi ikkiga, 2, 4, 6, 8 belgili uchlaming darajasi to‘rtga, 5 belgili uchning darajasi esa oltiga teng. Xullas, bu grafdagi barcha 3 7 uchlaming darajalari juftdir. Shuning uchun, 1-teoremaga ko‘ra, 1 -shaklda tasvirlangan graf Eyler grafidir va uning tarkibida Eyler sikli mavjud. Berilgan grafga flyori algoritmini qo‘llab, mavjud Eyler sikl- 4 6 9 laridan birini aniqlaymiz. Dast- i-shakl. 197 labki uch sifatida grafdagi 1 belgili uch olingan bo‘lsin. Bu uchdan ikki y o ‘nalishda: (1;2) qirra b o ‘ylab yoki (1;4) qirra b o ‘ylab harakatlanish mumkin. Masalan, (1;2) qirra bo‘ylab harakatlanib 2 belgili uchga o ‘tamiz. Endi harakatni 3 yo‘nalishda: yo (2;3) qirra b o‘ylab, yo (2;4) qirra bo‘ylab, yoki (2;5) qirra bo‘ylab davom ettirish mumkin. Aytaylik, (2;3) qirra bo‘ylab harakatlanib 3 belgili uchga o ‘tgan boiaylik. Shu usulda davom etish mumkin b o‘lgan Eyler sikllaridan birini, masalan, quyidagi siklni hosil qilamiz: ((1 ,2 ), (2 ,3 ),(3 ,5 ), (5,4), (4,6), (6,9), (9,8), (8,6), (6 ,5 ),(5 ,8 ), (8,7), (7,5), (5,2), (2,4),(4,1)). ■ 5.2. Gamilton' graflari. Graflar nazariyasining natijalari muayyan shartlarni qanoatlantiruvchi marshrutlarni topish masalasiga keltiriluvchi bir qator muammolarni hal etishda qollanilishi mumkin. Shunday muammolardan biri sifatida Uilyam Gamilton nomi bilan bog‘liq masalani keltiramiz. U. Gamilton dodekaedm i tekshirib, uning har bir uchidan faqat bir marta o ‘tadigan siklni izlab topgan va shu asosda 1859-yilda «Olam bo‘ylab sayohat» nom li o ‘yinni topgan. Grafning har bir uchidan faqat bir marta o ‘tadigan zanjir Gamilton zanjiri, deb ataladi. Yopiq G am ilton zanjiriga (ya’ni Gamilton sikliga) ega graf Gamilton grafi, deb ataladi. Agar grafda yopiq b o ‘lmagan G am ilton zanjiri topilsa, u holda bunday graf yarim Gamilton grafi, deb ataladi. Oriyentirlangan graflarda ham grafning har bir uchidan faqat bir marta o ‘tuvchi oriyentirlangan sikllami qarash mumkin. Eyler va Gamilton graflari bir-birlariga o ‘xshash ta’riflansa-da, grafning G am ilton grafi ekanligini tasdiqlaydigan alomat (m ezon) topish masalasi ancha murakkab hisoblanadi. Hozirgi vaqtgacha graflar nazariyasida grafning Gamilton grafi ekan1 Gamilton (William Rowan Hamilton, 1805— 1865) — Irlandiya matematigi, fizigi va astronomi. Uilyam G am ilton 198 ligini tasdiqlovchi shartlami o ‘rganish bo‘yicha izlanishlar davom etib, bu sohadagi ishlar hanuzgacha dolzarbligini yo‘qotmasdan kelmoqda. Qandaydir shartlarga bo‘ysunuvchi graflarda Gamilton sikli mavjudligi haqida bir necha tasdiqlar mavjud. Qator hollarda bu tasdiqlaming isbotlari konstruktiv bo‘lganligidan, Gamilton siklini tuzishga doir samarali algoritmlar ham yaratilgan. 1952-yilda G. E. Dirak1 quyidagi teoremani isbotladi. 2-teorema (Dirak). Uchlari soni uchtadan kam b o ‘lmagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam b o ‘lmasa, bu graf Gamilton grafi bo‘ladi. I s b o t i 2. Uchlari soni m > 3 bo‘lgan graf berilgan b o ‘lsin. Bu /71 grafning istalgan v uchi uchun p(v)> — shart bajarilsa-da, u Gam ilton grafi bo‘lmasin, deb faraz qilamiz.
6.Qo‘shnilik matritsalari
Tabiiyki, istalgan grafga yetarlicha sondagi yangi uchlarni qo‘shib olib, bu uchlarning har birini grafdagi har bir uch bilan qirra orqali tutashtirsak, berilgan grafdan G am ilton grafini hosil qilish mumkin. Bu usul bilan berilgan grafdan Gam ilton grafini hosil qilish uchun qo‘shilayotgan zarur uchlarning minimal sonini к > 0 bilan belgilaymiz. Yuqorida bayon qilingan usulni qo'llash natijasida hosil bo‘lgan grafdagi uchlardan tashkil topgan (v|,w,v2,...,v |) ketma-ketlikbiron Gam ilton sikli bo‘lsin, bunda vpv2 — berilgan grafning uchlari, w esa q o‘shib olingan uchlardan biri. Tushunarliki, v2 uch vl uchga qo‘shni emas, aks holda siklni tuzishda w uchni ishlatmasligimiz mumkin b o ‘lar edi. Bu esa к sonining minimalligiga ziddir. / / Agar grafdagi v, uch v, uch bilan qo‘shni, v2 uch esa v2 / / uch bilan qo‘shni b o‘lsa, v2 uch siklda v, uchdan bevosita keyingi uch bo‘la olmaydi, chunki bu holda (v,,w ,v2,..., v/, v /,.--, Vj) siklni / / (v^vj ,...,v 2,v2 Vj) siklga almashtirish mumkin. Natijada hosil bo‘lgan grafning v2 uchga qo‘shni bo‘lmagan uchlari soni v, uchga qo‘shni uchlari sonidan kichik emasligi (ya’ni bu son kamida 1 Dirak (Dirac Gabriel Andrew, 1925— 1984) — Daniya matematigi. 2 Dirak teoremasining bu isboti D.J. Nyuman tomonidan keltirilgan. 199 ( ga teng ekanligi) ravshan. Boshqa tomondan esa hosil bo‘lgan grafning v, uchga qo‘shni uchlari soni kamida ga ( m 4 V tengligi ko‘rinib turibdi. Hosil bo‘lgan grafning har bir uchi bir vaqtning o ‘zida v2 uchga qo‘shni ham, qo‘shnimas ham bo'lishi mumkin emasligidan hosil b o‘lgan graf uchlarining umumiy soni m (m + k) ushbu 2 y + ^ m +2k sondan kichik em as, y a ’ni m+k > m + 2к . Oxirgi tengsizlik faqat k=0 bo‘lgandagina to‘g‘ridir. Bu esa k>0 shartiga ziddir. ■ Dirak teorem asi shartlari berilgan grafning G am ilton grafi bo‘lishi uchun yetarli, lekin ular zaruriy emas. Bu tasdiq to‘g ‘ri ekanligini 2-shaklda tasvirlangan graf misolida ko‘ramiz. Bu grafda sakkizta uch b o iib (m=8 >3), har bir v (v = l,8 ) uchning darajasi 3 ga teng: p (v)=3. Dirak m teorem asidagi p (v)> — shart grafdagi hech qaysi uch uchun bajarilmasa ham , bu grafda (1 ,2 ,3 ,4 ,5 ,6 , 7,8,1) ko‘rinishdagi G am ilton sikli bor bolgani uchun u Gamilton grafidir. 1960-yilda O. Ore1 quyidagi teoremani isbotladi. 3-teorema (Ore). Agar uchlari soni m ga (m>2) teng bo'lgan grafdagi q o ‘shni b o ‘lmagan ixtiyoriy uchlar darajalari y ig ‘ndisi m dan kam bo ‘Imasa, и holda bu graf Gamilton grafi bo ‘ladi. Isb o ti o ‘quvchiga topshiriq sifatida beriladi. 2-misol. 3-shaklda tasvirlangan graflar G am ilton graflariga misol bo‘la oladilar. Bir qarashdayoq sezish mumkinki, bu graflaming har birida bir nechtadan G am ilton sikllari mavjud. M umkin bo‘lgan ba’zi Gamilton sikllari shaklda qa3-shakl. Hn chiziqlar bilan ifodalangan. ■ h s — X I 1 Ore (Oysten, 1899—1968) — Norvegiya matematigi. 200 3-misol. Shaxmat o ‘yinidagi otning yurishi haqidagi Eyler masalasi deb ataluvchi quyidagi masalani qaraymiz. Shaxmat taxtasidagi istalgan katakda turgan shaxmat oti uchun yurishlarning shunday ketma-ketligini tuzingki, u barcha kataklardan faqat bir martadan o ‘tsin va yurish boshlangan katakka qaytib kelsin. Bu masalani hal qilish maqsadida tuzilgan graf (shaxmat taxtasidagi kataklarga grafning uchlari, otning yurishlariga esa uning qirralari mos qo‘yilishi nazarda tutilmoqda) ham Gamilton grafiga m isol bo‘la oladi. Bu masalaning yechimlaridan biri 4-shaklda keltirilgan. ■ 4-misol. 5- shaklda tasvirlangan grafda G a m ilto n 8 zanjiri mavjud emas. Berilgan grafda Gamilton zanjirining mavjudligi shartlarni 0; 2) v = v 2 bo‘lgandagina d(vv v2)= 0 bo‘ladi; 3) i/(v1,v2)=rf(v2,vI); 4) rf(vp v3). Oxirgi aksioma uchburchak tengsizligi, deb ataladi. Boglamli G = ( V,U) graf berilgan bo‘lsin. G grafning ixtiyoriy ve V uchi uchun aniqlangan miqdor shu v uchning ekssentrisiteti, deb ataladi. Boglamli G graf barcha uchlarining ekssentrisitetlari orasidagi qiymati eng kattasi (maksimali) shu grafning diametri, deb ataladi. 6-§. ifning metrik xarakteristikalari e ( v ) = max d ( v , w) 204 G grafning diametri, odatda, d(G ) bilan belgilanadi: d (G )=max e ( v ) weV Diametr bu grafning istalgan ikki uchi orasidagi mumkin bo‘lgan eng katta masofadir, ya’ni d (G )= max d (vp v2). V[ ,V2eF Uzunligi d(G ) ga teng bo‘lgan oddiy zanjir diametral zanjir, deb ataladi. Tabiiyki, grafda diametral zanjir yagona bo‘lmasligi mumkin. Bog‘lamli G graf barcha uchlarining ekssentrisitetlari orasidagi qiymati eng kichigi (minimali) shu grafning radiusi, deb ataladi. G grafning radiusi, odatda, r(G ) bilan belgilanadi: r((j)= m in e (v ). Ravshanki, r(G )=m inm axd (vv v2). veV Vl v2eV Bog‘lamli G grafdagi ekssentrisiteti radiusga teng v0 uch grafning markazi (markaziy uchi), deb ataladi. Agar v0 uch G grafning markazi bo‘Isa, u holda e (vn) =mine ( v ) bo‘ladi, ya’ni grafning markaziy uchi minimal U veV ekssentrisitetga egadir. Agar grafning markazidan boshqa biron uchigacha bo‘lgan oddiy zanjir eng uzun masofaga ega bo‘lsa, u holda bu zanjir radial oddiy zanjir, deb ataladi. Tabiiyki, grafning radiusi uning diametridan katta emas va graf bittadan ko‘p markazga ega boMishi ham mumkin. Bundan tashqari, grafning barcha uchlari uning markaziy uchlari bo‘lishi ham mumkin. Grafning markaziy uchlarini topish bilan bog‘liq masalalar aholiga xizmat ko‘rsatadigan qandaydir obyektning (kasalxona, maktab va shu kabilaming) joylashish o‘mini aniqlash bilan bog‘- liq muammolami hal qilishda qo‘llanilishi mumkin.

7.Insidentlik matritsalari

Ta’kidlash kerakki, muayyan vaziyatlarda, ko‘pincha, boshqa holatlami, jumladan, obyektgacha borish vaqti, punktlar orasidagi masofa va shu kabilami hisobga oUshga to‘g‘ri keladi. Bunday vaziyatlarda joylashtirishning minimaks masalalari, deb ataluvchi masalalar vujudga keladi. 1-misol. 1-shaklda tasvirlangan grafni qaraymiz. Bu grafda d (1,6)—2, d {2,1)—3, d(G )—3; (1,4,6,7) va (1,5,6,7) zanjirlar 205 diametral zanjirlardir, (1,3) va (1,3,5,6,7) zanjirlar esa diametral zanjirlar bo‘la olmaydi. Berilgan grafda 4, 5 va 6 belgili uchlar markazlar bo ‘lib, r(G )—2 hamda (6,7) va (6,4,1) radial oddiy zanjirlardir. ■ 6.2. Minimal uzunlikka ega y o ‘l haqidagi masala. Berilgan bog‘lamli grafning har bir qirrasiga (agar berilgan graf oriyentirlangan bo‘lsa — yoyiga) qandaydir haqiqiy son mos qo‘yib, bu sonni qirraning (yoyning) uzunligi, deb ataymiz. Qirraning (yoyning) uzunligi additivlik xossasiga ega deb faraz qilamiz, ya’ni qirralar (yoylar) yordamida tuzilgan zanjiming (yo ‘Ining) uzunligi shu zanjimi (yo‘lni) tashkil etuvchi qirralar (yoylar) uzunliklari yig‘indisiga tengdir. Tabiiyki, qirraning yoki yoyning uzunligi tushunchasi yechilayotgan masalaning mohiyatiga qarab, muayyan bir ma’noga ega bo‘lishi mumkin. Masalan, ikki shahar orasidagi masofa, qandaydir operatsiyani bajarish uchun zarur mablag‘ (xarajatlar) yoki vaqt va boshqalar. Shu nuqtayi nazardan, umuman olganda, bu yerda manfiy uzunlikka ega yoki uzunligi nolga teng qirra (yoy) ham ma’noga ega deb hisoblanadi. Amaliyotda uchraydigan ko‘plab masalalarda marshrut uzunligi maksimallashtirilishi yoki minimallashtirilishi talab etiladi. Shunday masalalardan biriga, aniqrog‘i, kommivoyajer masalasiga Gamilton graflari bilan shug‘ullanganda duch kelgan edik (ushbu bobning 5-paragrafiga qarang). G=(V,U) oriyentirlangan graf berilgan bo‘lsin, bu yerda V={1,2G grafning biron se V uchidan boshqa te. V uchiga boruvchi yo‘llar orasida uzunligi eng kichik bo‘lganini topish masalasi bilan shug‘ullanamiz. Bu masalani minimal uzunlikka ega y o ‘l haqidagi masala, deb ataymiz. Quyida bu masalaning umumlashmasi hisoblangan masalani qarab, uni ham o‘sha nom bilan ataymiz. Grafdagi (i, j) yoyning uzunligini c.. bilan belgilab, C=(c..), / ,y'=l ,m, matritsa berilgan deb hisoblaymiz. Yuqorida ta’kidlaganlarimizga ko‘ra, С matritsaning c.. elementlari orasida manfiylari yoki nolga tenglari ham bo‘lishi mumkin. Agar grafda biron / uchdan chiqib, j uchga kiruvchi yoy mavjud bo‘lmasa, u holda bu yoyning uzunligini cheksiz katta deb qabul qilamiz (c. .= J) yoylar uchun ei +clj>ej tengsizlikning bajarilishini tekshiran1*2- Tekshirilayotgan tengsizlik o‘rinli bo‘lmagan (ya’ni e h >£, +cy. bo‘lgan) barcha j, belgili uchlarning har biriga mos qo‘yilgan esKi £j. Qiymat o'rniga yangi e7 +c(-. qiymatni mos qo‘yamiz va У°Ут 1 Agar grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud ^sa’ u holda grafning qandaydir s uchidan shu siklning biron i uchiga o‘tib> keyin esa sikl bo‘ylab harakatlanib, i uchga istagancha marta qaytish mumkin bo lganligidan, istagancha kichik uzunlikka ega yo‘l tuzish mumkin. 2 Deykstra Edsger Vayb (Dijkstra Wybe, 1930—2002) — goll2nc^ m^tema(igi. 207 ajratamiz. Bunda eski ejt qiymat aniqlangan paytda ajratilgan yoyni ajratilmagan deb hisoblaymiz. Uchlarga qiymat mos qo‘yish jarayonini oxirgi (к belgili) uchga qiymat mos qo‘yilguncha davom ettiramiz. Grafning 1 belgili uchidan (manbadan) chiqib, uning ixtiyoriy к uchigacha (oxirgi uchigacha) eng qisqa yo‘l uzunligi ek bo‘ladi. Oxirgi qadam. Grafning oxirgi uchidan boshlab, ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda uning 1 belgili uchiga kelguncha harakatlanib, natijada grafdagi 1 belgili uchdan ixtiyoriy к uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topamiz. ■ 2-m isol. 2-shaklda tasvirlangan orgrafda o ltita uch (F={1,2,3,4,5,6}) va o‘n bitta yoy bo‘lib, har bir yoy uzunligi uning yoniga yozilgan. Ko‘rinih turibdiki, berilgan grafda manfiy uzunlikka ega (5,3) yoy ham bor. Isbotlash mumkinki, bu grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas. Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni topish bilan shug‘ullanamiz. Dastlabki qadam. Manbaga (1 belgili uchga) £,=() qiymatni mos qo‘yamiz va /?={!} to‘pJamga ega bo‘lamiz. Shuning uchun, i?=F\7?={2,3,4,5,6} bo‘ladi. Umumiy qadam. 1-iteratsiya. R={ 1} va R={ 2,3,4,5,6} bo‘lgani uchun boshlang‘ich uchi R to‘plamga tegishli, oxirgi uchi esa R to‘plam elementi boclgan barcha yoylar to‘plami (R ,R )-{ ( 1,2), (1,3),(1,4)} ga egabo‘lamiz. (R ,R ) to‘plamga tegishlibo‘lgan har bir yoy uchun h ning qiymatlarini topamiz: 208 (1.2) yoy uchun hn—el+ cn=0+2=2; (1.3) yoy uchun A13=e1+c13=0+10=10; (1.4) yoy uchun /г14=е1+с14=0+13=13. Bu hn, hu va hl4 miqdorlar orasida eng kichigi hu bo‘lgani uchun (1,2) yoyni ajratamiz (3-shaklda bu yoy qalin chiziq bilan belgilangan) va 2 belgili uchga e2=2 qiymatni mos qo‘yamiz. Algoritmga ko‘ra 2 uchni R to‘plamdan chiqarib, R to'plamga kiritamiz. Natijada1 7?={1,2} va i?={3,4,5,6} to‘plamlarga ega bo‘lamiz. Ikkala uchi ham R to‘plamga tegishli bo‘lgan bitta (1,2) yoy bo'lgani uchun faqat bitta e,+c12> e2 tengsizlikning bajarilishini tekshirish kifoya. Bu tengsizlik 0+2 > 2 ko‘rinishdagi to‘g‘ri munosabatdan iborat bo‘lgani uchun 2-iteratsiyaga o‘tamiz. 2-iteratsiya. ( R ,R )={( 1,3),(1,4 ),(2,3),(2,5)} bo‘lgani sababli hl3= 10, hu= l3, h2= l va h2 = 11 qiymatlami va min {hn,hu,h23,h25}— —h23=7 ekanligini aniqlaymiz. Bu yerda eng kichik qiymat (2,3) yoyga mos keladi. Shuning uchun, (2,3) yoyni ajratamiz va e= 7 qiymatni 3 belgili uchga mos qo‘yamiz. 3 belgili uchni R to‘plamdan chiqarib, R to^lam ga kiritgandan so‘ng R={ 1,2,3} va i?={4 ,5,6} to‘plamlar hosfl boMadi. Ikkala uchi ham R to'plamga tegishli bo‘lgan uchta (1,2), (1,3) va (2,3) yoylardan birinchisi uchun ex+ cn >e2 tengsizlikning bajarilishi 1-iteratsiyada tekshirilganligi va ep e2 qiymatlaming o‘zgarmaganligi sababli faqat ikkinchi va uchinchi yoylarga mos £j+c13>e3 va e2+c23>£3 munosabatlarni tekshirish kifoya. Bu munosabatlar 0+10 > 7 va 2+5 > 7 ko‘rinishda bajariladi. Shuning uchun 3-iteratsiyaga o'tamiz. 3-iteratsiya. Boshlang‘ich uchi i?={ 1,2,3} to‘plamga tegishli, oxiriesa /?={ 4,5,6} to‘plamga tegishli bo‘lgan yoylar to‘rtta: (1,4), (2,5), (3,4) va (3,5). Shu yoylarga mos Л ning qiymatlari hl4= 13, Л25=11, h3 = 15, Л35=13 va, shuning uchun, min {/г14,/г25,/г34,/г35}= =h2 = 11 bo‘ladi. Demak, bu iteratsiyada (2,5) yoyni ajratamiz va £ = \ 1 deb olamiz. Endi, algoritmga ko‘ra, i?={ 1,2,3,5} va i?={4,6} to‘plamlami hosil qilamiz. 1 Yozuvning ixchamligi nuqtayi nazaridan bu yerda va bundan keyin hosil bo‘lgan to‘plamlar uchun R va R belgilar qoldiriladi. 209 Ikkala uchi ham R to‘plamga tegishli bo‘lgan yoylar oltita: (1,2), (2,3), (1,3), (2,5), (3,5) va (5,3). Bu yoylaming har biri uchun e+ r.> Ej tengsizlikning bajarilishini tekshirishimiz kerak. Lekin, 1- va 2-iteratsiyalarda (1,2), (2,3) va (1,3) yoylar uchun bu ish bajarilganligi sababli tekshirishni tarkibida 5 belgili uch qatnashgan (2,5),.(3,5) va (5,3) yoylar uchun amalga oshirib, quyidagilarga ega bo‘lamiz: (2,5) yoy uchun e2+c2s> e5 munosabat to ‘g‘ri (2 + 9 > ll), (3,5) yoy uchun e3+ c35> e5 m unosabat to ‘g ‘ri (7+6 > 11), lekin (5,3) yoy uchun e5+c53> £3 munosabat noto‘g‘ri (ll+ (—6)=5 £ munosabatning to‘g‘riligi (1,3), (1,4), (2,3), (3,5), (5,3) va (3,4) yoylar uchun tekshirilib ko‘rilganda, uning barcha yoylar uchun bajarilishi ma’lum bo‘ladi. 5-iteratsiya. Endi (R ,R )= {(3 ,6),(4 ,6),(5,6)} bolgani uchun hx = n , \ = 14, /г5б—18 va min{/?36,/i46,/z56} = ^ = 1 4 b o ‘ladi. Bu 210 yerda minimum (4,6) yoyda erishilgani uchun uni ajratib, orgrafning oxirgi 6 belgili uchiga e6= 14 qiymatni mos qo‘yamiz. Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida, algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uch yoydan faqat bittasi ((4,6) yoy) ajratilgan bo‘lgani uchun (4,6) yoy yo‘nalishiga qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili uchga kelamiz. 4 belgili uchga kiruvchi ikkala ((1,4) va (3,4)) yoylar ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yoi yagona emas. Agar harakatni (1,4) yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u holda 4 belgili uchdan 1 belgili uchga kelib, eng qisqa uzunlikka ega yo‘llardan biri bo‘lgan ц=( 1,4,6) marshrutni topamiz. Agarda harakatni (3,4) yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u holda 4 belgili uchdan 3 belgili uchga kelamiz. 3 belgili uchga kiruvchi ikkita yoydan faqat bittasi ((5,3) yoy) ajratilgan bo‘lgani uchun 3 belgili uchdan 5 belgili uchga kelamiz. Shu usulda davom etsak, oldin 2 belgili, keyin esa 1 belgili uchga o‘tib, mumkin bo‘lgan eng flisqa uzunlikka ega bo‘lgan yo‘llardan ikkinchisini, ya’ni j-i2=( 1,2,5,3,4,6) marshrutni aniqlaymiz. Shunday qilib, 2-shaklda tasvirlangan grafda eng qisqa uzunlikka ega va ji2 yo‘llar borligini aniqladik. Bu yo‘llaming har biri minimal e6= 14 uzunlikka ega| ■ Muammoli masala va topshiriqlar 1. 4-shaklda tasvirlangan grafning diametri, radiusi va markaz- (lar)ini toping. 2. Petersen grafming markazini toping. 3. Kyonigsberg ko‘priklari haqidagi ma7 ? ^ salaga mos grafning diametri va markazini toping. 4. Uch uy va uch quduq haqidagi masaIaga mos grafning diametri va radiusini toping. 5. Insidentlik matritsasi quyida berilgan grafning diametri, radiusi va markaz(lar)ini aniqlang: 211 1 1 1 о о о л 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 6. Uchlari to'plamlari kesishmaydigan К3 va 0 4 graflarga birikma amalini qo‘llash natijasida hosil bo‘lgan grafning diametri va radiusini aniqlang. 7. Qirralari qo‘shniligi matritsasi quyida berilgan graflaming radiuslarini aniqlang: a) 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 b) 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 8. Deykstra algoritmini 5-shaklda tasvirlangan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni toping. 9. Siz yashayotgan hududda har bir aholi punktidan boshqasiga bevosita borish mumkin bo‘lgan yo‘llarni va ularning uzunliklarini aniqlang. Bu ma’lumotlarga mos keluvchi graf 212 tuzing va Deykstra algoritmini qo‘llab, o‘zingiz yashayotgan aholi punktidan boshqa aholi punktiga borish mumkin bo‘lgan yo‘llaming eng qisqa uzunlikka ega bo‘lganlarini toping. GRAFLAR NAZARIYASI Ushbu bobda graflar nazariyasi elementlari qaraladi. Dastlab graflar haqida qisqacha tarixiy ma’lumotlar, grafning abstrakt matematik tushuncha sifatidagi ta’rifi va u bilan bog‘liq boshlang‘ich tushunchalar, graflarning geometrik ravishda, maxsus turdagi ko‘phad yordamida, qo‘shnilik va insidentlik matritsalari vositasida berilishi yoritiladi. So‘ngra grafning elementlari ustida sodda amallar, graflami birlashtirish, biriktirish va ko'paytirish amallari, marshrutlar va zanjirlar, grafning bog‘lamliligi tushunchasi, Eyler va Gamilton graflari, graflarda masofa tushunchasi, minimal masofali yo‘l haqidagi masala, daraxt va unga ekvivalent tushunchalar, grafning siklomatik soni bayon qilinadi. Tarmoq tushunchasi, tarmoqdagi oqimlar, maksimal oqim haqidagi masala va bu masalalami hal qilish uchun Ford algoritmi ham ushbu bobda keltiriladi. l-§ . Graflar nazariyasining bosblang‘ich ma’lumotlari Graf, uch, qirra, yoy, yo ‘nalish, orgraf, qo‘shni uchlar, yakkalangan uch, karrali qirralar, multigraf psevdograf nolgraf to ‘la, belgilangan va izomorf graflar, grafning geometrik ifodalanishi, uchlar, qirralar va yoylar insidentligi. 4.1 . Graflar nazariyasi haqida umumiy m a’lumotlar. 1736-yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg1 ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. Kyonigsberg shahridagi Pregel daryosi ustida qurilgan yetti ko‘prikning joylashuvi 1-shakldagi qadimiy xaritada tasvirlangan 1 Kyonisberg (Konigsberg) — bu shahar 1255-yilda asoslangan bo'lib, Sharqiy Prussiyadagi Pregel daryosi qirg‘oqlarida joylashgan. 1946-yildan boshlab, Kaliningrad, hozir Rossiya Federatsiyasi tarkibida. 155 1-shakl. va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqam lar bilan belgilangan. Pregel daryosi K yonigsberg sh ahrini o‘sha davrda to‘rt — А, B, Cva Z)qismgabo‘lgan. Shahaming ixtiyoriy qismida joylashgan uydan chiqib, yetti ko‘prikdan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinm i? K yonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut Eyler sikli nomi bilan yuritiladi, ushbu bobning 5-paragrafiga qarang) mavjudligi shartlari ham topildi. Bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2-shaklda keltirilgan. L. Eyleming bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo'yicha yagona ilmiy ish bo‘lib keldi. XIX asming o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlarG. Kirxgof vaA. Keli2 128 SOiyriO PROBLEM M IS SOLVTIO froblematis AD GEOMETRIAM SITYS P E R T IN E N T 1S. AVC.TORE Leonh. Eulero. § . X. Raeter illam Geometriae partem , qnac circa gWTOr tim es vcrfatur, ct om oi tempore fummo Jludio eft exculta, alterius partis etiamnum admodum iguotae primus mentionem fecit Leibnilzius% quam Geom etriam fitus vocauit. Id a pars ab ipfo in folo firu determinando, fitusque proprietatibus exuendis occupata efle ftatuitur; in quo negotio ncque ad quantitates refpiciendum, nequc calculo quantitamm vretrdum fit. Cuiusmodi autera problemata ad banc fitus Geometriam pert шел a t , et qnali methodo in iis rcfoluendis vti oporte a t, non fatis eftdefinitnm. Q uam obrem , cum nupet problematie cuiusdam mentio effet.fc d a, quod quidem ad .geometriam perdnere *idebatur, ot ita erat comparatum , vt ncque determinationem quantitatum requite re t, ncque folutionem. calculi quantitatum ope admifteret, id *ad geometriam fitus referrc baud dubiuui: praefertim quod in eius folutione .fnlus fitus in confideratiooem veniat, calculus vero nullius prorfus fir ffus. M ethod am ergo meam quam ad buius generis prnbloroata 2-shakl. ishlarida paydo bo'ldi. «Graf» iborasi D. Kyonig3 tomonidan 1936- yilda graflar nazariyasiga bag‘ishlangan dastlabki darslikda4 uchraydi. 1 Kirxgof (KirchhofT Gustav Robert, 1824—1887) — olmon faylasufi, fizigi. 2 Keli yoki Keyli (Cayley Artur, 1821—1895) — ingliz matematigi. 3 Kyonig (Denes Konig, 1884—1944) — venger matematigi. 4 Bu darslik olmon tilida yozilgan. 156 Graflar nazariyasi bo‘yicha tadqiqotlar natijalari inson faoliyatining turli sohalarida qo‘llaniladi. Ulardan ba’zilari quyidagilardir. boshqotirmalami hal qilish; qiziqarli o ‘ymlar; yo‘llar, elektr zanjirlari, integral sxemalari va boshqarish sistemalarini loyihalashtirish; avtom atlar, blok-sxem alar va kompyuter uchun programmalami tadqiq qilish va hokazo. 1.2. Grafning abstrakt ta ’rifi va и bilan bog'liq boshlang‘ich tushunchalar. Awalo, grafning abstrakt matematik tushuncha sifatidagi ta’rifmi va boshqa ba’zi sodda tushunchalami keltiramiz. Vqandaydir bo‘shmas to‘plam bo‘lsin. Uning VjG V va v2e V elementlaridan tuzilgan ko‘rinishdagi barcha juftliklar (kortejlar) to‘plamini ( Vto‘plamning o‘z-o‘ziga Dekart ko‘paytmasini) VxV bilan belgilaymiz. Graf deb shunday < V, U> juftlikka aytiladiki, bu yerda Уф0 va U — ( v , g V, v , g V) ko‘rinishdagi juftliklar korteji1 bo‘lib, Vx V to‘plamning elementlaridan tuzilgandir. Bundan buyon grafni belgilashda yozuv o‘rniga (V, U) yozuvdan foydalanamiz. Grafning tashkil etuvchilarini ko‘rsatish muhim bo'lmasa, u holda uni lotin alifbosining bitta harfi bilan belgilaymiz. G=(V, U) graf berilgan bo‘lsin. V to‘plamning elementlariga G grafning uchlari, V to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. Graflar nazariyasida «uch» iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. Umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. Shuning uchun, bundan keyingi ta ’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz. G = ( V, U) grafning ta ’riflga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin. Agar U bo‘sh bo‘lmasa, u holda bu kortej (a,b ) ( o g V, be V) ko‘rinishdagi juftliklardan2 tashkil topadi, bunda 1 Bundan keyin «juftliklar korteji» iborasi o ‘rniga, qisqacha kortej iborasini qo'llaymiz. 2 Bu yerda ham juftlik (kortej)ning odatdagi yozuvi o ‘rniga (a,b) yozuvidan foydalanamiz. 157 Denes Kyonig a=b bo‘lishi hamda ixtiyoriy (a,b) juftlik U kortejda istalgancha marta qatnashishi mumkin. (a,b)e C/juftlikni tashkil etuvchi a va b uchlaming joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turUcha atash mumkin. Agar {a,b) juftlik uchun uni tashkil etuvchilaming joylashish tartibi ahamiyatsiz, ya’ni (a,b)= —(b,a) bo‘Isa, (a, b) juftlikka y o ‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni (а,Ь)ф(Ь, a) bo‘lsa, u holda (a,b) juftlikka yoy yoki yo ‘naltirilgan (oriyentirlangan) qirra deyiladi. U kortejning tarkibiga qarab, uni yo grafning qirralari korteji yo yoylari korteji, yoki qirralari va yoylari korteji, deb ataymiz. Grafning uchlari va qirra (yoy)lari uning elementlari, deb ataladi. G=(V, U) graf elementlarining soni (|F|+|£/|)ga tengdir, bu yerda G grafning uchlari soni | V\*0 va | Ц bilan uning qirralari (yoylari) soni belgilangan. Grafning qirrasi (yoyi), odatda, uni tashkil etuvchi uchlar yordamida (a,b) yoki ab, yoki (a; b) ko‘rinishda belgilanadi. Boshqa belgilashlar ham ishlatiladi: masalan, yoy uchun (a,b) yoki (a,b), qirra uchun (a,b), yoy yoki qirra uchun и (ya’ni uchlari ko‘rsatilmasdan bitta harf vositasida) ko‘rinishda. Graf yoyi uchun uning chetki uchlarini ko‘rsatish tartibi muhim ekanligini ta’kidlaymiz, ya’ni (a,b) va (b,a) yozuvlar birbiridan farq qiluvchi yoylami ifodalaydi. Agar yoy (a,b) ko‘rinishda ifodalangan bo‘lsa, u holda a uning boshlang‘ich uchi, b esa oxirgi uchi, deb ataladi. Bundan tashqari, yoy (a,b) ko‘rinishda yozilsa, u haqida a uchdan chiquvchi (boshlanuvchi) va b uchga kiruvchi {uchda tugovchi) yoy, deb aytish ham odat tusiga kirgan. Qirra uchun uning (a, b) yozuvidagi harflar joylashish tartibi muhim rol o‘ynamaydi va a va b elementlar qirraning uchlari yoki chetlari, deb ataladi. Agar grafda yo (a,b) qirra, yo (a,b) yoy, yoki (b,a) yoy topilsa, u holda a v a b uchlar tutashtirilgan deyiladi. Agar grafning ikki uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo ‘shni uchlar deb, aks holda esa, qo ‘shni bo ‘Imagan uchlar, deb aytiladi. Grafning ikki uchi qo‘shni bo‘lsa, ular shu uchlami tutashtiruvchi qirraga (yoyga) insident, o‘z navbatida, qirra yoki yoy bu 158 uchlarga insident deyiladi. Grafda ikki qirra (yoy) umumiy chetga ega bo‘lsa, ular qo ‘shni qirralar (yoylar) deyiladi.; Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi. Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni m va qirralar (yoylar) soni n ga qarab belgilanadi va bu holda grafni (m, n) -graf, deb ataydilar. /Agar G=(V,U) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo ‘naltirilmagan (oriyentirlanmagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni yoylardan) tashkil topgan bo‘lsa, u holda u yo ‘naltirilgan (oriyentirlangan) graf, deb ataladi. Oriyentirlangan graf, qisqacha, orgraf, deb ham ataladi. Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko‘rishga to‘g‘ri keladi. Bunday graflar aralash graflar, deb ataladi. Agar G=(V,U) graf (orgraf)ning U korteji tarkibida Vx V to‘plamdan olingan takrorlanuvchi elementlar bo‘lsa, u holda ular karrali yoki parallel qirralar (yoylar), deb ataladi. Karrali qirralari yoki yoylari bo‘lgan graf multigraf deyiladi. Ikkala chetki (boshlang‘ich va oxirgi) uchlari ustma-ust tushgan qirra (yoy), ya’ni grafning (a, a)e U elementi sirtmoq, deb ataladi. Sirtmoq, odatda, yo‘naltirilmagan deb hisoblanadi. Qirralari (yoylari) orasida sirtmoqlari bo‘lgan graf psevdograf deyiladi. Umumiy holda uchlar to‘plami V va (yoki) qirralar (yoylar, qirra va yoylar) korteji U cheksiz ko‘p elementli bo'lishi mumkin. Bundankeyin V to‘plamva U kortej faqat cheklibo‘lgan G —(V,U) graflami qaraymiz. Bunday graflar chekli graflar, deb ataladi. Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan, xolis, yalangbch) uch, deb ataladi. Faqat yakkalangan uchlardan tashkil topgan graf (ya’ni grafda qirralar va yoylar bo‘lmasa) nolgraf yoki bo ‘sh graf, deb ataladi. Uchlari soni m ga teng bo‘lgan bo‘sh grafni Om yoki Nm kabi belgilash qabul qilingan. Istalgan ikki uchi qo‘shni bo‘lgan sirtmoqsiz va karrali qirralarsiz oriyentirlanmagan graf to ‘la graf, deb ataladi. Uchlari soni m ga teng bo‘lgan to‘la graf Km bilan belgilanadi. Ravshanki, Km grafning qirralar soni C2m = bo‘ladi. 159 Agar orgrafning istalgan ikki uchini har bir yo‘nalishda tutashtiruvchi faqat bittadan yoy mavjud bo‘lsa, u holda unga to ‘la orgraf, deb ataladLj Ravshanki, to‘la grafdagi qirralaming har birini ikki (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoyga almashtirilsa, natijada to‘la orgraf hosil bo‘ladi. Shuning uchun, to‘la orgrafdagi yoylar soni oriyentirlanmagan to‘la grafdagi qirralar sonidan ikki baravar ko‘pdir, ya’ni uchlari m ta bo‘lgan tola orgrafdagi yoylar soni 2Cl = m(m-l) bo‘ladi. /Agar grafning uchlariga qandaydir belgilar, masalan, 1,2 sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf, deb ataladi. Agar G=(V,U) va G'=(V', U) graflaming uchlari to‘plamlari, ya’ni V va V' to‘plamlar orasida uchlaming qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik o‘matish mumkin bo‘lsa, u holda G va G' graflar izomorf graflar, deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: agar Vx,ye V va ularga mos bo‘lgan x',y'e V' (x<-^j, x'^ y') uchun xy^x'y' (xye U, x'y'e Щ bo‘lsa, u holda G va G' graflar izomorfdir. Agar izomorf graflardan biri oriyentirlangan bo‘lsa, u holda ikkinchisi ham, albatta, oriyentirlangan bo‘lishi va ulardagi mos yoylaming yo‘nalishlari ham bir-birlariga mos bolishi shart. Graf uchiga insident qirralar soni shu uchning lokal darajasi yoki qisqacha darajasi yoki valentligi, deb ataladi.