prim algoritmlari. minimal qoldiq. eng qisqa yo`lni topish algoritmlari. ford-belman algoritmlari.

PPTX 42 стр. 5,2 МБ Бесплатная загрузка

42 стр.

FaylHub.uz

Скачать через Telegram

Размер 5,2 МБ

Тип файла PPTX

Страницы 42

Обновлено Дек 2025

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

Прокрутите вниз 👇

1 / 42

grafi mavzu: prim algoritmlari. minimal qoldiq. eng qisqa yo'lni topish algoritmlari. ford-bellman algoritmi. reja bog'langan graflar siklomatik son haqida tushuncha prim algoritmlari ford-bellman algoritmi savol va topshiriqlar prim algoritmi haqida prim algoritmi - murakkab bog'langan yo'naltirilmagan grafikning minimal oraliq daraxtini qurish algoritmidir. algoritm birinchi marta 1930 yilda chex matematigi voytsex jarnik tomonidan kashf etilgan, keyinchalik robert prim tomonidan 1957 yilda va 1959 yilda e. diykstralar tomonidan kashf etilgan. prim algoritmini ishlash prinsipi: algoritmning kirish qismiga bog'langan yo'naltirilmagan graf beriladi. birinchidan, ixtiyoriy uch olinadi va bu uchga tushadigan va eng kam xarajatga ega bo'lgan yo`l topiladi. topilgan yo`l va u bilan bog'langan ikkita uch daraxtni hosil qiladi. keyin, grafikning qirralari ko'rib chiqiladi, ularning bir uchi allaqachon daraxtga tegishli uch, ikkinchisi esa yo'q; bu qirralardan eng kam xarajat yo`li tanlanadi. har bir qadamda tanlangan yo`l daraxtga qo'shiladi. daraxt dastlabki grafikning barcha uchlari tugamaguncha o'sadi. algoritmning natijasi minimal xarajatli yo`llarni qamrab oluvchi daraxtdir. …

2 / 42

bir uchi boshqasining qo`shnisi bo'lgan sikllarni o'z ichiga olgan g asl grafigining uchlarini o'z ichiga olgan pastki grafik. grafiklar nazariyasining asosiy tushunchalari siklomatik raqam tsiklomatik raqam r grafikdan qancha qirralarni olib tashlash kerakligini ko'rsatadi, shunda unda sikllar qolmaydi. z = m - n + 1 , m - qirralar soni n - uchlari soni vazifa 1 ba'zi hududlarda besh daraxtli gaz quvurini qurishga qaror qilindi. galaosiyodan sheyxonchagacha 10 km yo'l bosib o'tdi, galaosiyodan rabotakgacha - 3 km, sheyxonchadan romitangacha - 6 km, romitandan buxorogacha - 12 km, rabotakdan sheyxonchagacha - 11 km, buxorodan galaosiyogacha - 5 km, sheyxonchagacha - 7 km. quvurni qanday qilib yotqizish kerak, shunda u barcha beshta daraxtni bog'laydi va shu bilan birga xarajatlar minimal bo'ladi? vazifa 1 keling, grafik, modellash daraxti, kenglikdagi daraxtni quraylik. buxoro galaosiyo rabotak sheyxoncha romitan 12 7 10 11 3 6 5 vazifa 1 muammo minimal murakkablikdagi daraxtni qurish bilan bog'liq. biz …

3 / 42

3 0 0 0 4 6 0 0 0 12 5 7 5 0 12 0 3 3 1 2 3 4 5 1 0 10 11 6 7 2 3 3 4 6 0 0 0 12 5 7 5 0 12 0 1 2 3 4 5 1 0 10 11 6 7 2 10 0 3 0 5 3 11 3 0 0 0 4 6 0 0 0 12 5 7 5 0 12 0 1 2 3 4 5 1 0 10 11 6 7 2 3 3 4 6 0 0 0 12 5 7 5 0 12 0 vazifa 1 jadvalning 2 va 3-qatorlarini kesib tashlang. 2 va 3-ustunlar ajratilgan. tanlangan ustunlardagi minimal elementni topamiz. 5 1 2 3 4 5 1 0 10 11 6 7 2 3 3 4 6 0 0 0 12 5 7 5 0 12 0 1 …

4 / 42

'langan kichik to'plamga birlashtiriladi; b) tugunlarning biri bog'langan kichik bo'limga tegishli bo'lsa, ikkinchisi yo'q, keyin ikkinchisini birinchisiga tegishli bo'lgan kichik to'plamga kiritamiz; c) turli bog'langan kichik to'plamlarga tegishli tugunlar bo'lsin , keyin biz kichik to'plamlarni birlashtiramiz; g) ikkala cho'qqi ham bir xil bog'langan kichik to'plamga tegishli bo'lsa, biz bu chetni istisno qilamiz. algoritm barcha uchlari bitta to'plamga birlashtirilganda tugaydi. vazifa 2 turistik marshrutning minimal uzunligi kruskal algoritmi bilan aniqlanadi. 1 6 5 2 3 4 25 18 15 12 20 23 21 19 26 vazifa 2 biz faqat ajratilgan tugunlarni o'z ichiga olgan kengaytmali subgraf quramiz. 1 6 5 2 3 4 25 18 15 12 20 23 21 19 26 biz oltita bitta elementli iskala olamiz. vazifa 2 minimal og'irlik qirrasini toping va uni oraliq pastki grafaga qo'shing. 1 6 5 2 3 4 25 18 15 12 20 23 21 19 26 5 , v 6 } uchlarning …

5 / 42

lgan qirralarning grafikga kiritilmasligi kerak, chunki barcha ix tugunlari bir xil bog'langan to'plamga tegishli. 1 6 5 2 3 4 25 18 15 12 20 23 21 19 26 ulangan daraxtning minimal og'irligi 85 ga teng edi . vazifa 3 qurilish uchastkasi yo'q, ular telefon, barcha almashtirish uylarini ulashadi. telefon liniyalari qurilishga xalaqit bermasligi uchun ix yo'l bo'ylab yugurishga qaror qildi. grafning ko`rinishi diagrammada ko'rsatilgan. umumiy uzunligi minimal bo'lishi uchun telefon liniyasini yaratishning eng yaxshi usuli qanday? 260 240 180 210 100 100 150 200 380 1 6 5 2 3 4 7 170 210 100 100 150 200 1 6 5 2 3 4 7 170 telefon liniyasining umumiy uzunligi 930 metrni tashkil qiladi. "javob" yozuvi topshiriqning javobini avtomatik ravishda qaytarish uchun tetikdir 33 ford-bellman algoritmi ushbu algoritm og'irlikli grafikda bir cho'qqidan qolgan barcha nuqtalargacha bo'lgan eng qisqa masofalarni, agar grafik qo'shni matritsa bilan berilgan bo'lsa, o(n3) vaqtida yoki …

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

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

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

О "prim algoritmlari. minimal qoldiq. eng qisqa yo`lni topish algoritmlari. ford-belman algoritmlari."

grafi mavzu: prim algoritmlari. minimal qoldiq. eng qisqa yo'lni topish algoritmlari. ford-bellman algoritmi. reja bog'langan graflar siklomatik son haqida tushuncha prim algoritmlari ford-bellman algoritmi savol va topshiriqlar prim algoritmi haqida prim algoritmi - murakkab bog'langan yo'naltirilmagan grafikning minimal oraliq daraxtini qurish algoritmidir. algoritm birinchi marta 1930 yilda chex matematigi voytsex jarnik tomonidan kashf etilgan, keyinchalik robert prim tomonidan 1957 yilda va 1959 yilda e. diykstralar tomonidan kashf etilgan. prim algoritmini ishlash prinsipi: algoritmning kirish qismiga bog'langan yo'naltirilmagan graf beriladi. birinchidan, ixtiyoriy uch olinadi va bu uchga tushadigan va eng kam xarajatga ega bo'lgan yo`l topiladi. topilgan yo`l va u bilan bog'langan ...

Этот файл содержит 42 стр. в формате PPTX (5,2 МБ). Чтобы скачать "prim algoritmlari. minimal qoldiq. eng qisqa yo`lni topish algoritmlari. ford-belman algoritmlari.", нажмите кнопку Telegram слева.

Теги: prim algoritmlari. minimal qold… PPTX 42 стр. Бесплатная загрузка Telegram