Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер


Транспорттық желілерде толық және максимал



бет9/10
Дата29.09.2022
өлшемі64,16 Kb.
#40779
түріЛекция
1   2   3   4   5   6   7   8   9   10
Байланысты:
14-лекция

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 бграфта ζ11υ2υ4υ6 жәй тізбе айырамыз және ζ1 дегі доғалар бойынша ағындарды а=3 санына ((v2,v4)-доға қанық болғанға дейін) үлкейтеміз. Нәтижеде бір қанық доғаға ие болған φ=φ1 ағын аламыз (47в-сызба).
Ол доғаға ☼ белгі қоямыз. Қалған бграфты тағыда D1 арқылы белгілейміз (47г - сызба) . D1 графтан кезектегі ζ21υ2 υ3υ4 υ6 жай тізбені айырамыз және ζ2 дегі доғалар бойынша ағынды a=2 ге үлкейтеміз ((υ23),(υ34) доғалар қанық болғанға дейін). Нәтижеде үш қанық доғаға ие болған φ=φ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

  1. (б)

υ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е -сызба). Тағыда ζ31υ3 υ5υ6 жәй тізбеде (υ35) доғалар қанық болғанға дейін a=2 санға ағынды үлкейтеміз. Сонымен φ=φ3 төрт қанық доғаға ие (47ж-сызба). Сол секілді ζ41υ 2υ5υ6 жәй тізбеде (υ12) доғаны 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)
ℓ(x)= (60)
∞, егер φ(x)=c(x);

0, егер φ(x)>0;


ℓ(x1)= (61)
∞, если φ(x)=0,
яғни I(D,φ) тиелген бграф болады. Сонымен I(D,φ) бграфтағы кез келген (υ1n)-жол ұзындығы 0, не ∞ ке тең екендігі айқын.
Айталық ζ-I(D,φ) бграфтағы кез келген бір жай тізбе болсын. Егер не x, не х1 доғалар ζ тізбеде бар болса, онда ζ тізбе x=(υ,ω)ÎX доға арқылы өтеді деп айтамыз.
Сонда, егер ζ тізбеде x қатысса, онда ζ және x бағыты дәл келеді, ал ζ тізбеде x1 қатысса, ζ және х бағыты қарама-қарсы деп айтамыз.


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   10




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет