Мысал-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) б)
46-сызба
Транспорттық желідегі ағын
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 қанық доға деп айтылады.
