Дискрет анал

Дарахт-граф. Режалаштириш тармоғи.

Дарахт- графлар. Таркибида цикллар бўлмаган граф дарахт –граф дейилади.
Бу таърифдан қуйидаги натижалар келиб чикади: биринчидан, дарахт –графда каррали қирралар бўлмайди, иккинчидан дарахт-графнинг хар бир жуфт учини боғловчи ягона занжир мавжуд.
Дарахт графнинг бошланғич учини илдизи дейилади. Шуни айтиш керакки, дарахт- графнинг ихтиерий учи унинг илдизи бўла олади. Дарахт- граф элементлари сонини ҳисоблаш учун қуйидаги теорема хизмат қилади.
Учлари n та бўлган дарахт графнинг n-1 та қирраси бўлади.
Дарахт графлар транспорт системалари билан боғлик масалаларни ечишда жуда қулай восита бўлиб хизмат қилади. Шу жумладан, у йўллар қуриш масаласида мухим ахамиятга эгадир. Айтайлик ахоли яшайдиган n та пунктни ўзаро асфальт йўллар ёки темир йўллар билан туташтириш керак бўлсин. Ихтиерий А ва В шахарларни туташтирувчи йўлни қуриш харажати маълум бўлсин. Масала шундан иборатки, мумкин бўлган барча йўл тармоқларидан энг арзони қурилсин. Худди шунга ўхшаш масалалар электр узатиш тармоқларини , сув ва газ билан таъминлаш системаларини ва телефонлаштириш системаларини қуришда хам қаралиши мумкин ва хоказо.

3. 
   Граф тармоғида ресурсларни тақсимлаш масаласи.
   

Транспорт тармоғи деб тугунга эга бўлмаган чекли графга айтилади ва унда:

1. 
   ягона уч х₀ мавжудки, унинг учун = х₀ учни тармокнинг кириши ва шундай ягона уч Z мавжудки, унинг учун ГZ= булиб, Z учга тармокнинг чикиши дейилади;
   
2. 
   графнинг хар бир u ейига C(u) бутун сон мос қўйилган бўлиб, у шу ёйнинг ўтказиш қуввати дейилади.
   

Транспорт тармоғи тушунчаси билан оқим деган тушунча узвий боғланган.
Агар х- ихтиерий графнинг учи бўлса - х учга кирувчи барча ёйлар тўплами бўлсин.
Транспорт тармоғи оркали окаётган оким деб қуйидаги

шартларни қаноатлантирувчи функцияга айтилади.
ни х учдан у учга бир бирлик вақт ичида u=(x,y) ёйдан оқиб ўтувчи оким шу ёйнинг ўтказиш қувватидан катта бўла олмайди.

- транспорт тармоғидаги оқим миқдори дейилади.
Қуйидаги транспорт оқимини кўрайлик:
Ёйнинг узулишидаги рақамлар ўтказиш қувватини белгилайди. Йўналиш эса оқим йўналишини белгилайди, йўналиш устидаги рақамлар эса оқим миқдорини белгилайди.
Транспорт тармоғида оқимлар тақсимотини ўрганишда транспорт тармоғини кесими тушунчасини киритамиз.
Фараз қилайлик бирор АХ тўплам учун х₀А, zА бўлсин
орқали А га кирувчи ва А дан чикувчи ёйлар тўплами бўлсин.
ни транспорт тармоғининг А кесими деб атаймиз.
Ихтиерий А кесим учун

ўринли бўлади.

- транспорт тармоғидаги оқим миқдори дейилади.