Лекция Графтарды қолдану Графтарда қуат және ток үшін Кирхгоф теңдеулері. Графтарда ішкі және сыртқы тұрақтылық. Графтарда транспорттық желілер
Мысал-42. 38-сызбада бейнеленген және 35, 36, 38, 39-мысалдарда қарастырылған D бграфтың ядролары U2, U3 болады. Теорема
жүктеу/скачать 64,16 Kb.
|
14-лекция
- Бұл бет үшін навигация:
- 3. Графтарда транспорттық желілер ұғымы 18-анықтама
| Мысал-42. 38-сызбада бейнеленген және 35, 36, 38, 39-мысалдарда қарастырылған D бграфтың ядролары U2, U3 болады.
Теорема. NÎ V жиын D=(V,X) бграфтың ядросы болуы үшін ол бір үақытта максимал іштен тұрақты және минимал сырттан тұрақты болуы қажет және жеткілікті. Теорема бойынша D бграф ядросын айырып алу үшін D бграфтағы барлық минимал сырттан тұрақты төбелер жиынынан ішкі түрақты жиынды таңдау жеткілікті болады. 3. Графтарда транспорттық желілер ұғымы 18-анықтама. V={υ1,…,υn} төбелер жиынына ие болған D=(V,X) бграф транспорттық желі деп айтылады, егер мынадай шарттар орындалса: 1) көз деп аталатын D-(υ1)=Ø болған, яғни бірде бір доға кірмейтін тек біреуғана υ1 төбе бар; 2) соңы деп аталатын D+(υn)=Ø болған, яғни бірде бір доға шықпайтын тек біреуғана υn төбе бар; 3) әр бір xÎ X доғаға “доғаның өткізу қабилеті” деп аталатын c(x)≥0 бүтін сан сайкес қойылған. Транспорт желісіндегі көз және соңы болмаған төбелер аралық төбелер деп айтылады. Мысал-52. 46а-сызбада υ1-көзі, υ4-соңы, υ2, υ3-аралық төбелері болған транспорттық желі көрсетілген. Әр бір доғада жақшадағы сан арқылы оның өткізу қабілеті жазылған. υ2 υ2 (9) (4) 3 1 (3) 2 υ1 υ4 υ1 υ4 (2) 0 (6) (8) 3 5 υ3 υ3 a) б)
Транспорттық желідегі ағын 19-анықтама. D транспорттық желінің X доғалар жиынында анықталған және бүтін санды мәндер қабылдайтын φ(x) ф-я үшін 1) кез келген xÎ X үшін x доға бойынша ағын деп аталатын φ(x) шама 0≤ φ(x) ≤ c(x) шартты қанағаттандырса; 2) кез келген υ аралық төбелер үшін ∑φ(ω,υ) - ∑φ(υ,ω) = 0 ωÎD-(υ) ωÎD+(υ) теңдік орындалса, яғни υ төбеге кіретін доғалар бойынша ағын қосындысы, осы төбеден шығатын доғалар бойынша ағын қосындысына тең болса, онда φ(x) функцияны D транспорттық желінің мумкіндік ағыны деп айтылады. Мысал-53. 46б-сызбада транспорттық желінің мүмкіндік ағыны көрсетілген. Әр бір доғада ағын шамасы жазылған. Бұл жерде “мұмкіндік ағын” анықтамасында көрсетілген барлық шарттар орындалатындығы айқын. 56-тұжырым. D транспорттық желідегі кез келген φ мүмкіндік ағын үшін ∑ φ (υ1,υ) = ∑ φ (υ,υn) (58) υÎ D+(υ1) υÎ D-(υn) теңдік ақиқат. Тағыда φ мүмкіндік ағын анықтамасынан ∑ [ ∑ φ(ω,υ) - ∑ φ(υ,ω) ] = 0 (59) υÎ V\{υ1,υn} ωÎD- (υ) ωÎ D+(υ) теңдік орынды. D транспорттық желідегі υn төбеге кіретін барлық доғалар бойынша ағындар қосындысына және сол секілді υ1 төбеден шығатын барлық доғалар бойынша ағындар қосындысына тең болған φ* шама φ ағынның шамасы деп айтылады және мынадай есептеледі: φ* = ∑ φ(υ,υn) = ∑ φ(υ1,υ ). υÎ D-(υn) υÎ D+(υ1) Айталық D транспорттық желінің φ-мүмкіндік ағыны берілген болсын. Егер xÎ X доға ағыны өзінің өткізу қабілетіне тең, яғни φ(x)=c(x) болса, онда x қанық доға деп айтылады. жүктеу/скачать 64,16 Kb. Достарыңызбен бөлісу:
|