Samarqand davlat universiteti raqamli texnologiyalar fakulteti dasturiy injiniring yo



Download 1,33 Mb.
bet2/6
Sana26.02.2022
Hajmi1,33 Mb.
#471865
1   2   3   4   5   6
Bog'liq
kurs ishi namuna

Qo’shnilik matritsasi. 1 dan n gacha raqamlangan G grafning qo'shnilik matritsasi kvadrat kattalikdagi A matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. Bunday matritsa binar matritsa deb ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi.
Qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. Yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.
Qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. Ushbu kattalik qo'shnilik ro'yxatlariga qaraganda yaxshiroq (pastga qarang).

3-rasm. Yo’naltirilmagan grafda qo’shnilik matritsasi

4-rasm. Orgrafda qo’shnilik matritsasi

Qo'shnilik matritsasini amalga oshirish uchun massivlar massivi qo'llaniladi: vektorlar vektori (vector>) yoki kaliti uchlar soni, qiymati esa vektori. Agar grafni kengaytirish kerak bo'lmasa, u holda vektorni array (massiv) bilan almashtirish kerak.


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 :

  1. Kruskal algoritmi

  2. Prima algoritimi

  3. Boruvka algoritmi

  4. 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



Download 1,33 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish