DiM 2203 дискретті математика

Анықтама.  Төменде  аталған  шарттар:  а)  ілгек  жоқ;  b)  шығу  төбесі 
(бірде бір доға кірмейтін, тек шығатын ғана төбелері бар) бар болса; с) кіру 
төбесі  (бірде бір доға  шықпайтын,  тек кіру  төбелері  ғана бар)  бар болса; d) 
доғалардың Е жиынындағы әр доғада мәні өткізу қабілеті деп аталатын теріс 
емес бүтін мәнді с(е) функциясы анықталған болса; бағытталған, байланысты 
G(E, V) графы транспорт желісі деп аталады. 
Транспорт желісінің шығу,кіру деп аталатын төбелерден басқа төбелері 
аралық төбелер деп аталады. 1-суретте v
0
-басталу төбесі, z-аяқталу төбесі, v
1
, 
v
2
, v
3
, v
4
-аралық төбелер, ал әр доғада өткізу қабілеті көрсетілген. 
Анықтама.  Айталық, 
v
E   желінің  v  V  төбесінен  қосылатын,  а 
v
E -
төбесінен  шығатын  доғалар  жиыны  болсын.  G(V,E)  желісінің  Е  доғалар 
жиынында  берілген  бүтін  мәнді  теріс  емес  φ(е)  функциясы  а),  b),  c) 
шарттарын  қанағаттандырса  ағын  деп  аталады.  φ(е)  функциясының  мәнін  х 
төбесінен  у  төбесіне  баратын  v(x,y)  доғасымен  уақыт  бірлігінде  өтетеін 
заттың  саны  деп  қарауға  болады.  Бұл  сан  доғаның  өткізу  қабілетінен 
аспайды. Желінің басталатын және аяқталатын төбелерінен басқа төбелерде 
келетін заттардың саны одан шығатын заттарға тең болатындықтан еш жерде 
олар жиналып қалмайды 
a) 
v
v
E
e
E
e
e
e
)
(
)
(
, 
v v
0
, v z; 
b)  (e) c(e); 
c) 
z
E
e
E
e
e
e
v
)
(
)
(
0
 
 
5-сурет 
Анықтама. 
z
E
e
e)
(
  ағын  шамасы  деп  аталады  және  φz  болып 
белгіленеді. 
Анықтама.  е  доғасы  үшін  φ(е)=с(е)  болса,ол  толыққан  доға  деп,  ал 
әрбір  жолдың  басынан  бастап  ағына  дейін  ең  болмаса  бір  қаныққан  доғасы 
болса  z ағыны толық деп аталады. 
Анықтама. Айталық, v
0
A, ал z A шарты орындалатындай транспорт 
желісі төбелерінің ішкі жиыны A V болсын. А-ға енбейтін төбелерді А-ның 
төбелерімен  қосатын  доғалар  жиыны 
A
E   G(V,  E)  желісінің  Т  қимасы  деп 
аталады. Мысалы, 1-суретте көрсетілген желідегі төбелердің A={v1,v2,v4, z } 

ішкі  жиыннан  бөлек, 
A
E =  {(v
0
,  v
1
),  (v
0
,  v
2
),(v
3
,  z)}  доғалар  жиыны  қима 
болады. 
Анықтама. 
A
E   қимасының  өткізу  қабілеті  c(
A
E )  деп  қимаға  кіретін 
доғалардың  өткізу  қабілеттерінің  қосындыларын  айтады, 
A
E
e
A
e
c
E
c
)
(
)
(
 
деп белгілейді. 
Теорема.  G(V,  E)  транспорт  желісіндегі  v
0
A,  z Aорындалатындай 
төбелердің  ішкі  жиыны  A V  арқылы  анықталатын  G(V,  E)  транспорт 
желісінен  алынған  φ  ағыны  мен  кез  келген  Т  қимасы  үшін  z    c(
A
E ), 
орындалса, яғни желідегі кез келген ағынның шамасы (оның ішінде ең үлкені 
де) кез келген қиманың өткізу қабілетінен артық емес (оның ішінде ең кішісі 
де). 
Салдар.  Егер  кез-келген  φ  ағыны  мен 
A
E   қимасы  үшін  z=  с(
A
E ), 
орындалса,  онда  φ  ағыны–ең  үлкен,  ал 
A
E қимасының  өткізу  қабілеті  ең  аз 
болады. 
Транспорт  желісінің  ең  үлкен  ағынын  анықтайтын  Форд-Фалкерсон 
алгоритмін  қарастырайық.  Ол  алгоритм  бойынша  ағын  біртіндеп  ең  үлкен 
мән қабылдағанша үлкейтіле береді. 
AL  алгоритмі.  (транспорт  желісіндегі  ең  үлкен  ағынды  табу  ға 
арналған). 
Басы.  Транспорт  желісі  V  төбелер  жиыны,  доғалар  жиыны  E    және 
желінің  басы  v
0
V,  соңы  z V  арқылы  беріледі.  Доғалардың  өткізу  қабілеті 
c(е), е Е беріледі. 
1.  G(V,E)  желісінің  v
0
  мен  zтөбелерінен  басқаларын  еркін  түрде 
нөмірлейміз. 
2. Барлық e E үшін φ(e)=0 деп алып кез-келген ағын тұрғызамыз. 
3.  Транспорт  желісінің  басталу  төбесі  v
0
  мен 
 
соңғы  z  төбелерін 
қосатын барлық жолдарды қарап шығу. Егер φ ағыны толық болса 4 пунктке 
көш. Болмаса v
0
 
 
төбесін z қосатын барлық доғалары қаныққан емес μ жолын 
қарастыру керек те мына формула бойынша 
,
e
,
k
)
e
(
e
),
e
(
)
e
(
'
 φ' ағынын құрыңыз. Мұндағы 
))
(
)
(
(
min
e
e
c
k
e
. 
3–пунктті қайталаңыз. 
4.  Желінің  төбелеріне  бүтін  мәнді  таңбалар  және  желі  доғаларын  "+"  
және "-" таңбаларымен мына ережелер бойынша белгілейміз: 
а) v
0
 
 
басталу төбесін е0; 
в)  Егер  vi  төбесі  таңбаланса,  ал  v  әлі  таңбаланбаса,онда  егер  v  -ға  vi 
төбесінен( (vi,v)  c((vi,v)),  қанықпаған доға келсе, v төбесіне i таңбасы ,ал 
(vi,v) доғасына "+" таңбасы беріледі; немесе v төбесінен нөлдік емес ағынмен 
vi төбесіне ( ((v, vi))>0) баратын доға бар болса, (v, vi) доғасы "-" белгісімен 
таңбаланады. Қалған белгіленбеген доғалар мен төбелерге таңба берілмейді; 

с) 4в пунктегі сипатталған процесс жаңа таңбаланған доға мен төбенің 
пайда  болуы  тоқталғанға  дейін  қайталанады.  Осы  процестің  нәтижесінде  z  
таңбаланбаса,  онда  құрылған  ағын  ең  үлкен  болғаны  одан  соңына  көшу 
керек, керісінше болса 5 пунктке көшіңіз.  
5. Әрқайсысы келесі төбенің нөмірімен таңбаланған 
( ,
,
,...
)
z v v
v
i
i
1
2
0
 
төбелердің және   жиынынан алынған төбелерді қосатын μ (не обязательно 
маршрут  болуы  міндетті  емес)  доғалар  тізбегін  қарастырамыз.Төменде 
көрсетілгендей жаңа ағын құрасыз. 
"
_"
знак
_
имеет
_
и
_
e
_
если
_
1
)
e
(
"
_"
знак
_
имеет
_
и
_
e
_
если
_
,
1
)
e
(
e
_
если
_
),
e
(
)
e
(
'
 
4-пунктке көш. Соңы. 
Енді  сипатталған  алгоритммен  құрылған  ағынның  ең  үлкен  екендігін 
көрсетейік.  А  арқылы  желінің  белгіленбеген  төбелер  жиынын    белгілейміз. 
A
z
,
A
V
0
 болғандықтан А жиыны 
A
E
 желісінің қимасын анықтайды. Әрбір 
A
E
e
  доғасы  таңбаланған  төбені  таңбаланбаған 
A
V
  төбесімен  қосады.  V 
төбесі 
A
u
)),
v
,
u
((
c
))
v
,
u
((
  шартында  таңбаланбай  қалуы  мүмкін.  Екінші 
жағынан  А(
A
E
e
)  шығатын  әрбір  доғада 
0
)
e
(
теңдігі  орындалады, 
сондықтан 
)
E
(
c
)
e
(
c
)
e
(
)
e
(
A
E
e
E
e
E
e
z
A
A
A
 
өрнегі орындалады. Ендеше теореманың салдары бойынша φ
z 
 ең үлкен ағын 
болып табылады. Мысал. 2-суретте өрнектелген транспорт желісінің ең үлкен 
ағыны  анықтау  керек.Әр  доғада  жазылған  сандар  осы  доғаның  өткізу 
қабілетін  білдіреді.  Жолдың  басы    v
0     
төбесін  соңы  z-пен  қосатын  барлық 
жолды тізіп шығайық:  1=(v0, v1, v4, z);  2=(v0, v1, v2, v4, z);  3=(v0, v2, v3, 
z);  4=(v0,  v1,  v3,  z);  5=(v0,  v1,  v2,  v3,  z);  6=(v0,  v2,  v4,  z).  Желідегі 
алғашқы ағынды 0 деп алып, оны әр жолдың ең болмаса қаныққан бір доғасы 
болғанға  дейін  біртіндеп  көбейтеміз.  Ол  үшін  әр  жолдан  доғалардың  өткізу 
қабілеті мен осы доғалардағы ағынның ең кіші айырымын анықтаймыз  және 
бүкіл  жолдағы  ағынды  осы  шамаға  арттырамыз.  Бұл  процесс  6а,  6b,  6с,  6d 
суреттерде  көрсетілген,доғаларда  әрқайсысының  өткізу  қабілетімен  бірге 
жақша ішінде осы доғаның ағыны көрсетілген. 6d  суреттегі  құрылған ағын 
толық  және  ол 
z
  =  9    (6а  –6d)  суреттерде  қаныққан  доғалар  жуан 
сызықтармен бейнеленіп тұр). 
 

 
Құрылған ағынның ең үлкен болу шартын тексереміз.Ол үшін доғалар 
мен  төбелерді  таңбалаймыз,  нәтижесінде    z    төбесі  таңбаланған  болып 
шығады(  6d-сурет).  Бұл  6d-суреттегі  ағынның  ең  үлкен  емес  екендігін 
көрсетеді."+" -белгісімен таңбаланған  ағын шамасын көбейту, "-"- белгісімен 
таңбаланған  ағын шамасын  азайту  6e- суретте көрсетілгендей  шамасы  
z
 = 
11 болатын ағынға әкеледі. Бұл ең үлкен ағын болады. 
 
 
15 дәріс. Графтағы ең қысқа жолдар.  
 
Айталық,  G кез-келген  граф,  ал х,  y V(G)  оның  екі  төбесі  болсын. х-
тен  у  апаратын  маршрутты  Р
0
  деп,  ал  ұз.  Р  арқылы  х  пен  у-ті  қосатын  кез 
келген  маршруттың  ұзындығын  белгілейік.  (ұз.  Q  арқылы  Q  маршрутының 
ұзындығы белгіленеді.). 
Анықтама.  Егер  ұз.  Р
0
≤  ұзындығы  Р  болса  Р
0
  маршруты  ең  қысқа 
маршрут деп аталады. 
Ең  қысқа  жолда  төбелер  мен  доғалар  (қабырғалар)  қайталанбайды. 
Шынында  да,  егер  Р
0
  маршрутында  Р
0
:х=z,  e
1
,  z
1
,….,z
p-1
,  e
p
,  z
p
=у    z
i
=z
j
  бар 
болса,  онда  Р
0
  маршрутын  z
і
-ден  z
j
-ға  дейінгі  кесіндіні  алып  тастап 
қысқартуға  болар  еді,  яғни  Р
0
  -ді  x  =  z
0
,  e
1
,...,e
i
,  z
i
,  e
j+1
,...,z
p-1
,  e
p
,  z
p
=у 
маршрутымен  алмастырар  едік.  Сондықтан  да  шын  мәнінде  ең  қысқа 

маршрут қарапайым шынжыр болады. «Ең қысқа жол», «Ең қысқа маршрут», 
«Ең қысқа шынжыр» терминдерінің мағынасы бірдей. 
Айталық, G= байланысқан бағытталмаған граф, ал а мен b оның 
әртүрлі төбелері болсын. 
Анықтама. Ең қысқа (a, b) -маршруты  a, b  төбелерінің арақашықтығы 
деп аталады және 
)
,
( b
а
 мен белгіленеді. 
)
,
( b
а
=0  (анықтама  бойынша  арақашықтық  0  ге  тең  болсын).  Бұлай 
анықталған 
арақашықтық 
метриканың 
төмендегідей 
аксиомаларын 
қанағаттандырады. 
- 
)
,
( b
а
 ≥0; 
- 
)
,
( b
а
 = 0‹═›a=b; 
- 
)
,
( b
а
 =
( b, a) (симметриялық); 
- 
)
,
( b
а
 <
)
,
(
)
,
(
a
c
c
а
  (үшбұрыш теңсіздігі) 
Анықтама.  Егер  M={a
1
,  a
2
,  …,  a
n
}  төбелер  жиыны  болса,  онда 
элементтері  P
ij 
=(р
ij
)  арақашықтықтар  арқылы  анықталатын  р
ij
=
)
,
(
j
i
a
а
 
матрицасы  арақашықтық  матрицасы  деп  аталады.  P
T
=P,  яғни  Р-симетриялы 
матрица. 
Анықтама.  Тұрақты  бір  а  төбесі  үшін  e(a)
max{
)
,
( b
a
│b M}  а 
төбесінің  эксцентриситеті    деп  аталады.    Яғни  төбелердің  эксцентриситеті 
осы төбемен одан ең алыс жатқан төбенің арақашықтығы. 
Егер  Р  арақашықтық  матрицасы  болса  онда  e(a
i
)  эксцентриситеті  і-ші 
жолда 
орналасқан 
сандардың 
ең 
үлкеніне 
тең. 
 
 
Төбелері 
эксцентриситеттерінің ішіндегі ең үлкені G графының диаметрі деп аталады 
және ол d(G)  болып белгіленеді; d(G)=max{e(a)│a M} 
Анықтама.  Егер  e(a)=d(G)  болса  а  төбесі  перийфериядағы  төбе  деп 
аталады Мысал : 
Суреттегі G графының диаметрін табу керек. 
 
Анықтама.  Эксцентриситеттердің  ең  кішісі  графтың  радиусы  деп 
аталады r(G) болып белгіленеді; r (G)
min{e (a)│a M}; 
Анықтама.  Егер  e(a)=r(G)  а  төбесі  орталық  төбе  деп  аталады.  Барлық 
орталық  төбелердің  жиыны  графтың  центрі  деп  аталады.  Мысалы, 
жоғарыдағы  графтың  радиусы  2-ге  тең  r(G)=2,  центрі  {2,  4,  5}  жиыны 
болады. 
Орталық  төбелерді  табу  есебі  іс  жүзінде  көптеп  кездеседі.  Мысалы 
граф – төбелері елді мекендер, қабырғалары олардың арасындағы жолдарды 
білдіретін  –  жолдар  желісін  өрнектейтін  болсын.Ауруханаларды,  қызмет 
көрсету пунктерін т.б. тиімді орналастыру керек. Тиімділік дегенді бұл жерде 
қызмет көрсететін пункттен неғұрлым алыс орналасқан елді мекендердің ара 
қашықтығын  неғұрлым  азайту  болып  табылады.  Демек,  графтың  орталық 

төбелері  больница,  қызмет  көрсету  пункттерін  орналастыратын  орындар 
болып  табылады.  Нақтылы  есептерде  бұларға  қоса  елді  мекендердің  ара 
қашықтығын, жолға кететін уақыт, жол бағасын т.б. ескеруге тура келеді. Бұл 
параметрлерді  ескеру  үшін  салмақталған  графтар  қолданылады.  Айталық 
G=  әр  (a,  b)  доғасының  салмағы (a,  b)  нақты  санына  тең 
салмақтанған граф болсын. 
Анықтама.a
1
,  a
2
,…,a
n
,  a
n+1
  маршрутының  салмағы  деп 
n
i
i
i
a
a
1
1
)
,
(
 
санын  айтады.  (a,  b)-  маршрутының  салмақтарының  ең  кішісі    а  және  b 
төбелерінің  салмақтанған  арақашықтығы  деп  аталады 
)
,
( b
a
  болып 
белгіленеді. 
Анықтама.  Салмағы 
)
,
( b
a
  арақашықтығына  тең  (a,  b)  маршруты 
салмақтанған G графындағы ең қысқа маршрут деп аталады. 
Анықтама. 
а 
төбесінің 
салмақтанған 
эксцентриситеті 
деп 
max{
)
,
( b
a
│b M} санын айтады, оны 
)
(a
e
 деп белгілейді. 
)
(a
e
=max{
)
,
( b
a
│b m} 
Анықтама.  G  графының  салмақтанған  орталық  төбесі  деп 
)
(a
e
=min{
)
(b
e
│b M} а төбесін айтады. 
Анықтама.  Орталық  төбенің  салмақтанған  эксцентриситеті  G 
графының салмақтанған радиусы деп аталады , 
)
(G
r
 болып белгіленеді. 
Мысалы:  Салмақтанған  орталық  төбе  Новосибирск 
)
(a
e
=274,  ал 
)
(G
r
=681  
Графтағы  ең  қысқа  маршрутты  анықтайтын  өте  қарапайым  әрі  тиімді 
алгоритм бар. 
 
Оны  бұрыннан  белгілі  бас  қатырғыш  жұмбақ  есеп  мысалында 
қарастырайық.    Екі  адамда  вино  құйылған  8  литрлік  бір  құмыра  және  5 
литрлік, 3 литрлік екі бос құмыра бар. Виноны құмыралар не толық, не бос 
болатындай құйып, екі адам барлық виноны тең бөлісуі керек. 
Алдымен  екі  мүмкіндікті  қарастырамыз:  8  литрлік  құмырадан  вино  5 
литрлік  және  3  литрлік  құмыраларға  құйылады.  Бұл  мүмкіндіктерді 
символдық  түрде    800→350  және  800→503  деп  белгілейік.  Құмыраларға 
виноны  құюдың  әртүрлі  мүмкіндіктерін  (х,у,z)  үштігімен  немесе  қысқаша 
хуz  деп  белгілейміз.  Мұндағы  х  –  8  литрлік  құмырадағы  вино,  у–5  литрлік 
құмырадағы  вино  және  z  –  3  литрлік  құмыраға  құйылатын  вино.  350 
жағдайында  3  түрлі  құю  мүмкіндігі  бар:  350→323,  350→053,  350→800. 
Осындай  ситуацияларға  талдау  жасай  келе  және  құмыраларды  түрліше 

толтыра  отыра  суретте  көрсетілгендей  бағытталған  граф  аламыз.  Алынған 
графтың  төбелері  ретінде  әртүрлі  жағдайларды  сипаттайтын  үштіктер  ал 
виноны  түрліше  құюлар  доғаларға  сәйкес  келеді.  Әрине,  бұлграфта  еселі 
доғалар  жоқ,  яғни  бұл  диграф.  Жалпы,  ең  қысқа  маршрутты  анықтау 
есептеріндегі  графтарда  ілгектер  мен  еселі  қабырғалар  (доға)  жоқ  деп 
алынады. 800 төбеден 440 төбесіне  апаратын маршрут табылса есеп шешілді 
деп  есептейміз.  Суреттен  мұндай  жол  оңай  табылатындығын  көреміз:  800, 
350, 323, 620, 152, 143, 440. Бұл жолға есептің шешімін беретін төмендегідей 
құюлар сәйкес келеді. 
Вино 8 литрлік құмырадан 5 литрлік құмыраға толтырылады. 
 
1-Сурет. Түрлі жағдайлар мен құюлар графы. 
Содан  кейін  5  литрлік  құмырадан  вино  3  литрлік  құмыра  толғанға 
дейін құйылады. 3 литрлік құмырадан вино түгелдей 8 литрлікке құйылады. 5 
литрліктегі  2  литр  3  литрлікке  құйылады.  8  литрліктегі  5  литрлікке 
толтырылады. 5 литрліктен 1 литрді 8 литрлік құмыраға құю керек (толғанға 
дейін). Соңында 3 литрліктен барлық виноны 8 литрлік құмыраға құйылады. 
Нәтижесінде  8  литрлік  құмырада  4  литр  вино  және  сонша  литр  5  литрлік 
құмырада болады. Вино тең бөлінді. 
Осы  800  төбеден     440  төбеге  апаратын  жол  ең  қысқа  болады.  Бұл 
жолды    графтардағы  ең  қысқа  маршрутты    анықтайтын  алгоритмді 
пайдаланып та табуға болады. Енді осы  алгоритмнің жұмысын  формальды 
түрде  сипаттап көрейік: 
Алгоритмнің  жұмысы  барысында  х
0
=800  алғашқы  төбеден  бірдей 
қашықтықтағы төбелер жиыны құрылады. Бұл жиындарды вертикаль түзулер  
яғни  ярустарға (2 сурет) орналастырамыз (2-сурет). Нөлінші яруста бір ғана 
х
0
=800  төбесі  орналасқан.  Бірінші  яруста  800-ден  шығатын  доғалар  кіретін  
төбелер  орналасқан  (350  және  503).  Екінші  ярусқа  350  және  503  төбелерге 
сыбайлас, бірақ 0-ші немесе 1-ші ярустарға кірмейтін төбелерді белгілейміз. 
Егер k-шы ярус құрылған болса (k+1)-ярусқа G графының алдыңғы ярустарда 
жоқ және k-шы ярустағы төбелерге сыбайлас төбелерді енгіземіз. Ярус құру 
у
0
=440 төбесі алынған сәтте тоқталады. 
Осыдан  кейін  құрылған  графтың  у
0
=440  төбесінен  х
0
=800  төбесіне 
қайту  барысында  маршрутты  анықтаймыз.  Бұл  маршрутпен  кері  жүру 
барысында  х
0
=800  төбесінен  у
0
=440  төбесіне    апаратын  ең  қысқа  жол 
табылады.   

 
2-сурет "Ярусты" граф 
Біз  ең  қысқа  жолды  табу  алгоритмін  1-суреттегі  графқа 
қолданылатындай  сипаттадық.  Нақтылы  бір  мысалға  жазылған  бұл 
алгоритмді  кез  келген  графқа  қолдануға  болатындай  алгоритмнің 
сипаттамасын  келтірейік:  Al1  алгоритмін  графтың  берілген  екі  төбесін 
қосатын  ең  қысқа  маршрутын  табу  үшін  сипаттаймыз.  Бұл  алгоритмнің 
негізіне берілген графтың бір төбесінен шығатын ең қысқа жолдардың графы 
деп  қарастыруға  болатын  ярустық  граф  құру  алгоритмі  жатады.  Сондықтан 
алдымен  ең  қысқа  жолдардан  құралған  ішкі  граф  құратын  Al2  алгоритмін 
сипаттайық: 
Al2 алгоритмі (ең қысқа жолдар графын құрады). 
Басы. Бағытталған G графы және оның бір х0 V(G) төбесі берілген. G 
графын  кіретін  және  шығатын  аймақтар  {O+(х),  O-(х)|x V(G)}  үйірімен 
берейік. 
1. L:={x
0
}, M:= , Г(x
0
):= , h(x
0
):=0, t:=0; 
Мұндағы L мәндері құрылғалы тұрған ағымдағы яруста жатқан төбелер 
жиыны болатын айнымалы; М-мәндері құрылғалы тұрған ағымдағы ярустың 
алдындағы яруста орналасқан төбелер жиыны болатын айнымалы; Г әрбір х 
төбесіне  құрылатын  графтың  х–ке  апаратын  төбелер  жиынын  белгілейтін 
функция;  h  x
o
  төбесінен  x  төбесіне  дейінгі  аралықты    көрсететін  натурал 
санды кез келген x төбесіне белгілейтін функция; t- h функциясын есептеуге 
қолданылатын бүтін мәнді айнымалы t. 
2. M:=MUL; 
3. Әрбір z L, t:=t+1; L:= {O-(x)|x L}\M, Г(z):=O+(z) М, Г(z):=t+1; 
4. Тексеру: L= . Егер дұрыс болса 2 пунктке көш. 
Соңы. М, h және Г баспаға бер. 
Мұнда  М  x
o
  төбесінен  шығатын  ең  қысқа  жолдар  графының  төбелер 
жиыны; Г(х) ең қысқа жолдар графынан шығатын х төбесінің аймағы. 
h(х)–G  графындағы  ρ(х
0
,  х)  арақашықтығы(х  пен  у  төбесінің  арақаш-
ықтығы деп х пен у-ті қосатын ең қысқа жолды айтады). 
1-кесте 
X 800  350  503  053  323  530  620  233  602  251  152  701  143  710  440  413 
Г   
800  800  350  350  503  323  530  620  233  602  251  152  701  143  710 
H 0 
1 
1 
2 
2 
2 
3 
3 
4 
4 
5 
5 
6 
6 
7 
7 
AL2 алгоритмін х
0
-800 төбесімен G басқатырғыш графына қолданғанда 
26 қадам жүргізіледі, оған қоса М айнымалысының  ең соңғы мәні Г және h 

функцияларының мәндерімен берілген 1-кестеде  көрсетілген жиын болады. 
1-кестеде  шын  мәнінде  х
0
-800  төбесінен  шығатын  ең  қысқа  жолдар  графы 
көрсетілген. (Г(х) бұл графта х төбесінің кір етін аймағы). 
х
0
 төбесінен у
0
 төбесіне жеткізетін ең қысқа жолды табу үшін кестеден 
Г(у
0
)  мәнін  табамыз  және  одан  қандай  да  бір  у
1
Г(у
0
)  төбесін  аламыз.  у
1
 
төбесі  үшін  Г(у
1
)  мәнін  табамыз  да,  одан  қандай  да  бір  у
2
Г(у
1
)  төбесін 
аламыз. Осылай жалғастыра келе х
0
 төбесіне келеміз ( бұл төбе үшін Г(х
0
)=0). 
Мысалы,  у
0
=440  алсақ  мынадай  тізбек  аламыз:  у
0
=440,  у
1
=143 Г(440),  у
2 
=152 Г(143), у
3
=602 Г(143), у
4
=620 Г(602), у
5
=323 Г(620), у
6
=350 Г(323), 
у
7
=800,  Г(800)=0.  Демек,  800  төбесінен  440  төбесіне  жеткізетін  ең  қысқа 
маршрут: 800, 350, 323, 620, 602, 152, 143, 440. 
Графтың  екі  төбесінің  арасындағы  ең  қысқа  жолды  анықтайтын  Al1 
алгоритмін Al2 алгоритмінен жеңіл шығарып алуға болады. 
Al1  алгоритмі  (графтың  екі  төбесінің  арасындағы  ең  қысқа  жолды 
анықтайды) 
Басы. G бағытталған граф, х
0
, у
0
 оның екі төбесі 
Al2 алгоритмін (G, х
0
) жұбына қолдану. 
у:=у
0
, u:u=у
0
. 
Мұнда құрылып жатқан ең қысқа жолдың ағымдағы төбесі у-тің мәні болады. 
Г(у)  табу  және  Г(у)=0  екендігін  тексеру.  Егер  шарт  дұрыс  болса,  «х
0
-
ден у
0
-ге апаратын жол жоқ» деген хабар баспаға шықсын. 
x
0
Г(у). екендігін тексеру. Егер дұрыс болса, соңына көш. 
Қандай  да  бір  z Г(у)  төбесін  алу.  Анық  болу  үшін  Г(у)  тізіміндегі 
бірінші төбені аламыз да у:=z және u:=z,u 3 қадамға көш. 
Мұндағы z,u z-ті u тізбегінің басына қосқандағы нәтижені білдіреді. 
Соңы. U тізбегін баспаға шығару. 
 

жүктеу/скачать 3,62 Mb.

Достарыңызбен бөлісу: