Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
жүктеу/скачать 200,54 Kb.
|
14-лекция
| Мысал-55. 48-сызбада 54-мысалда берілген D транспорттық желі және φ4 ағын үшін I(D,φ4) өсімше бграф бейнеленген.
υ2 0 υ5 0 0 ∞ 0 υ1 0 ∞ 0 0 υ6 0 ∞ ∞ 0 0 0 0 υ3 0 υ4 ¥ 48 - сызба Транспорт желілерінде максимал ағындар құру алгоритмі. Алгоритм №11. 1. i=0 деп аламыз. Айталық φ0-D транспорттық желідегі кез келген мүмкіндік ағын болсын (мысалы, толық немесе нөльдік φ0(x)=0, xÎ Х ағын); 2. D желі және φi бойынша I(D,φi) өсімше бграф құрамыз; 3. I(D,φi) бграфта υ1 төбеден υn ге өтетін минимал жол болған ζі жәй тізбе табамыз. Егер осы тізбенің ұзындығы ∞ ке тең болса, онда φі ағын максимал болады және алгоритм аяқталады. Кері жағдайда ζі тізбе бойлап ai>0 максимал мұмкіндік шама үлкейтеміз. Бұл жерде, егер ζі тізбе бойынша өтетін x доға дәл келсе қосылады, ал қарама-қарсы болса алынады. ℓ(ζi )=0 бойынша және (60),(61) теңдіктерден пайдаланып aі шаманың бар екендігін табамыз. Нәтижеде D транспорттық желінің ағыны өзгереді, яғни φі ағыннан φi+1 ағынға өтеміз және сонымен φ*і+1=φ*i + ai . і:=i+1 және 2- қадамға өтеміз. Мысал-57. 54, 55-мысалдардың жалғасы ретінде D транспорттық желінің максимал ағынын құрастырамыз. Бұл жерде φ4 толық ағыннан басталады. I(D,φ4) бграф бейнеленген 48-сызбадағы (55-мысал) өсімше бграфтан пайдаланамыз. I(D,φ4) тиелген бграфта ұзындығы 0 ге тең болған ζ5=υ1υ3υ2υ5υ6 жәй тізбе табылады. (бұл жерде ζ5-I(D,φ4) дегі υ1 ден υ6 ға баратын минимал жол). ζ5 тізбе бойынша ағынды максимал мүмкіндік шамаға (2 ге) үлкейтеміз ((υ2,υ3) доға қанық болғанша). Нәтижеде φ5 ағын аламыз (49а-сызба). I(D,φ5) өсімше бграф құрастырамыз (49б-сызба). Бұл жерде I(D,φ5) тиелген бграфта кез келген υ1 ден υ6 ға баратын жол ұзындығы ∞ ке тең. Сондықтан φ5 максимал ағын болады және φ*5=11. υ2 0 υ5 υ2 4 υ5 0 7 3 2 6 0 ∞ 0 0 ☼ ☼ υ6 υ1 ∞ 0 ∞ 0 υ1 υ6 ☼ 5 0 0 0 4 0 υ3 2 υ4 υ3 ¥ υ4 ☼ 0 (а) (б) 49 – сызба жүктеу/скачать 200,54 Kb. Достарыңызбен бөлісу:
|