Diskret tuzilmalari

OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Diskret tuzilmalari

Mustaqil ish
Bajardi: Shaylazimov Shaxzod

Toshkent 2022

Mavzu: Yo’nalgan graflar matritsalari, yo’l tushunchasi.

Reja:
1)Yo`naltirilgan graf.

2)Yo`naltirilgan graf uchun qo’shnilik matrisasi.
3)Yonaltirilgan graflarda marshrut, zanjir, sikl.
4)Xulosa.
5)Foydalanilgan adabiyotlar.

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’rifiga ko‘ra, U bo‘sh kortej bo‘lishi ham mumkin. Agar U bo‘sh bo‘lmasa, u holda bu kortej (a,b) ( aV , bV ) ko‘rinishdagi juftliklardan1 tashkil topadi, bunda a  b bo‘lishi hamda ixtiyoriy (a,b) juftlik U kortejda istalgancha marta qatnashishi mumkin.

(a,b)U juftlikni tashkil etuvchi a va b uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. Agar (a,b) juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni (a,b)  (b, a) bo‘lsa, (a,b) juftlikka yo‘naltirilmagan (oriyentirlanmagan) qirra (yoki, qisqacha, qirra) deyiladi. Agar bu tartib muhim, ya’ni (a,b)  (b, a) bo‘lsa, u holda (a,b) juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyiladi.

U kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yoki yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz.
Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi. G  (V,U) graf elementlarining soni ( |V |  |U | )ga tengdir, bu yerda G grafning uchlari soni |V | 0 va |U | 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 u (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 bir-biridan farq qiluvchi yoylarni 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.
1 Bu yerda ham juftlikning (kortejning) odatdagi  a,b  yozuvi o‘rniga (a,b)
yozuvdan foydalanamiz.

Agar grafda yo (a,b) qirra, yo (a,b) yoy, yoki (b, a) yoy topillsa, u holda a va b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni bo‘lmagan uchlar deb aytiladi.

Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlarni tutashtiruvchi qirraga (yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi.
Grafda ikkita 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) grafning (orgrafning) U korteji tarkibida V 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)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. Bundan keyin V to‘plam va U kortej faqat chekli bo‘lgan G  (V,U) graflarni qaraymiz. Bunday graflar chekli graflar deb ataladi.
Hech qanaqa qirra (yoy) bilan bog‘lanmagan uch yakkalangan (ajralgan, xolis, yalong‘och) 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 O_m yoki N_m kabi belgilash qabul qilingan.
Istalgan ikkita uchlari 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 K_m bilan belgilanadi. Ravshanki, K_m grafning qirralar soni bo‘ladi.
Agar orgrafning istalgan ikkita uchini har bir yo‘nalishda tutashtiruvchi faqat bittadan yoy mavjud bo‘lsa, u holda unga to‘la orgraf deb ataladi. Ravshanki, to‘la grafdagi qirralarning har birini ikkita (yo‘nalishlari bir-biriga qarama-qarshi bo‘lgan) yoylarga 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 to‘la orgrafdagi yoylar soni 2C_m² = m(m-1) bo‘ladi.
Agar grafning uchlariga qandaydir belgilar, masalan, 1,2,...,m sonlari mos qo‘yilgan bo‘lsa, u belgilangan graf deb ataladi.
Agar G  (V,U) va G'  (V' ,U') graflarning uchlari to‘plamlari, ya’ni V va V ' to‘plamlar orasida uchlarning qo‘shnilik munosabatini saqlaydigan o‘zaro bir qiymatli moslik o‘rnatish mumkin bo‘lsa, u holda G va G' graflar izomorf graflar deb ataladi. Bu ta’rifni quyidagicha ham ifodalash mumkin: agar  x,yV va ularga mos bo‘lgan x' , y'V' ( x  y , x' y' ) uchun xy  x' y' ( xyU , x' y'U ' ) 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 yoylarning yo‘nalishlari ham bir-birlariga mos bo‘lishlari shart.
Graf uchiga insident qirralar soni shu uchning lokal darajasi, yoki, qisqacha, darajasi, yoki valentligi deb ataladi. Grafdagi a uchning darajasini (a) bilan belgilaymiz.
Sirtmoqqa insident bo‘lgan uchning darajasini aniqlashda shuni e’tiborga olish kerakki, qaralayotgan masalaga bog‘liq holda sirtmoqni bitta qirra deb ham, ikkita qirra deb ham hisoblash mumkin. Ravshanki, ajralgan uchning darajasi nolga teng. Darajasi birga teng uch chetki (yoki osilgan) uch deb ataladi. Chetki (osilgan) uchga insident qirra ham chetki (yoki osilgan) qirra deb ataladi.
Agar grafning barcha uchlari bir xil r darajaga ega bo‘lsa, u holda bunday graf r darajali regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch valentli) graf deb ataladi. O_m graf nol darajali regulyar graf ekanligini, K m esa ( m1 ) darajali regulyar graf ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq o‘rinlidir.
1 - l e m m a (“ko‘rishishlar” haqida).Ixtiyoriyoriyentirlanmagan grafda barcha uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli graf (bixromatik yoki Kyonig grafi) deb ataladi. Ta’rifdan ko‘rinib turibdiki, ikki bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita uchlar qo‘shni bo‘la olmaydi. Biror bo‘lagida faqat bitta uch bo‘lgan to‘la ikki bo‘lakli graf yulduz deb ataladi.
Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo‘shni bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki bo‘lakli grafni Km,n bilan belgilaymiz, bu yerda m va n bilan grafning bo‘laklaridagi uchlar sonlari belgilangan. ( , ) Km,n  V U graf uchun |V | m  n va |U | mn bo‘lishi ravshan, bu yerda |V | – Km,n grafning uchlari soni, |U | – uning qirralari soni.
Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar (Kyonig teoremasi) ushbu bobning 4- paragrafida keltirilgan. Ikkidan katta ixtiyoriy natural k son uchun k bo‘lakli graf tushunchasini ham kiritish mumkin.

1. 
   m i s o l . O‘zbekiston Respublikasi hududidagi aeroportlar to‘plamini V bilan, bu shaharlar orasida belgilangan vaqt mobaynida amalga oshirilayotgan samolyotlarning uchib qo‘nish hodisalari kortejini U bilan belgilaymiz. U holda (V,U) juftlikni graf deb qarash mumkin. Bu yerda grafning uchlariga aeroportlar, yoylariga esa samolyotlarning uchib qo‘nish hodisalari mos keladi. Tabiiyki, (V,U) grafda karrali yoylar bo‘lishi mumkin, agar, qandaydir sababga ko‘ra, samolyot uchgan aeroportga qaytib qo‘nsa, u holda bu hodisaga qaralayotgan grafdagi sirtmoq mos keladi.
   

Graflar ustida amallar graflarni qo`shish.

Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin, masalan, graflarni birlashtirish, biriktirish, ko‘paytirish,grafni qismlarga ajratish va hokazo.
Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini keltirsa bo‘ladi. Bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta element yo‘qotishni (olib tashlashni) anglatadi. Natijada uchlari soni bittaga kamaygan yangi graf hosil bo‘ladi. Albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi.
Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. Bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan birorta element yo‘qotiladi (olib tashlanadi). Berilgan grafdan qirrani (yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish ham mumkin. Bu yerda vaziyatga qarab ish yuritiladi. G  (V,U) va G'  (V' ,U') graflar berilgan bo‘lsin. Agar V V' va G grafning barcha qirralari (yoylari) G' grafning ham qirralari (yoylari), ya’ni U U' bo‘lsa, u holda G graf G' grafning qism grafi deb ataladi.

1. 
   m i s o l . 1- shaklda Petersen grafining (ushbu bobning 2- paragrafidagi 8- shaklga qarang) qism graflaridan biri tasvirlangan. 1- shakl Agar G graf karrali qirralarga ega bo‘lmasa, u holda uchlari G grafning barcha uchlaridan iborat bo‘lgan shunday yagona G graf mavjudki, G grafdagi barcha juft uchlar faqat va faqat G grafda qo‘shni bo‘lmagandagina qo‘shnidir. Bunday G graf berilgan G grafning to‘ldiruvchi grafi deb ataladi.
   

Berilgan graf uchun to‘ldiruvchi grafni qurish jarayonini ham graflar ustida bajariladigan amallar qatoriga kiritish mumkin. G graf uchun to‘ldiruvchi grafni qurish amalini qo‘llash natijasida G graf hosil bo‘ladi. Isbotlash mumkinki, G  G munosabat o‘rinlidir.

2. 
   m i s o l . 2- shaklda tasvirlangan graf 1- shaklda ifodalangan graf uchun to‘ldiruvchi grafdir. Graflar ustida shunday amallarni bajarish mumkinki, ular elementlari soni berilgan grafdagidan ko‘proq bo‘lgan boshqa graflarning hosil bo‘lishiga olib keladi. Bunday amallar qatoriga uchni qo‘shish amali yoki qirrani (yoyni) qo‘shish amalini kiritish mumkin. Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin. Masalan, yangi v uchni berilgan grafga qo‘shish shu grafning v1 va v2 uchlariga insident bo‘lgan qandaydir u qirrasiga qo‘shish orqali quyidagicha ikki bosqichda bajarilishi mumkin: 1) u qirra berilgan grafdan olib tashlanadi;
   

2) hosil bo‘lgan grafga ikkita yangi qirralar: v va v1 uchlarga insident u1 qirra hamda v va v2 uchlarga insident u2 qirra qo‘shiladi.
Bu jarayon grafda qirraga darajasi 2 bo‘lgan yangi uchni qo‘shish (kiritish) yoki qirrani ikkiga bo‘lishamali deb ataladi.
Agar G graf G' grafdan qirrani ikkiga bo‘lish amalini chekli marta ketma-ket qo‘llash vositasida hosil qilingan bo‘lsa, u holda G graf G' grafning bo‘linish grafi deb ataladi.
Bo‘linish graflari izomorf bo‘lgan graflar gomeomorf graflar deb ataladi.

3. 
   shaklda tasvirlangan graflar izomorf emas, lekin ular gomeomorf, chunki bu graflarning har
   

biri 4- shaklda tasvirlangan bo‘linish grafiga ega. 3.2. Graflarni birlashtirish. ( , ) G1  V1 U1 va ( , ) G2  V2 U2 graflar berilgan bo‘lsin. Uchlari to‘plami V V1 V2 va qirralari (yoylari) korteji U U1 U2 kabi aniqlangan2 G  (V,U) graf G1 va G2 graflarning birlashmasi (uyushmasi) deb ataladi va G  G1 G2 ko‘rinishda belgilanadi.
5-misol shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 graflarning birlashmasi amali tasvirlangan
m i s o l . Uchlari to‘plamlari kesishadigan graflarning birlashmasi amali 6- shaklda tasvirlangan. Agar birlashtirilayotgan graflarning uchlari to‘plamlari kesishmasa, u holda bu graflarning birlashmasi diz’yunkt birlashma deb ataladi.
Masalan, 5- shaklda tasvirlangan

birlashma diz’yunkt, 6- shakldagi birlashma esa – diz’yunkt emas.
3.3. Graflarni biriktirish. ( , ) G1  V1 U1 va ( , ) G2  V2 U2 graflar berilgan bo‘lsin. G1 va G2 graflar birlashtirilishi hamda G1 grafning har bir uchi G2 grafning har bir uchi bilan qirra vositasida tutashtirilishi natijasida hosil bo‘lgan G  (V,U) graf G1 va G2 graflarning birikmasi (tutashmasi) deb ataladi va G  G1 G2 ko‘rinishda belgilanadi.
5- m i s o l . Uchta uy va uchta quduq haqidagi boshqotirma masalaga mos graf (ushbu bobning 2- paragrafidagi 9- shaklga qarang) uchlari to‘plamlari kesishmaydigan ikkita ( O3 ) nolgraflarning birikmasidir.
6- m i s o l . 7- shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 graflarning birikmasi amali tasvirlangan.
Agar uchlari to‘plamlari kesishmasi bo‘sh bo‘lmagan graflarni biriktirish zarur bo‘lsa, u holda hal qilinayotgan masala xossalarini e’tiborga olib ish ko‘rish kerakligini ta’kidlaymiz.
3.4. Graflarni ko‘paytirish. ( , ) G1  V1 U1 va ( , ) G2  V2 U2 graflar berilgan bo‘lsin. Uchlari to‘plami V V1 V2 bo‘lgan G  (V,U) grafning qirralari (yoylari) kortejini quyidagicha aniqlaymiz: agar ' '' 1 1 v  v va 2 2 2 (v ' ,v '')U yoki ' '' v2  v2 va 1 1 1 (v ' ,v '')U bo‘lsa, u holda (v' ,v'')U bo‘ladi, bu yerda 1 1 1 v ' ,v ''V , 2 2 2 v ' ,v ''V , v'  (v1 ' ,v2 ')V va v''  (v1 '' ,v2 '')V .
Bu yerda birlashma “  ” amali V ning to‘plam, U ning esa kortej ekanligini e’tiborga olgan holda amalga oshiriladi.
shakl 1 2 3 4 5 1 2 3 4 5 K2 K3 K2  K3 6- shakl 1 2 3 4 5 1 2 3 4 5 4 3 Shunday usul bilan hosol qurilgan G  (V,U) graf G₁ va G₂ graflarning ko‘paytmasi deb ataladi va G  G₁ G₂ kabi belgilanadi.

Graflarning ko‘paytmasi ta’rifiga asosan berilgan ( , ) G1  V1 U1 va ( , ) G2  V2 U2 graflarning ko‘paytmasi hisoblangan G grafdagi:
– uchlar ( , ) v1 v2 yoki ( , ) v2 v1 ko‘rinishdagi juftliklardan iboratdir, bu yerda 1 V1 v  , v2 V2 ;
– v'  (v1 ' ,v2 ')V va v''  (v1 '' ,v2 '')V uchlar faqat va faqat shu holda qo‘shni bo‘ladilarki, qachonki bu uchlarni (juftliklarni) tashkil qiluvchi elementlarning biri unga mos element bilan ustma-ust tushgan holda boshqa elementlar o‘z grafida qo‘shni bo‘lishsa, bu yerda 1 1 1 v ' ,v ''V , 2 2 2 v ' ,v ''V ;
– 1 1 |V | m , 2 2 |V | m , 1 1 |U | n va 2 2 |U | n munosabatlardan 1 2 |V | mm va 1 2 2 1 |U | m n  m n bo‘lishi kelib chiqadi.
7- m i s o l . 8- shaklda uchlari to‘plamlari kesishmaydigan K2 va K3 graflarning ko‘paytmasi

amali tasvirlangan.
Dekart ko‘paytmalar bilan bog‘liq tuzilmalar ustida bajariladigan amallar boshqalaridan o‘ziga xosligi bilan ajralib turadi. Bu o‘ziga xoslik graflarni ko‘paytirish amalida namoyon bo‘ladi. Aniqrog‘i, graflar ko‘patmasida qatnashgan birorta grafning qirralari korteji bo‘sh bo‘lsada, ko‘paytirish amalini qo‘llash natijasida hosil bo‘lgan grafning qirralari korteji bo‘sh bo‘lmasligi ham mumkin. Haqiqatdan ham, yuqorida keltirilgan graflarning ko‘paytmasi ta’rifidan kelib chiqadiki, agar G  (V,U) graf ( , ) G1  V1 U1 va ( , ) G2  V2 U2 graflarning ko‘paytmasi, ya’ni, G  G1 G2 bo‘lsa, u holda V V1 V2 bo‘ladi va U kortej elementlari bilan ( ) ( ) V1U2  U1V2 birlashma elementlari orasida o‘zaro bir qiymatli moslik mavjud. Shuning uchun, agar, masalan, U1   , U2   bo‘lsa, u holda (V1 U2 )(U1 V2 ) V1 U2   bo‘ladi, chunki grafning tarifiga ko‘ra V1   . Demak, U  , ya’ni G1 bo‘sh graf bo‘lsada, G  G₁ G₂ bo‘sh bo‘lmagan grafdir.
Graflarni ko‘paytirish amalini takror qo‘llash usuli bilan graflar nazariyasining muhim sinfini tashkil etuvchi n o‘lchovli kublarni aniqlash mumkin. N o‘lchovli kub ( Q_n ) uchlari soni ikkiga teng bo‘lgan to‘la graf K2 yordamida quyidagi rekurrent formula bilan aniqlanadi:
Q₁  K₂ , Q_n  K₂ Q_n-1 .
Yuqorida graflar ustidagi ba’zi amallar haqida qisqacha ma’lumot berildi. Shuni ta’kidlash lozimki, graflar ustida bundan boshqa bir qator amallar ham bor.