graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi

DOCX 1 sahifa 234,4 KB Bepul yuklash

1 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 234,4 KB

Fayl turi DOCX

Sahifalar 1

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 1

o‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti radio va mobil aloqa fakulteti algoritm va matematik modellashtirish kafedrasi algoritmlarni loyihalash fanidan mustaqil ishi cal_021(810-21) guruh talabasi bajardi:evatov diyorbek. tekshirdi: begimov o`ktam . toshkent – 2023 mavzu: graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi mundarija: 1. kirish 2. graflar haqida . 3. graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi haqida. 4. graflarni eniga va bo’yiga aylanishi. 5. xulosa! 6. foydalanilgan adabiyotlar. kirish eng qisqa masofani aniqlash misolini ko’rib chiqaylik. shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’i berilgan bo’lsin. ba’zi yo’llar bir tomonlama. shahar markazidan har bir viloyatga eng qisqa yo’lni topishimiz zarur. keltirilgan masalani yechishda deykstraning algoritmidan foydalanishimiz mumkin. algoritm graflarga asoslangan bo’lib, u 1959 yil niderlandiyalik olim e. deykstra tomonidan yaratilgan. u grafning bitta uchidan boshqa uchlarigacha eng qisqa masofani aniqlaydi, bunda grafning quvurg’alari manfiy og’irlikka ega bo’lmasligi lozim. bizdan birinchi uchdan qolganlariga …

2 / 1

davrda qiziqarli amaliy masalalardan biri hisoblangan kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi. kyonigsberg shahridagi pregel daryosi ustida qurilgan yettita ko‘priklar joylashuvi 1- shakldagi qadimiy xaritada tasvirlangan va qurilishi tartibida 1, 2, 3, 4, 5, 6 va 7 raqamlar bilan belgilangan. pregel daryosi kyonigsberg shahrini o‘sha davrda to‘rtta , , va qismlarga bo‘lgan. shaharning ixtiyoriy qismida joylashgan uydan chiqib yettita ko‘priklardan faqat bir martadan o‘tib, yana o‘sha uyga qaytib kelish mumkinmi? kyonigsberg ko‘priklari haqidagi bu masalani hal qilish jarayonida graflarda maxsus marshrut (hozirgi vaqtda graflar nazariyasida bu marshrut eyler sikli nomi bilan yuritiladi, mavjudligi shartlari ham topildi. bu natijalar e’lon qilingan tarixiy ilmiy ishning birinchi sahifasi 2- shaklda keltirilgan. l. eylerning bu maqolasi yuz yildan ko‘p vaqt mobaynida graflar nazariyasi bo‘yicha yagona ilmiy ish bo‘lib keldi. xix asrning o‘rtalarida graflar nazariyasi bilan bog‘liq tadqiqotlar g. kirxgof va a. keli ishlarida paydo bo‘ldi. “graf” iborasi …

3 / 1

shunday juftlikka aytiladiki, bu yerda va – (, ) ko‘rinishdagi juftliklar korteji1 bo‘lib, to‘plamning elementlaridan tuzilgandir. bundan buyon grafni belgilashda yozuv o‘rniga yozuvdan foydalanamiz. grafning tashkil etuvchilarini ko‘rsatish muhim bo‘lmasa, u holda uni lotin alifbosining bitta harfi, masalan, bilan belgilaymiz. graf berilgan bo‘lsin. to‘plamning elementlariga grafning uchlari, to‘plamning o‘ziga esa, graf uchlari to‘plami deyiladi. graflar nazariyasida “uch” iborasi o‘rniga, ba’zan, tugun yoki nuqta iborasi ham qo‘llaniladi. umuman olganda, hanuzgacha graflar nazariyasining ba’zi iboralari bo‘yicha umumiy kelishuv qaror topmagan. shuning uchun, bundan keyingi ta’riflarda, imkoniyat boricha, muqobil (alternativ) iboralarni ham keltirishga harakat qilamiz. grafning ta’rifiga ko‘ra, bo‘sh kortej bo‘lishi ham mumkin. agar bo‘sh bo‘lmasa, u holda bu kortej (, ) ko‘rinishdagi juftliklardan2 tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. agar juftlik uchun uni tashkil etuvchilarning joylashish tartibi …

4 / 1

sa, u holda bu kortej (, ) ko‘rinishdagi juftliklardan2 tashkil topadi, bunda bo‘lishi hamda ixtiyoriy juftlik kortejda istalgancha marta qatnashishi mumkin. juftlikni tashkil etuvchi va uchlarning joylashish tartibidan bog‘liq holda, ya’ni yo‘nalishning borligi yoki yo‘qligiga qarab, uni turlicha atash mumkin. agar juftlik uchun uni tashkil etuvchilarning joylashish tartibi ahamiyatsiz, ya’ni bo‘lsa, juftlikka yo‘naltirilmagan (oriyentirlanmagan) qi rra (yoki, qisqacha, qirra) deyiladi. agar bu tartib muhim, ya’ni bo‘lsa, u holda juftlikka yoy yoki yo‘naltirilgan (oriyentirlangan) qirra deyila di. kortejning tarkibiga qarab, uni yo grafning qirralari korteji, yo yoylari korteji, yoki qirralari va yoylari korteji deb ataymiz. agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli graf (bixromatik yoki kyonig grafi) deb ataladi. ta’rifdan ko‘rinib turibdiki, ikki bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita uchlar …

5 / 1

o’tamiz. ishni eng kichik vaznli df tomondan boshlaymiz. boshlang’ich garf v rasmda ifodalangan. navbatda a va v tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga teng bo’lgan tomon qo’shiladi va g rasmda ifodalangan grafga ega bo’lamiz. navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(d va e rasmlar) qo’shib olinadi. natijada qo’shilmagan faqat g tugun qoladi. keyingi qadamda vazni 6 ga teng tomonlarni qayta ishlash kerak bo’ladi. vazni 6 ga teng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. natijada qaysi ikki tomonning qoldirilishiga bo?liq holda j yoki z rasmlarda ifodalangan mod lardan biriga ega bo’lamiz. a) b) v) g) d) e) j) z) quyida ushbu algoritm matnini keltiramiz. bunda e bilan grafdagi tomonlar soni, n bilan tugunlar soni ifoddalangan: edgecount=1 while edgecount dist[u] + chekka uv og'irligi bo'lsa, dist[v] ni yangilang dist[v] = dist[u] + chekka uv og'irligi ushbu bosqich grafikda salbiy og'irlik aylanishi mavjudligi haqida xabar beradi. yana har bir …

Ko'proq o'qimoqchimisiz?

Barcha 1 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi" haqida

o‘zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti radio va mobil aloqa fakulteti algoritm va matematik modellashtirish kafedrasi algoritmlarni loyihalash fanidan mustaqil ishi cal_021(810-21) guruh talabasi bajardi:evatov diyorbek. tekshirdi: begimov o`ktam . toshkent – 2023 mavzu: graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi mundarija: 1. kirish 2. graflar haqida . 3. graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi haqida. 4. graflarni eniga va bo’yiga aylanishi. 5. xulosa! 6. foydalanilgan adabiyotlar. kirish eng qisqa masofani aniqlash misolini ko’rib chiqaylik. shahar viloyatlarini birlashtiruvchi avtomobil yo’llari tarmog’i berilgan bo’lsin. ba’zi yo...

Bu fayl DOCX formatida 1 sahifadan iborat (234,4 KB). "graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflarni eng arzon tayanch qur… DOCX 1 sahifa Bepul yuklash Telegram