|
Algoritmlarni loyihalash fanidan mustaqil ishi
|
| bet | 4/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MIInsidentlik 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.
Graflar insidentlik matritsasini nxm oʻlchamdagi B=[bi,j] toʻrtburchaklar matritsasi sifatida aniqlaylik, bunda bi,j elementi 1 ga teng, agar ej insident qirraning vj uchi boʻlsa, aks holda 0 boʻladi. B matritsasining satrlari insidentlik vektorlari deb nomlanadi va Bi bilan belgilanadi.
7-rasm. Grafda insidentlik matritsasi
Bogʻlanmagan grafning insidentlik matritsasi, xuddi qoʻshnilik matritsasi singari, blok-diagonali koʻrinishga keltirilishi mumkin, bu yerda har bir diogonal blok ba‘zi bir bogʻlangan komponentlarning insidentlik matritsasi hisoblanadi.
Grafda parallel qirralar boʻlmaganligi sababli, agar vi va vj uchlar qoʻshni boʻlsa, har qanday BiBj insidentlik vektorlari jufligi skalar koʻpaytmasi birga teng boʻladi va agar bu uchlar qoʻshni boʻlmasa, skalar koʻpaytma nolga teng boʻladi. Binobarin, BBT koʻpaytma graflarning qoʻshnilik matritsasiga toʻgʻri keladigan mos darajalariga teng boʻlgan diagonal elementlar bundan mustasno.
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.
8-rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi
9-rasm. Orgrafda insidentlik matritsasi
Grafda oʻtish algoritmlari Graflar bilan ishlashda barcha asosiy amallar (masalan, grafni bitta koʻrinishda ikkinchisiga oʻtkazish, bosib chiqarish yoki grafni chizish) uning tizimli oʻtishini, ya‘ni grafning har bir uchiga va har bir qirrasiga tashrif buyurishni nazarda tutadi. Agar labirintni graf koʻrinishida namoyish etsak, u yerda qirralar oʻtish joylari, uchlar esa qirralarning kesishish nuqtalari boʻlsa, u holda grafni bosib oʻtish uchun har qanday toʻgʻri algoritm ixtiyoriy ravishda labirintidan chiqish yoʻlini topishi kerak. Ushbu algoritmlarning eng mashhurlari grafda oʻtish boʻyi boʻyicha qidiruv (DFS) va oʻtish eni boʻyicha qidiruv (BFS) algoritmlari boʻlib, ular qoʻllaniladigan muammolarni hal qilish uchun koʻplab boshqa algoritmlar uchun asos boʻlib xizmat qiladi.
Graflar boʻylab harakatlanishning asosiy gʻoyasi shundaki, har bir uchni birinchi marta tashrif buyurganingizda belgilang va barcha qirralari koʻrib chiqilmagan uchlar haqidagi ma‘lumotlarni saqlang. Qadimgi Yunoniston afsonalarida Tesey labirint atrofida yurish uchun Ariadna bergan ipdan foydalangan, qarichlab tosh yoki maydalangan toshlar bilan bosib oʻtgan yoʻlini belgilab qoʻygan, sanab oʻtilgan turlar grafni bosib oʻtish uchun ishlatilgan. Grafni bosib oʻtish jarayonida har bir uch uchta holatdan birida boʻladi:
1) ochilmagan - uchning dastlabki holati;
2) ochiq - uch topilgan, ammo unga tushgan qirralar koʻrib chiqilmagan;
3) ishlov berilgan (belgilangan) - ushbu uchga tushgan barcha qirralarga tashrif buyuriladi.
Grafning har bir uchi ketma-ket ushbu holatlarning barchasini qabul qilishi aniq. Dastlab, faqat bitta uch ochiq boʻladi, ya‘ni grafni bosib oʻtish ushbu uchdan boshlanadi.
|
| |
