Тапсырманы орындау мысалы. Біріншілік желі граф түрінде көрсетіледі, оның қабырғаларына – салмақтар (бағалар

 

Біріншілік желі граф түрінде көрсетіледі, оның қабырғаларына – салмақтар (бағалар, ұзындықтар) және арналар санындағы өткізу қабілеттіліктер сәйкес болады. Мысал үшін 6 шыңдар және 8 қабырғалардан құрылатын желіні қарастырайық. Әр қабырғаның сыйымдылығы b_ij=20 арнаға тең. Арналар тарату жоспарын құру кезінде келесі шарттар орындалуы тиіс: 1 және 3 шыңдар арасындағы шоғыр сыймдылығы 18 тең, 3 және 6 -16, 2 және 4 –15, 5 және 6 –16 арналар, яғни Y₁₃=18; Y₃₆=16; Y₂₄=15; Y₅₆=16; сонымен қатар әр жолдағы транзитті телімдер саны үштен аспау керек.

 

 

18 – сурет. Желі графы

 

i және j шыңдар арасындағы жолын тізбектелген түйіндер жиынтығы түрінде ұсынамыз.

Мысалы, 3 және 6 шыңдар келесі жолдармен байланысу мүмкін:

m₃₆¹={3,2,6}; m₃₆²={3,5,1,2,6}; m₃₆³={3,5,1,4,6};

m₃₆⁴={3,2,1,4,6}; m₃₆⁵={3,4,6}; m₃₆⁶={3,4,1,2,6};

 

Жолдың рангі - оған кіретін қабырғалар саны аталады. Анықтамаға сәйкес:

 

r(m¹)=2; r(m²)=4; r(m³)=4; r(m⁴)=4; r(m⁵)=2; r(m⁶)=4.

 

Байланыс сапасын қамтамасыз ету мақсатымен жолдың рангі шектеледі, қарастырылған тапсырмасы үшін үштен аспайтын ранг үшін жолдарды ғана қолдану керек, яғни m₃₆¹ және m₃₆⁵ жолдарын.

 

Алгоритм

1 - қадамы. Әрбір шыңдар қосындысы (i,j) үшін, жолдар көпшілігі құрылады және ранг шектелу шартына сәйкес келетін жолдар алынады.

2 - қадамы. Талап қойылған арналар саны Y_ij арналар арасында теңдей бөлінеді.

1-2 қадамдар барлық (i,j) жұптар үшін орындалады.

3 - қадамы. Рұқсат берілген сыйымдылықтар матрицасы құрылады, жолдары байланыс жолдарына сәйкес болатын, ал бағаналар граф қабырғаларына. Жол мен бағана (i,j) қиылысында осы жолға берілген қабырғаның арналар саны х жазылады, яғни

Әрбір бағананың элементтер қосындысы осы қабырғаның араналар санын білдіреді.

4 - қадамы. Әрбір қабырғада қойылған шектелу тексеріледі. Егер олар орындалса, есеп шығарылды. Керісінше болса – 5 қадамы есептеледі.

5 - қадамы. Шамадан артық жүктемеленген қабырғалар үшін жүктемеден босату қажет (егер мүмкін болса) және 4 қадамына ауысу. Егер кейбір қабырғаларды жүктемеден босату мүмкінсіз болса – 7 қадамына ауысу.

6 - қадамы. Арналар таралу жоспары құрылады.

7 - қадамы. Желі сыйымдылығы жеткілікті болмағандықтан есеп мүмкін емес.

Мысал:

1 - қадамы. Ранг жолдар көпшілігін құрайық

2 - қадамы. Арналар саны барлық жолдарға теңдей бөлінеді

3 - қадамы. Сйымдылықтар матрицасын құрайық (2 - кесте).

Матрицаның бағаналары берілген желінің қабырғаларына сәйкес. (1-2),(1- 4), (1-5), (2-3)..., ал жолдар байланыс жолдарына : 1 жолдың (1-2), (2-3) бағаналарда 6 тең арналар саны жазылған, 2 жолдың (1-4) және (3-4) бағаналарда және т.б..

4 - қадамы. Әрбір бағанадағы арналар санын қосып және әрбір қабырғаның сыйымдылығы 20 тең болу шартын ескере отырып, тексереміз

 

 

мұндағы М - (i-j) қабырғасы арқылы өтетін жолдар көпшілігі.

 

Есептейміз

 

 

және |М+1| жолына жазамыз. Теріс шамасы анализденетін арналар таралу жоспарының ретсіз болуын және түзету қажеттілігін білдіреді. Мысалы, (1 -2) қабырғасына сәйкес болатын бағанада.

Арналар саны

6 + 5 + 4 =15

жолында

20-15 = 5,

(2-3) бағанада

6 + 8 + 5 + 4=23

=20-23 = -3,

Сонымен (2 - 3) қабырғаның жүктемесі жоғары.

Келесі әрекеттер – сол ағын ішінде реттеп шамадан артық жүктемеленген жолдардан жүктемесі аз жолдарға ауыстыру (5 қадамы).

 

5(I) - қадамы. жолына кіретін (2-3) қабырғасынан артық жүктемені (3 арна) аламыз, сонымен қатар, бұл жолдың барлық қабырғалардан (матрицада 6 цифраларын өшіріп 3 жазайық). Бқл арналарды (3) жүктемесі аз қабырғаларына қосайық, яғни (1-5) және (-5) қабырғалар арналарына.

4 (II) - қадамы. Жолдың элементтерін есептейік . және теріс болып табылады.

5 (II) - қадамы. жолында 1-ке арналар санын азайтып, жолында (1-2) және (1-4) қабырғаларда қосамыз.

4 (III) - қадамы. есептеп, (3,-4) қабырғасы ғана жүктемеленгенін көреміз.

5 (III) - қадамы. жолдың арналар санын азайтып1,5,3 көбейтеміз.

4 (IV) - қадамы. Тексеріс көрсетті, шамадан артық жүктемеленген қабырғалар жоқ, яғни жоспар орындалады.

 

8 – кесте. Арналар тарату жоспары

 

Yij	Жол сыйымдылығы	Қабырғалар
1-2	1-4	1-5	2-3	2-6	3-4	3-5	4-6
Y13	X1,2,3	6 3			6 3
X1,4,3		6 3				6 3
X1,5,3			6 9 12				6 9 12
Y36	X3,2,6
X3,4,6
Y24	X2,3,4
X2,1,4	5 6	5 6
X2,6,4					5 4			5 4
Y56	X5,1,2,6
X5,1,4,6
X5,1,2,6
X5,3,4,6
		+5	+5	+6	-3	-1	-3	+6	-1	АТЖ ретсіз
		+8	+5	+3		-1	-3	+3	-1	АТЖ ретсіз
		+7	+4	+3			-3	+3		АТЖ ретсіз
										ретті