|
Xoldarova Mashhuraning
|
| bet | 3/4 | | Sana | 19.05.2024 | | Hajmi | 1,58 Mb. | | #244422 |
Bog'liq Mashxura3-AMALIY MASHG’ULOT
Mavzu: Bog’langan graflarda marshrutlar, ularni narxi(masofasi) bo’yicha baholash.
Ishdan maqsad. Bog’langan graflarda marshrutlar, ularni narxi(masofasi) bo’yicha baholashni o’rganish.
Qo’yilgan masala. Bog’langan graflarda marshrutlar, ularni narxi(masofasi) bo’yicha baholash.
Ish tartibi:
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
Berilgan topshiriqning algoritmini ishlab chiqish;
C++ dasturlash muhitida dasturni yaratish;
Natijalarni tekshirish;
Hisobotni tayyorlash va topshirish.
Graf – bu tugunlar va qirralar (tugunlar juftligini birlashtiruvchi) to’plamidan iborat bo’lgan abstrakt matematik ob’ektdir
Graf — obyektlar toʻplamining grafik koʻrinishi boʻlib, unda baʼzi juft obyektlar linklar orqali bogʻlanadi. Oʻzaro bogʻlangan obyektlar uchlari deb ataladigan nuqtalar bilan ifodalanadi, uchlarini bogʻlaydigan boʻgʻinlar esa qirralar deb nomlanadi. Graflar vaznli va vaznsiz graflarga ajratiladi. Har bir yoyga mos ravishda qandaydir sonli qiymatlar – og’irlik qo’yilgan graflar vaznli graf deb ataladi. Agar yoylarga hech qanday qimatlar qo’yilmagan bo’lsa, bunday graflar vaznsiz graf deyiladi. Umuman olganda graflar nomlari ularning yo’naltirilganligi yoki yo’naltirilmaganligi, hamda ularning vaznli yoki vaznsiz ekanligini anglatadi.
Agar grafning ixtiyoriy ikkita tuguni orasida hech bo’lmaganda bitta yo’l (bog’lovchi yoy) mavjud bo’lsa, bunday graflar bog’langan deyiladi. Agar grafda hech bo’lmaganda birorta tugunlar juftligi bog’lanmagan bo’lsa (ular orasida yo’l bo’lmasa), bunday graflar bog’lanmagan deb ataladi.
Grafning yoylari soni maksimal (mumkin bo’lgan yoylar) soniga yaqin bo’lsa (ya’ni, grafning har bir tuguni ixtiyoriy boshqa tuguni bilan yoy orqali bog’langan bo’lsa), bunday graflar zich (to’liq) graf deb ataladi.
Yuqoridagilarga teskari xususiyatlarga ega bo’lgan graflar, ya’ni yoylar soni kam bo’lgan graflar tarqoq (yoki siyrak) graf deb ataladi.
Ustma –ust tushuvchi tugunlarni bog’lovchi yoy xalqa (petlya) deb ataladi. Boshqacha qilib aytganda xalqa yoy bitta tugundan boshlanib, shu tugunning o’zida yakunlanadi.
Marshrut – bu graf bo’yicha berilgan ketma-ketlikdagi tugunlar dan graf bo’yicha o’tish. Agar tugunlar ketma-ketligining boshlang’ich tuguni v0 va oxiri vk ustma-ust tushsa, ya’ni v0=vk, u holda marshrut yopiq, aks holda marshrut ochiq deyiladi.
Ochiq marshrut: tugunlar 2-4-1-2-3-4-1
Zanjir – grafning ixtiyoriy yoyi ko’pi bilan bir marta kiritilgan marshrut. Agar bunday marshrutning barcha tugunlari takrorlanmasa, u holda zanjir oddiy bo’ladi. Marshrutning boshlang’ich va oxirgi nuqtalari (marshrut oxirlari) bitta tugunda bo’lgan zanjir tsikl deyiladi.
Yopiq marshrut: tugunlar 2-3-5-4-3-2.
Ushbu rasmda grafika umumiy tepaliklar sonining umumiy sonlari matritsasi yordamida namoyish etiladi. Demak, 4 vertikalli grafik 4X4 o'lchamdagi matritsa yordamida tasvirlangan. Ushbu matritsa 1 yoki 0 bilan to'ldirilgan. Bu erda 1 satr vertikalidan ustun tepasiga chekka borligini, 0 esa satr tepasidan ustun vertikaligacha chekka yo'qligini bildiradi.
|
| |
