Алгоритмларни лойиҳалаш

---

1 
“Алгоритмларни лойиҳалаш” фанидан маърузалар матни 
Бизга маълумки, ҳозирда аҳоли пунктлари орасидаги йўлларни, алоқа 
тармоқлари каналларини, сув, газ узатиш ва канализация қувурларини 
лойихалашда ахборот ёки моддий ресурсларни узатиш ҳаражатлари билан 
боғлиқ масалалар юзага келади. Бундай масалаларни математик 
моделлаштиришда графлар назариясидан фойдаланиш ва математик 
моделлар бўйича энг яхши вариантини таҳлил қилиш ва оптимал 
вариантларини танлаш мумкин бўлади. Ушбу ёндашувнинг қулайлиги 
шундаки, биз масаланинг физик параметрларига вақтинча эътибор бермасдан 
туриб, математик масалани ечишимиз ва шундан сўнг дастлабки масалага 
қайтиб,олинган натижаларини берилган масалага мос равишда таҳлил 
қилишимиз мумкин. 
Бизга боғланган, йўналтирилмаган граф берилган бўлиб, унинг 
қирралари маълум вазнларга эга бўлсин. Вазнлар- бу шундай сонларки 
,уларберилган қирраларнинг чекка учлари орасидаги масофасини билдиради, 
харажатларни англатади.“Хасис алгоритмлар” номи билан бирлаштирилган
алгоритмлар 
графнинг 
шундай 
А 
ва 
D 
учлари 
орасидаги 
маршрутни(йўналишни) топишга каратилганки, у энг арзон(энг кам 
А ва D учлари орасидаги барча мумкин бўлган йўналишларни аниқлаб, 
шундан сўнг ушбу йўналишларни энг кам харажатлилигини танлаймиз. 
Ушбу турдаги маълум масалалардан бири “коммивояжер масаласи” 
бўлади.Агар бирор графни тасаввур қилсак ва унинг учлари қайсидир 
ташкилотнинг бўлимларини ва қирралари эса шу бўлимлар орасидаги йўлини 
англатса,у холда коммивояжер–ушбу ташкилотнинг ходими, ҳамма 
бўлимларни айланиб чиқиб, яна ўзининг идорасига қайтиши керак бўлади. 
Бунда у энг кам харажатли йўналишни танлаши керак бўлади. Бошқача 
қилиб айтганда коммивояжер графда энг кам харажатли Гамильтон циклини 
танлаши керак. 
Шунга ўхшаш кўплаб масалалар бирор коммуникация тармоқлари 
билан боғлиқ граф учун ҳам вужудга келиши мумкин.Шунинг учун 
 
17-18 маъруза
“ОЧКЎЗ” АЛГОРИТМЛАР. КРУСКАЛ АЛГОРИТМИ.ПРИМА
АЛГОРИТМИ.ХОФФМАН ДАРАХТИ
.
харажатли) бўлиши керак. Табиийки, бундай масалаларни ечишда биз аввал 
бу қирра бўйлаб харакатланишда транспорт харажатларини ёки бошқа 

---

2 
дастлабки ишланмаларни олдиндан хозирлаб қўйиш мақсадга мувофиқ 
бўлиб,улар асосида масала ечими тезлашиб боради. Бунинг учун барилган 
дейилади. Кейинроқ кўрамизки,бу дарахт минимал маршрутлар топишда 
эффектив восита бўлади. Остов дарахти қуриш усулларининг бирини 
тасвирлашга ўтамиз. 
Алгоритм ғоясини ифодалайлик. Аввал дарахт қирраларининг тўплами бўш 
деб эълон қилинади. Шундан сўнг мумкин бўлгунга қадар кейинги амал 
бажарилади: барча қирралардан, уларни мавжуд тўпламга қўшилиши цикл 
пайдо бўлишига олиб келмайдиган қирралардан,энг арзон(энг кам 
харажатли) қирраси танлаб олинади ва мавжуд тўпламга қўшиб қўйилади. 
Бундай қирралар қолмаганида,алгоритм тугалланади ва биз дастлабки графни
циклар бўлмаслигидан,у энг арзон(энг кам харажатли)дарахт бўлиб,унинг 
босқич схематик тарзда ифодалаймиз. Дастлабки граф 11.1.расмда 
келтирилган 
11.1.расм 
B 
D 
5 
10 C 
7 
A 
8 
12 9 
6
15 
E 
8 
F 
Графнинг хар бир қирраси маълум вазнга эга бўлиб, остов дарахтини 
қуришда биз айнан қирралар вазнидан келиб чиқамиз. Бунинг учун 
қирраларни вазнлари бўйича тартиблаймиз. Энг арзон 5 қийматли қирра АВ 
дарахт тўпламининг биринчи элементи бўлади ва кейнги AG, CD, AC, GF, 
DE қирралар қиймати бўйича дарахтга қўшиб борилади 
бошқача 
номини 
остов 
дарахти 
деб 
юритилади. 
Алгоритмни 
яққол тасаввурини мисолда амалга оширамиз ва барча жараённи босқичма-
граф асосида энг арзон(кам харажатли) граф қурилиб, бу граф 
остов дарахти