graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari

DOCX 10 sahifa 376,3 KB Bepul yuklash

10 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 376,3 KB

Fayl turi DOCX

Sahifalar 10

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 10

7-ma’ruza graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari. eng kichik uzunlikdagi daraxt – berilgan grafning eng kam og'irlikka ega bo’lgan daraxti, bu yerda daraxtning vazni uning qirralari og'irliklari yig'indisi sifatida tushuniladi. misol. minimal uzunlikdagi daraxtni topish muammosi ko'pincha xuddi shunday sharoitda uchraydi: masalan, har qanday shahardan boshqasiga (to'g'ridan-to'g'ri yoki boshqa shaharlar orqali) o'tish uchun n ta shaharlarni yo'llar bilan bog'lash kerak. berilgan juft shaharlar o'rtasida yo'llar qurishga ruxsat beriladi va har bir bunday yo'lni qurish qiymati ma'lum. qurilishning umumiy narxini minimallashtirish uchun qaysi yo'llarni qurish kerakligini hal qilish talab qilinadi. ushbu muammoni grafika nazariyasi nuqtai nazaridan shakllantirish mumkin. bu yerda berilgan grafnin uchlari shaharlarni, qirralari esa to'g'ri yo'l qurilishi mumkin bo'lgan va qirralarning og'irliklari teng bo'lgan shaharlarni ifodalaydigan minimal daraxtini topish muammosidir. 1-rasm. eng kichik uzunlikka ega bo’lgan daraxt minimal uzunlikdagi daraxtni topish uchun bir nechta algoritmlar mavjud. eng mashhurlari quyida keltirilgan: 1) prima algoritmi; 2) kruskal algoritmi; 3) boruvka …

2 / 10

a, ulanish komponentlari bitta umumiy ulanish komponenti bo'lguncha birlashadi. barcha bog'langan tarkibiy qismlarni raqamlaymiz va har bir uch uchun uning ulangan qismlarini sonini saqlaymiz, shuning uchun har bir uch uchun boshida uning bog'langan komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha uchlar bir-biriga bog'langan komponentning bir xil raqamlariga tegishli bo'ladi. keyingi qirrani ko'rib chiqayotganda, ushbu qirraning uchlariga to'g'ri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz. agar bu raqamlar bir xil bo'lsa, unda qirra allaqachon bir xil bog'langan komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu qirrani qo'shish siklni tashkil qiladi. agar qirra ikki xil bog'langan komponentni, masalan, va raqamlari bilan bog'lasa, u holda qirra asosiy daraxtning bir qismiga qo'shiladi va bu ikkita bog'langan komponentlar birlashtiriladi. buning uchun, masalan, ilgari komponentida bo'lgan barcha uchlar uchun komponent raqamini ga o'zgartirish kerak. quyidagi rasmda minimal uzunlikka kiritilgan qirralar qizil rang bilan, qora rang bilan esa nomzodlar ulardan eng kam og'irlikdagi qirra tanlangan. …

3 / 10

$tish int g[v][v] = { {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0} }; int main () { int no_edge; // qirralar soni // tanlangan uchni kuzatish uchun massiv yaratish int selected[v]; // dastlab false qiymatini berish memset (selected, false, sizeof (selected)); // qiralar soniga 0 ni berish no_edge = 0; selected[0] = true; int x; // qator raqami int y; // ustun raqami // qirra va og'irlikni chop etish cout g[i][j]) { min = g[i][j]; x = i; y = j; } } } } } cout > n >> m; vector > edges(m, vector (3)); for (int i = 0; i > edges[i][1] >> edges[i][2] >> edges[i][0]; sort(edges.begin(), edges.end()); vector comp(n); for (int i = 0; i < n; ++i) comp[i] = i; int ans = 0; for (auto & edge: …$

4 / 10

graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari - Page 4

5 / 10

graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari - Page 5

Ko'proq o'qimoqchimisiz?

Barcha 10 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari" haqida

7-ma’ruza graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari. eng kichik uzunlikdagi daraxt – berilgan grafning eng kam og'irlikka ega bo’lgan daraxti, bu yerda daraxtning vazni uning qirralari og'irliklari yig'indisi sifatida tushuniladi. misol. minimal uzunlikdagi daraxtni topish muammosi ko'pincha xuddi shunday sharoitda uchraydi: masalan, har qanday shahardan boshqasiga (to'g'ridan-to'g'ri yoki boshqa shaharlar orqali) o'tish uchun n ta shaharlarni yo'llar bilan bog'lash kerak. berilgan juft shaharlar o'rtasida yo'llar qurishga ruxsat beriladi va har bir bunday yo'lni qurish qiymati ma'lum. qurilishning umumiy narxini minimallashtirish uchun qaysi yo'llarni qurish kerakligini hal qilish talab qilinadi. ushbu muammoni grafika nazariyasi nuqtai nazaridan shakllantirish mumk...

Bu fayl DOCX formatida 10 sahifadan iborat (376,3 KB). "graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: graflarda eng kichik uzunlikdag… DOCX 10 sahifa Bepul yuklash Telegram