graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari

DOCX 10 pages 376.3 KB Free download

10 pages

FaylHub.uz

Download via Telegram

Size 376.3 KB

File type DOCX

Pages 10

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

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

Want to read more?

Download all 10 pages for free via Telegram.

Download full file

About "graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari"

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

This file contains 10 pages in DOCX format (376.3 KB). To download "graflarda eng kichik uzunlikdagi daraxtlarni qurish algoritmlari", click the Telegram button on the left.

Tags: graflarda eng kichik uzunlikdag… DOCX 10 pages Free download Telegram