Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
Транспорттық желілерде толық және максимал
жүктеу/скачать 200,54 Kb.
|
| 4. Транспорттық желілерде толық және максимал
ағындарды табу мәселесі 20-анықтама. Егер D транспорттық желінің υ1 төбеден υn төбеге баратын кемінде бір қанық доғаға ие болған кез келген бір жолы табылса, онда φ толық ағын деп айтылады. Егер D транспорттық желінің ағын шамасы басқа мүмкіндік ағындарға салыстырғанда ең ұлкен φ* мән қабылдаса, онда оны максимал ағын деп айтылады. Барлық максимал ағындар толық болады. Ал кері жағдай болуы мүмкін емес. Бірақта толық ағынды максимал ағынға жұық ретінде қарастыруымыз мүмкін. Осыған байланысты D транспорт желісінің толық ағынын табу алгоритімін келтіреміз. Алгоритм №10. 1. Кез келген xÎ X ушін φ(x)=0, яғни нөлінші ағын ретінде бастаймыз. Сонымен қатар D1=D деп аламыз. 2. D1 бграфтың D транспорттық желісіндегі φ ағында қанық болған барлық доғаларды жоямыз . Алынған бграфты тағыда D1 арқылы белгілейміз. 3. D1 бграфта υ1 төбеден υn ге баратын ξ жай тізбекті табамыз. Егер ондай тізбе болмаса, онда D транспорт желісінің ізделінген толық ағыны φ болып есептеледі және алгоритм соңына жетеді. Ал, кері жағдайда 4-қадамға өтеміз. 4. φ(x) ағынның ζ тізбесіндегі әр бір доғаны бір шамаға (a>0) үлкейтеміз. Ол кезде ζ тізбенің кемінде бір доғасы қанық доғаға өтуі тиіс, ал басқа доғалардағы ағындар өзінің өткізу мүмкіншілігінен асып кетпеуі талап етіледі. Сонда φ* ағын шамасы а ға үлкейеді, ал D транспорт желісіндегі φ ағынның өзі мүмкіндік қалпында қалады. Бұдан кейін 2-қадамға өтеміз. Мысал-54. 47а-сызбада бейнеленген D транспорттық желінің толық ағынын табамыз (сызбадағы жақшалар ішіндегі сан доғалардың мүмкіндік қабілетін білдіреді.) 10-алгоритмді қолданамыз. Бастап D1=D, xÎ X, φ(x)=0 деп қабылдаймыз. (Бұл жағдай үшін D бграфтың доғалар бойынша φ ағынның шамасы 47б-сызбада бейнеленген). Нөльдік ағында қанық доғалар қатыспайды. D1 бграфта ζ1=υ1υ2υ4υ6 жәй тізбе айырамыз және ζ1 дегі доғалар бойынша ағындарды а=3 санына ((v2,v4)-доға қанық болғанға дейін) үлкейтеміз. Нәтижеде бір қанық доғаға ие болған φ=φ1 ағын аламыз (47в-сызба). Ол доғаға ☼ белгі қоямыз. Қалған бграфты тағыда D1 арқылы белгілейміз (47г - сызба) . D1 графтан кезектегі ζ2=υ1υ2 υ3υ4 υ6 жай тізбені айырамыз және ζ2 дегі доғалар бойынша ағынды a=2 ге үлкейтеміз ((υ2,υ3),(υ3,υ4) доғалар қанық болғанға дейін). Нәтижеде үш қанық доғаға ие болған φ=φ2 ағын аламыз (47д-сызба). D1 графтан белгіленген қанық доғаларды жоямыз. υ2 υ2 0 υ5 (6) υ5 (7) (3) (2) (9) 0 0 0 (2) υ6 υ1 0 0 υ6 υ1 0 0 (8) (2) (7) 0 υ3 υ4 υ3 υ4 (б) υ2 υ2 υ5 0 υ5 3 0 3 0 υ6 υ1 υ1 υ6 ☼ 0 3 0 υ3 υ4 υ3 υ4 (в) (г) υ2 υ2 υ5 0 υ5 5 3 0 2 ☼ υ6 υ1 υ6 υ1 ☼ 0 0 5 υ3 2 ☼ υ4 υ3 υ4 (д) (е) υ2 0 υ5 υ2 υ5 5 3 2 2 2 ☼ ☼ υ6 υ1 υ1 ☼ υ6 2 5 υ3 2 ☼ υ4 υ3 υ4 (ж) (з) υ2 υ2 υ5 2 υ5 7 3 2 4 ☼ 2 ☼ ☼ υ6 υ1 υ6 υ1 ☼ 2 5 υ3 2 ☼ υ4 υ3 υ4 (и) (к) 47- сызба Қалған бграф тағыда D1 арқылы белгіленеді (47е -сызба). Тағыда ζ3=υ1υ3 υ5υ6 жәй тізбеде (υ3,υ5) доғалар қанық болғанға дейін a=2 санға ағынды үлкейтеміз. Сонымен φ=φ3 төрт қанық доғаға ие (47ж-сызба). Сол секілді ζ4=υ1υ 2υ5υ6 жәй тізбеде (υ1,υ2) доғаны a=2 ге қанықтырып бес қанық доғаға ие болған φ=φ4 ағын құраймыз (47и-сызба). D1 графтан соңғы қанық доғаны жойып, қалған бграфты тағыда D1 арқылы белгілейміз (47к-сызба). Сонғы алынған D1 бграфта υ1 төбеден υ6 төбеге өтетін жол жоқ, яғни φ4 ағыннан басқа қанық доғаларға ие болатын жол табылмайды, сондықтан φ4 толық ағын есептеледі. Ал толық ағыннан алынған φ*4 шама 9 ға тең. Өсімше бграф. Берілген D транспорттық желі және оның φ мүмкіндік ағын үшін D желідегі барлық төбелерге ие болған I(D,φ) өсімше бграф еңгіземіз. D транспорттық желідегі әр бір x=(υ,ω)ÎX доғасына I(D,φ) өсімше бграфта екі доға сәйкес қойылады: x және x1=(ω,υ)- х доғасының бағытына қарама-қарсы болған доға. I(D,φ) өсімше бграфтың х= ( υ,ω )Î X, x1=(ω,ν) доғаларына ℓ-ұзындық өлшемін енгіземіз: 0, егер φ(x) |