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

Yo`naltirilmagan grafika

Yo'naltirilmagan grafik - bu grafikning tepalarini bog'laydigan qirralarda yo'nalish bo'lmagan grafik. 1 -rasmda V = {V1, V2, V3} tepaliklar to'plami bilan yo'naltirilmagan grafik tasvirlangan. Yuqoridagi grafikdagi qirralarning to'plami V = {(V1, V2), (V2, V3), (V1, V3)} shaklida yozilishi mumkin. Shuni ham ta'kidlash mumkinki, qirralarning V = {(V2, V1), (V3, V2), (V3, V1)} deb yozilishiga hech narsa to'sqinlik qilmaydi, chunki qirralarning yo'nalishi yo'q. Shuning uchun yo'naltirilmagan grafikdagi qirralar tartibli juftliklar emas. Bu yo'naltirilmagan grafikning asosiy xarakteristikasi. Yo'naltirilmagan grafikalar tepaliklar bilan tasvirlangan ob'ektlar orasidagi nosimmetrik munosabatlarni ifodalash uchun ishlatilishi mumkin. Masalan, shaharlar majmuasini bog'laydigan ikki tomonlama yo'l tarmog'ini yo'naltirilmagan grafik yordamida ko'rsatish mumkin. Shaharlar grafikdagi tepaliklar bilan ifodalanishi mumkin va qirralari shaharlarni bog'laydigan ikki tomonlama yo'llarni ifodalaydi.

Yo'naltirilgan grafiklarni taqdim etish
Algoritmlarni loyihalash kontekstida yo'naltirilgan grafiklarni ifodalash uchun yo'nalishsiz graflar uchun ishlatiladigan qo'shni ro'yxatni ifodalash turi qo'llaniladi. Har bir tugundagi qo'shnilarning bitta ro'yxati o'rniga ikkita ro'yxat mavjud: biri ma'lum bir tugundan qirralar olib boradigan tugunlardan, ikkinchisi - bu tugunga qirralar chiqadigan tugunlardan iborat. Shunday qilib, tugunni ko'rib chiqadigan algoritm yo'naltirilgan chekka bo'ylab bir qadam oldinga siljish paytida erishish mumkin bo'lgan tugunlar va teskari yo'nalishda bir qadam orqaga qaytishda erishish mumkin bo'lgan tugunlar haqida ma'lumot olishi mumkin.va).
Yo'naltirilgan grafikalarda kenglik va chuqurlikni qidirish algoritmlari yo'naltirilmagan grafikalar uchun o'xshash algoritmlardan deyarli farq qilmaydi. Ushbu bo'limda biz bfs bilan shug'ullanamiz. Algoritm s tugunidan boshlanadi, s dan chekka olib boradigan barcha tugunlarning birinchi darajasini aniqlaydi, so'ngra birinchi darajali tugunlardan qirralar olib boradigan barcha tugunlarning ikkinchi darajasini aniqlaydi va hokazo.
D. ushbu yondashuv bilan tugunlar s dan qidiruvni tarqatish jarayonida darajadan keyin aniqlanadi va j darajasi tugunlardan iborat bo'ladi, buning uchun s ning eng qisqa yo'li aniq j qirralarini o'z ichiga oladi. Yo'naltirilmagan grafikda bo'lgani kabi, ushbu algoritm har bir tugun va chekka uchun doimiy ish hajmidan boshqa narsani qilmaydi va Shuning uchun O(m + n) vaqt ichida ishlaydi.
Bfs-ning yo'naltirilgan versiyasi aniq nimani hisoblashini tushunish muhimdir. Yo'naltirilgan grafikalarda s dan t gacha bo'lgan yo'l t dan s gacha bo'lgan yo'l mavjud bo'lmasa ham mavjud bo'lishi mumkin; va bfs ning yo'naltirilgan versiyasi 5 dan t ga yo'l borligi xususiyatiga ega bo'lgan barcha t tugunlarining to'plamini hisoblab chiqadi.
Bunday tugunlardan s ga qaytish yo'llari bo'lishi mumkin yoki bo'lmasligi mumkin.
Chuqurlikni qidirish uchun siz chiziqli vaqt ichida to'ldiradigan va bir xil tugunlarni hisoblaydigan tabiiy o'xshashlik ham mavjud. Bunday holda, grafikni iloji boricha chuqurroq o'rganishga harakat qiladigan rekursiv protsedura ham qo'llaniladi (bu safar faqat tegishli yo'nalishdagi qirralar bo'ylab). DFS tugunda bo'lganda va, u u dan chekka olib boradigan har bir tugun uchun chuqurlikda rekursiv qidiruvni boshlaydi.
Aytaylik, berilgan s tugun uchun siz ko'plab tugunlarni olishingiz kerak, ulardan s ga yo'llar mavjud (s dan yo'llar olib boradigan tugunlar o'rniga). Buni har bir chekka yo'nalishini oddiy o'zgartirish orqali g dan olingan yangi yo'naltirilgan g ^rev grafigini aniqlash orqali osongina amalga oshirish mumkin. Shundan so'ng, bfs yoki DFS algoritmi g ^revga qo'llaniladi; s dan tugunga yo'l g ^Revda mavjud va faqat G dan s ga yo'l mavjud bo'lsa.
Shuni esda tutingki, agar har ikki tugun va va v uchun v dan v gacha va v dan u gacha bo'lgan yo'l mavjud bo'lsa, yo'naltirilgan grafik kuchli bog'langan deb ataladi. ushbu ta'rifga asoslangan xususiyat uchun ba'zi atamalarni shakllantirish ham foydalidir; yo'naltirilgan grafadagi ikkita tugun va va v, agar yo'l mavjud bo'lsa, bir-biriga mos keladi v dan v gacha va v dan i gacha bo'lgan yo'l.
(Shunday qilib, agar undagi har bir juft tugun bir-biriga mos keladigan bo'lsa, grafik kuchli bog'liqdir.)
O'zaro tushunish bir qator foydali xususiyatlarga ega, ularning aksariyati quyidagi oddiy faktdan kelib chiqadi.
(3.16) agar ikkala va v tugunlari bir-biriga mos keladigan bo'lsa va v va w tugunlari bir-biriga mos keladigan bo'lsa, unda ikkala va v tugunlari ham bir-biriga mos keladi.
Isbot. W dan va W gacha bo'lgan yo'lni qurish uchun biz avval v dan v ga o'tamiz (uning mavjudligi o'zaro tushunish va va v bilan kafolatlangan yo'l bo'ylab), keyin v dan v gacha (mavjudligi o'zaro bog'liqlik bilan kafolatlangan yo'l bo'ylab - v va w). W dan yo'lni qurish uchun va xuddi shu fikrlar teskari yo'nalishda qo'llaniladi: biz avval w dan v ga o'tamiz (mavjudligi v va v ning o'zaro bog'liqligi bilan kafolatlangan yo'l bo'ylab), keyin v dan i ga (mavjudligi va va v ning o'zaro bog'liqligi bilan kafolatlangan yo'l bo'ylab).
Yo'naltirilgan grafikning kuchli ulanishini tekshirish uchun (3.16) ga asoslangan chiziqli ish vaqti bilan oddiy algoritm mavjud. Biz har qanday s tugunini tanlaymiz va s dan boshlab G-da ^bfs-ni qidiramiz. Agar ikkita qidiruvdan kamida bittasi barcha tugunlarni topmasa, G juda bog'liq emasligi aniq. Ammo aytaylik, biz s dan har bir boshqa tugunga yo'l borligini va har bir boshqa tugundan s yo'li borligini aniqladik. bunday holda, s va v har bir v uchun bir-biriga tushunarli bo'lib, undan har qanday ikkita tugunning o'zaro bog'liqligi va v: s va bir-biriga tushunarli,s va v bir-biriga tushunarli, va (3.16) dan kelib chiqadiki, v ham bir-biriga tushunarli.
Yo'naltirilmagan grafikalardagi ulanish komponentlariga o'xshab, biz yo'naltirilgan grafik uchun s tugunini o'z ichiga olgan kuchli komponentni s va v bir-biriga mos keladigan barcha v tugunlarning to'plami sifatida aniqlashimiz mumkin. Agar siz o'ylab ko'rsangiz, oldingi xatboshidagi algoritm aslida s ni o'z ichiga olgan kuchli komponentni hisoblab chiqadi: biz BFSNI s dan boshlab G va g ^Revda bajaramiz; ikkala qidiruvda erishilgan tugunlar to'plami s va s yo'llari bo'lgan tugunlar to'plamidir; shuning uchun bu to'plam kuchli kompo-nent, o'z ichiga olgan .