Назад

graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi

DOCX 1 стр. 234,4 КБ Бесплатная загрузка

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇
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 …

Хотите читать дальше?

Скачайте все 1 страниц бесплатно через Telegram.

Скачать полный файл

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

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

Этот файл содержит 1 стр. в формате DOCX (234,4 КБ). Чтобы скачать "graflarni eng arzon tayanch qurilishini qurishda kruskal xasis algoritmi", нажмите кнопку Telegram слева.

Теги: graflarni eng arzon tayanch qur… DOCX 1 стр. Бесплатная загрузка Telegram

Похожие файлы

Вам также может понравиться

Показать все
graflarni kompyuter xotirasiga joylashtirish algoritmi — PPTX PPTX
graflarni kompyuter xotirasiga joylashtirish algoritmi
13 стр. 297,2 КБ
graflarni kompyuter xotirasiga joylashtirish algoritmi — DOCX DOCX
graflarni kompyuter xotirasiga joylashtirish algoritmi
25 стр. 1,3 МБ
graflarni tasvirlash usullari va eng qisqa yo‘l algoritmlari — DOCX DOCX
graflarni tasvirlash usullari va eng qisqa yo‘l algoritmlari
6 стр. 17,9 КБ
k-eng yaqin qo'shni (knn) algoritmi — PDF PDF
k-eng yaqin qo'shni (knn) algoritmi
11 стр. 757,2 КБ
klassifikasiya va regressiya algoritmi. k-nearest neighbour eng yaqin qo’shnilar algoritmi — PPTX PPTX
klassifikasiya va regressiya algoritmi. k-nearest neighbour eng yaqin qo’shnilar algoritmi
— 2,6 МБ
graflarni tasvirlash usullari va eng qisqa yo‘lni topish algoritmlari — PPTX PPTX
graflarni tasvirlash usullari va eng qisqa yo‘lni topish algoritmlari
8 стр. 597,8 КБ
k-nn algoritmi mashinali o'qitish uchun eng yaqin qo'shn — PPTX PPTX
k-nn algoritmi mashinali o'qitish uchun eng yaqin qo'shn
15 стр. 4,4 МБ
prim algoritmi. minimal qoldiq daraxtlar. eng qisqa yo’lni topish algoritmlari — PDF PDF
prim algoritmi. minimal qoldiq daraxtlar. eng qisqa yo’lni topish algoritmlari
12 стр. 494,4 КБ