|
Insidentlik matritsasi. Insidentlik matritsasi - bu grafning elementlari (qirra - uch) orasidagi bog'lanishlar ko'rsatiladigan grafni tasvirlash shakli. Matritsaning ustunlari qirralarga, satrlar uchlarga to'g'ri keladi. Demak, matritsa kvadrat bo‘lmaydi. Matritsa yacheykasidagi nolga teng bo'lmagan qiymat uch va qirra (ularning insidentligi) o'rtasidagi munosabatni bildiradi.
Yo'naltirilgan graf holatida tegishli ustundagi har bir uch chiquvchi x vertikal qatorida "−1" va kiruvchi y uch qatorida "1" qiymatiga ega; agar uch va qirra o'rtasida hech qanday bog'liqlik bo'lmasa, unda mos keladigan katak "0" qiymatiga ega bo‘ladi.
5-rasm. Yo’naltirilmagan grafda insidentlik matritsasi
6-rasm. Orgrafda insidentlik matritsasi
Qo’shnilik ro'yxati. Qo’shnilik ro'yxati - bu grafni uchlar ro'yxati ("ro'yxatlar ro'yxati") to'plami sifatida ko'rsatish usuli - grafning har bir uchi qo'shni uchlar ro'yxatiga to'g'ri keladi. Masalan, 1-rasmni biz quyidagi qo'shnilik ro'yxati bilan tavsiflashimiz mumkin:
7-rasm qo’shnilik ro‘yxati
Bu sodda graflarni aks ettirish uchun ham, grafni kenglik yoki chuqurlikda bosib o'tish uchun asosiy algoritmlarni amalga oshirish uchun ham eng qulay usuldir, bu yerda siz hozirda ko'rib chiqilgan uchning "qo'shnilarini" tezda olishingiz kerak.
Graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari
Eng kichik uzunlikdagi daraxt – berilgan grafning eng kam og’irlikka ega bo’lgan daraxti, bu yerda daraxtning vazni uning qirralari og’irliklari yig’indsi sifatida tushuniladi.
Misol. Minimal uzunlikdagi daraxtni toppish muammosi ko’pincha xuddi shunday sharoitda uchraydi: masalan, har qanday shaharda boshqasiga (to’g’ridan –to’g’ri yoki boshqa shahar orqali) o’tish uchun n ta shaharni yo’llar bilan bog’lash kerak . Berilgan juft shaharlar o’rtasida yo’llar qurisha ruxsat beriladi va har bir bunday yo’lni qurish qiymati ma’lum. Qurishning umumiy narxini minimallashtirish uchun qaysi yollarni qurish kerakligini hal qilish talab etiladi.
Ushbu muammoni grafika nazariyasi nuqtai nazardan shakillantirish munkin. Bu yerda berilgan grafning uchlari shaharlarni, qirralari esa to’g’ri yo’l qurishi munkin bo’lgan va qirralarining og’rliklari teng bo’lgan shaharlarni ifodalaydigan minimal daraxtni toppish muammosidir.
8
-rasm.Eng kichik uzunlikka ega bo’lgan daraxt
Minimal uzunlikdagi daraxtlarni toppish uchun bir nechta algoritmlar mavjud. Eng mashhur algoritmlar quydadilar :
Kruskal algoritmi
Prima algoritimi
Boruvka algoritmi
Orqadan o’chirish algoritmi
Kruskal algoritmi birlashtirilgan Kruskal kamaymaydigan chekka og'irliklariga muvofiq tartiblangan. Bundan tashqari, girralar og'irligi kichikrog bo'lgan girralardan yuqori tomonga siljiydi va keyingi chekka ilgari tanlangan girralar bilan sikl hosil gilmasa, karkasga go'shiladi. Xususan, grafdagi minimal og'irlikdagi girralaridan biri har doim birinchi bo'lib tanlanadi.
Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz grafni bir nechta bog'langan komponentlarning birlashishi sifatida namoyish etamiz. Eng boshida, grafining chekkalari tanlanmaganida, har bir uch alohida bog'langan komponent hisoblanadi, Yangi qirralar go'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti bo'lguncha birlashadi. Barcha bog'langan tarkibiy gismlarni ragamlaymiz va har bir uch uchun uning ulangan gismlarini sonini saglaymiz, shuning uchun har bir uch uchun boshida uning bog'langan komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha uchlar bir- biriga bog'langan komponentning bir xil raqamlariga tegishli bo'ladi.
Keyingi qirrani ko'rib chiqayotganda, ushbu girraning uchlariga to'g'ri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz. Agar bu ragamlar bir xil bo'lsa, unda qirra allaqachon bir xil bog'langan komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu girrani qo'shish siklni tashkil giladi. Agar girra ikki xil bogʻlangan komponentni, masalan, a va b raqamlari bilan bog'lasa, u holda girra asosiy daraxtning bir gismiga go'shiladi va bu ikkita bogʻlangan komponentlar birlashtiriladi. Buning uchun, komponentida bo'lgan barcha uchlar uchun komponent ragamini a ga oʻzgartirish kerak.
2-qadam.
9-rasm.Algoritm bajarilsh ketma ketligining 1-2-qamlari
3-qadam.
10-rasm.Algoritm bajarilsh ketma ketligining 3-4-qamlari
Do'stlaringiz bilan baham: |
