Граф бөліктеріне қолданылатын амалдар

б)  Антисиметриялы  R  қатынасына  еселі  қабырғаларсыз,(әртүрлі 
төбелерге қарама-қарсы бағытталған  қабырғалары бар төбелер  болмайтын)  
өзара бір мәнді бағытталған G(R) графы сәйкес келеді . 
в)  Егер    R  рефлексивті  болса,  барлық  төбелерінде  ілгектері  бар  еселі 
қабырғаларсыз G(R)  графы сәйкес келеді. 
г) Егер  R антирефлексивті болса, еселі қабырғаларсыз G(R)  графында 
бір де бір ілгек болмайды. 
д)  Егер    R  транзитивті  болса,    еселі  қабырғаларсыз  G(R)    графының 
әрбір
)
,
(
v
v
  және 
)
,
(
v
v
  қабырғалар  жұбына    оларды  тұйықтайтын 
)
,
(
v
v
 
қабырғасы бар болады. 
Цикломатикалық  сан.  Бағытталмаған  G(V,  E)  графы  берілсін. 
υ(G)=m-n+p,  Мұндағы  m–граф  қабырғаларының  саны;  n–граф  төбелерінің 
саны; p–байланысты компоненттер саны G(V, E) графының цикломатикалық 
саны  деп  аталады.  Цикломатикалық  санының  физикалық  мағынасы  бар:  ол 
графтың тәуелсіз циклдарының санына тең. Электр шынжырларын есептеген 
кезде цикломатикалық сан тәуелсіз контурлар санын есептеуге қолданылады.  
1-Теорема.Егер  G1  графы  G  графының  суграфы  болса,  онда  υ(G1)≤ 
υ(G). 
2-Теорема.Байланысты графта цикл болмауы үшін υ(G)=0 қажетті және 
жеткілікті. 
3-Теорема. Егер G графтың екі байланысты G
1
 және G
2
 компоненттері 
бар болса, онда υ(G)=υ(G
1
)+υ(G
2
). 
4-Теорема. Графта цикл болмауы үшін υ(G)=0 қажетті және жеткілікті.  
Айталық,  G(V,  E)  бағытталмаған  граф.  G  графының  S
1
,  S
2
,…,S
k
 
циклдар  жүйесі  сызықты  тәуелді  деп  аталады,  егер  қандай  да  бір  i
1
,  i
2
,  …,i
r
  
(1≤   i
1
 ≤ i
2 
≤…≤ i
r
 ≤ k) S
i1
∆   S
i2
∆…∆S
ik 
ноль граф болса. Керісінше болса S
1
, 
S
2
, …,S
k
 циклдары сызықты тәуелсіз циклдар деп аталады. Сызықты-тәуелсіз 
циклдардың ең көп саны G графындағы тәуелсіз циклдар саны деп аталады.  
5-Теорема. 
Графтың 
цикломатикалық 
саны 
оның 
тәуелсіз 
циклдарының санына тең.   
Хроматикалық сан. Әр төбесіне қандай да бір бояу сәйкестендірілген 
және  сыбайлас  төбелер  әртүрлі  бояулармен  боялған  граф  деп  аталады.  G 
графын дұрыс бояуға қажетті бояулардың саны оның хроматикалық саны деп 
аталады және χ(G) болып белгіленеді.  
6-Теорема.G  графы  ноль-граф  болса  ғана  бір  хроматикалы  граф 
болады. 
7-Теорема  (Кениг  теоремасы).  Граф  бихроматикалы  болуы  үшін  онда 
тақ ұзындықты қарапайым цикл болмауы қажетті және жеткілікті.  
Ағаштар,  ағаштардың  негізгі  қасиеттері.  Шексіз  бағытталмаған 
байланысты граф ағаш деп, ал циклсыз байланыссыз граф орман деп аталады. 
Анықтама бола алатындай G ағашының кейбір қасиеттерін қарастырамыз: 
а) G байланысты және циклы жоқ; 
б) G циклы жоқ және n-1 қабырғасы бар; 
в) G байланысты және n-1 қабырғасы бар; 

г)  G  графында  цикл  жоқ,  бірақ  сыбайлас  емес  төбелер  арасында 
қабырға қосу тек бір ғана циклдың пайда болуына әкеледі; 
д)  G  байланысты,  бірақ  бұл  қасиетін  кез  келген  қабырға  алынып 
тасталса жоғалтады; 
е)  G  графының  кез  келген  төбелер  жұбы  тек  бір  ғана  шынжырмен 
байланысқан. 
Граф қаңқасы. 
8-Теорема. Граф байланысты болса ғана орман болатын суграф болады. 
Орман  болатын  G  суграфы  қаңқалы  ағаш  немесе  G  суграфының 
қаңқасы деп аталады. 
Ең аз қосылу туралы есеп.(Ең аз салмақты қаңқалы ағаш құру) 
Жол  тұрғызу  есебі  түрінде  өрнектеуге  болатын  мына  есептің 
практикалық  мағынасы  үлкен.  Жолдар  желісімен  қосылуы  қажет  бірнеше 
қалалар  болсын.  Әр  екі  қаланы  қосатын  жолдың  бағасы  белгілі.  Мүмкін 
болатын  жолдар  желісінің  ең  арзанын  салу  қажет  болсын.  (Жолдардың 
орнына электр желісін, мұнай құбыры желісі, т.б. алуға болады. 
Ең  арзан  жолдар  желісін  кескіндейтін  граф  әрқашан  ағаш  болады. 
Себебі,  егер  цикл  бар  болса,  циклдың  бір  қабырғасын  алып  тастауға  болар 
еді,  ал  төбелер  қосылған  болып  қала  берер  еді.  Есептің  математикалық 
қойылуы. Айталық, бағытталмаған G(V, E), |V|=n, графының әр қабырғасына 
осы  қабырғаның  салмағы  болып  саналатын  қандай  да  бір  μ(e)  нақты  сан 
бекітілген  болсын.  G  графында  салмағы  ең  аз,  ең  кіші  қосылу,  яғни  G 
графының Т қаңқасын салу керек болсын.  
μ(T)=
T
e
e)
(
. 
Краскал  алгоритмін  қарастырайық  (ең  аз  салмақты  қаңқалы  ағаш 
сызу).  
Сызу жұмысын салмағы μ(e
1
 ) ең аз e
1
E
 қабырғасын таңдаудан басталады. 
Егер мұндай қабырғалар бірнешеу болса, олардың кез келгенін алуға болады. 
Таңдалған қабырғаға E\{e
1
} алынған ең аз салмақты е2  қабырғасы е3 ретінде 
цикл  құрмайтын  E\{e
1
,е
2
}  деп  алынған  ең  аз  салмақты  E\{  e
1
,е
2
,  e
3
} 
таңдалады.  Қабырға  таңдау  процесі  кез  келген  қабырға  қосу  цикл  пайда 
болуына әкеліп соққанға дейін жүргізіледі. Осы граф ең аз салмақты қаңқалы 
ағаш болып саналады.  
 
13-дәріс. Байланысты графтар.  
Егер  графтың  кез  келген  2  төбесін  қосатын  маршрут  бар  болса,  граф 
байланысты  (мықты  байланысты)  деп  аталады,ондай  маршрут    болмаса    ол  
байланыспаған  граф болады. 
Маршруттар. Айталық G= Н-граф болсын. 
Мұндағы a
1
, a
2
,…,a
n+1
M  U
1 
U
2
, … , U
n
R 
Анықтама:  Егер  U
i
=(a
i
,  a
i+1
),  i=1,  2,…,n  (екі  көрші  төбені  қосатын 
қабырға ) болса a
1
, U
1
, a
2
, U
2
, a
3
,…,U
n
, a
n+1  
(*) маршрут деп аталады. 

 
а
1
-төбесі  маршруттың  басы,  а
n+1
-соңы  болады.  (*)  Маршрутты  төбелердің 
тізбегі  арқылы  беруге  болады.Маршрут  доғаларының  саны  оның  ұзындығы 
деп  аталады.  Айталық,  G  н-граф  болсын.  Егер  (*)  маршрутта  қабырғалар 
[a
1
a
2
],…,[a
n
a
n+1
]  әртүрлі  болса,  яғни  әр  қабырға  бірден  артық  кездеспесе, 
маршрут  шынжыр  деп  аталады,  ал  графтың  кез  келген  төбесі  2-ден  артық 
емес қабырғаға инцидентті болса (төбелер әртүрлі), онда маршрут қарапайым 
шынжыр деп аталады. 
Анықтама. Егер a
1
=a
n+1
 болса (*) маршруты циклды деп аталады (басы 
мен соңы бірдей маршрут). 
Анықтама. Циклы бар  маршрут шынжыр болса цикл деп аталады, ал 
маршрут қарапайым шынжыр болса қарапайым цикл деп аталады. 
Анықтама.  Бағытталмаған  циклсыз  граф  ациклды  граф  деп  аталады.  
Бағытталмаған графтың циклдарының ұзындықтарының ең кішісі құлаш деп 
аталады (обхват). 
Бұл  графта  (1,2),(1,2,4,7),(3,4,5,6)-қарапайым  шынжыр.(1,2,4,7,8,4)  -
қарапайым  емес  шынжыр(4-екі  рет).  (1,  2,  4,  7,  8,  4,  2)–шынжыр  емес 
маршрут; (1, 2, 4, 7, 8, 4, 1)–қрапайым емес цикл; 
(1, 2,  4,  1)–қарапайым цикл;  Графтың  құлашы  3-ке  тең.  Айталық  граф 
бағытталған  болсын.  Егер  (*)  маршруттарындағы  доғалар  әртүрлі  болса, 
маршрут  жол  деп  аталады.  Егер  a
1
=a
n+1
  болса  маршрут  контур  деп  аталады. 
Контур жоқ графтар контурсыз граф деп аталады. 
 
Маршруттың  (жолдың)  қабырғаларынаң  (доғаларының)саны  оның 
ұзындығы деп аталады. 
Анықтама.  Егер  (a,  b)  жолы бар  болса,  онда  b  төбесі  а  дан  жекізетін 
(достижымый) төбе деп аталады. 
Мысал: Контур бар (1,2,3). 
5-төбеге  басқа  кез-келген  төбеден  жетуге  болады,  ал  5-тен  ешқандай 
басқа төбе жеткізбейді. 
 
Графтың байланыс компоненттері. 

Анықтама.  Бірдей  емес  екі  төбесі  (
1
,
11
) G  маршрутпен  қосылған 
(
1
-басы, 
11
-соңы) бағытталмаған G графы байланысты граф деп аталады.  
Анықтама: Егер бағытталмаған G графының әртүрлі а,в төбелері үшін 
(а,в)  және  в,а)маршруттары  бар  болса,онда  G  мықты  байланысқан  граф  деп 
аталады. 
 
Мұндай ұғымды мультиграф үшін де енгізуге болады. 
Мысалдар: 
 
Кез  келген  байланысты  бағытталмаған  графтар  мықты  байланысқан 
граф екендігін байқауға болады. 
Маршрутпен  байланысты  төбелер  қарапайым  шынжыр  мен  де 
байланысқан болады.  
Байланыстылық  қатынастың  эквиваленттік  қасиеті  бар  және  ол  граф 
төбелерін  өзара  қиылыспайтын  V
i
,  i=1,  2,…,k  ішкі  жиындарға  бөлінуін 
анықтайды.  Сондықтан  барлық  ішкі  графтар  G(V
i
)  байланысқан  және  олар 
графтың  байланыс  компоненттері  деп  аталады.  Бағытталған  G  графы 
доғалардың бағыты ескерілмесе байланысқан делінеді, ал егер кез келген V
1
 
төбесінен V
11
 төбесіне жол болса мықты байланысқан болады. 
Мысалы, мына суреттегі графта екі {1, 2, 3, 4} және {5, 6, 7} байланыс 
компонент  тері  бар.  Ал  мына  төмендегі  суреттегі  бағытталған 
графта{1,2,3},{4}және {5} төбелерімен берілген 3 мықты компоненттері бар.  
 
Теорема. 
Кез 
келген 
графты 
қиылыспайтын 
байланыс 
компоненттерінің  бірігуімен  өрнектеуге  болады.  Графтың  байланыс 
компоненттеріне жіктелуі бір мәнді анықталады. G=U
i
 G(V
i
) 
Сонымен,  төбелердің  байланысты  компоненттері  мен  мықты  компоненттер 
жиыны төбелер жиындарын бөлшектейді, ал байл. компоненттерінің саны бір 
мәнді анықталады. 
Келесі  теорема  сыбайлас  A
G
  матрицасы  бойынша  G  графының 
маршруттарын зерттеуге мүмкіндік береді. 

Теорема.  Егер  A
G
-G  графыың  іргелестік  матрицасы  болса,  онда 
G
G
G
k
G
A
A
A
A

  матрицасының  (i,  j)-ші  элементі  ұзындығы  к-ға  тең  (а
i,j
)-
маршруттарының санын анықтайды. 
Салдар.  A
G
+
2
G
A
+…+
1
n
G
A
  матрицасының  (i,j)-ші  элементі  0-ге  тең 
болмаса ғана n қуатты G графында a
i
 төбесі ішінде болатын  (a
i
,a
j
) - маршрут 
(a
i
≠a
j
) бар.  
Мысалы.  Сыбайлас  A
G
  матрицаның  көмегімен  G  графында  (1,3) 
маршрутының бар екендігін анықтаймыз. 
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
G
А
 
 
(1,3)- элемент  0-ге тең, демек ұзындығы 1-ге тең маршрут жоқ 
2
1
0
1
1
1
0
1
1
0
2
1
0
0
1
1
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
G
A
 
(1,3)-элемент  тағыда  0-ге  тең.  Ұзындығы  2-ге  тең  (1,3)-маршруты  жоқ 
Ұзындығы 3-ке тең (1,3)-маршруттың саны 1-ге тең 
1
0
3
2
1
0
2
1
3
2
1
3
2
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
1
0
0
0
2
1
0
1
1
1
0
1
1
0
2
1
0
0
1
1
2
G
G
A
A
 
Графтың  суретінен  бұл  маршрут  (1,  4,  2,  3)  төбелерімен  анықталады. 
Бұл тізбекті іргелестік матрицаны көбейту арқылы алуға болады: 
3
G
A
  матр-ң 
(1, 3) элементі 
2
G
A
 матр-ң (1, 2) элементімен A
G
 матрицаның (2, 3) элементін 
көбейткеннен алынады. 
Өз кезегінде 
2
G
A
 м-ң (1, 2) элементі A
G
 матрицаның (1, 4) эл-н A
G
 (4,2)-
ге көбейткеннен алынды. Демек 1-ден 3-ке жылжи отыра үш қадамнан кейін 
(1, 4, 2, 3) маршруты алынады. 
3
G
A
 матриц-да (4, 2) элементі 3 ке тең, демек, ұзындығы 3 ке тең (4, 2)- 
маршрутының саны үшеу. Олар:(4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2) 
Граф төбелерінің арасында ұзындығы к-ға тең маршруттың (жол) бар жоғын 
анықтайтын алгоритмді қарастырайық: 

Айталық, 
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
A
 төбелері υ1, υ2, υ3, υ4 бағытталған G графының 
сыбайлас  матрицасы  болсын.
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
2
A
  матрицасын 
қарастырайық. Жалпы алғанда, 
1
kj
ik
A
A
  орындалатындай  к саны бар болса 
ғана 
1
2
ij
A
  болады,  басқаша  айтқанда  υі  төбесімен  υк  төбесін  және  υк 
төбесімен  υі  төбелерін  қосатын  қабырға  бар.  Сондықтан  υі  төбесінен  υj 
төбесіне  апаратын ұзындығы 2-ге тең жол бар. 
Теорема.  Айталық,  G  төбелері  υ1,  υ2,  υ3...  υn  және  сыбайлас  А 
матрицасы  берілген  бағытталған  граф  болсын. 
i
v
  мен 
j
v   төбелерінің 
арасында 
.
A
k
ij
1
  (1≤к≤n)  шарты  орындалса  ғана  ұзындығы  к  –ға  тең    жол 
бар болады. 
Уоршалл алгоритмі. 
1.  А  матрицасының  бірінші  бағанын  қарап  шығыңыз.  Бұл  бағаннан  1 
бар жолды табыңыз да оған бірін жолды қосыңыз. 
2. (1) пунктте құрылған матрицаның 2 бағанын қараңыз. Бұл бағаннан 1 
бар жолды тауып, оған 2-жолды қосыңыз. 
3.(2) пунктте құрылған  матрицаның 3 бағанын қараңыз. Бұл бағаннан 1 
бар жолды  тауып оған 3- жолды қосыңыз. 
4.Осылайша  алдыңғы  қадамда  құрылған  матрицаның  келесі 
бағандарын қарауды жалғастырасыз. Одан 1 бар жолды тауып, оған зерттеліп 
отырған бағанға сәйкес жолды қосасыз. 
5. Барлық бағандар қарастырылып болғанша жалғастырасыз. 
Жеткізу  матрицасы.  (b
ij
)=E+A
G
+A
2
G
+…+A
2
n
  матрицасынан  төменде 
берілген ережемен n ретті C=(с
ij
) матрицасын құрамыз: 
0
0
0
1
ij
ij
ij
b
егер
b
егер
C
 
Бұл  С  матрицасы  егер  G-Н-граф  болса  байланыстық  матрица  деп 
аталады,  ал  G-бағытталған  граф  болса  жеткізуші  матрица  деп  аталады.  G 
графында C
ij
=1 болса ғана (a
i
, a
j
) i≠j маршрут бар болады. 
Сонымен  С  матрицасында  G  графының  әр  түрлі  элементтерінің 
арасындағы 
байланыстың 
бар 
я 
жоқ 
екендігі 
турлы 
ақпарат 
болады(маршруттар арқылы). 
Егер  G
i
-бағытталмаған  байланысты  граф  болса,  онда  С  байланыс 
матрицасының барлық элементтері 1-ге тең. 
Жалпы  (жағдайда)  алғанда  бағытталмаған  графтың  байланыс 
матрицасы  граф  төбелері  жиынын  байланыс  компоненттеріне  бөлетін 
эквиваленттік қатынас матрицасы болып табылады. 
Контр жеткізу матрицасы. 
Төмендегі ережемен анықталғн Q=(q
ij
)-матрицасын анықтаймыз. 

болса
керісінше
болса
жетуге
тµбесінен
a
тµбесіне
a
егер
q
j
i
ij
,
0
1
 
Бұл  матрицаның  анықталуынан,  егер  С-жеткізу  матрицасы  болса, 
Q=C
Т
.  Бұл  екі  матрицаларды  (Q,  C)  графтың  мықты  компоненттерін  табуға 
пайдалануға болады.  
S=Q*C  матрицасын  қарастырамыз  ,  мұндағы  *  операциясы  С  мен  Q 
матрицаларының сәйкес элементтерін көбейту дегенді көрсетеді, яғни:  
s
ij
=q
ij * 
с
ij 
матрицаның    a
i
  және  a
j
  төбелері  өзара  жеткізетін  төбелер  болса,  яғни 
a
i
a
j
, a
j
a
i
 болса ғана s
ij
=1.  
 
Демек  s  матрицасы  төмендегідей  Е  эквивалентті  қатынас  болып 
табылады:  a
i
  мен  a
j
  бірге  бір  мықты  компонентте  болса  ғана  a
i
  Е  a
j
 
орындалады.  Демек,  a
i
  төбесі  бар  мықты  компонент  s
ij
=1  a
j
    элементтерінен 
тұрады. Суреттегі графтың жеткізуші С матрица сымен контр  жеткізуші Q 
матрицалары төмендегідей:  
1
0
0
0
0
1
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
С
,  
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
T
C
Q
,  
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
Q
C
S
  
S  матрицаның  екінші  жолы  бойынша  2-ші  төбе  кіретін  мықты 
компонент {1,2,3} төбелерінен тұрады. 
 
Графтар теориясына негіз болған есептердің бірі Кенигсберг көпірлері 
туралы  есеп.  1-Суретте  Леонард  Эйлердің  тұсындағы(17  ғасыр)  XVII 
ғасырдағы  Кенигсберг  қаласының  картасы  салынған.  Қала  Прегель  өзенінің 
екі  жақ  жағалауында  және  2  аралда.  орналасқан  Аралдар  өзара  және 
жағалаулармен 7 көпірмен жалғасқан. Кенигсберг тұрғындарының арасында 
сол кезде Кенигсберг көпірлері деп аталатын есеп кең тараған: 
Есеп. Үйден шығып әр көпірмен бір рет қана жүріп үйге қайтып келуге 
болама ма деген сұрақ туады? 
 
3-сурет  
Бұл есеп үшін көпірлерден өтудің маңызы бар. Сондықтан көпірлердің 
орналасуын  2-суреттегі  бағытталмаған  мультиграфпен  алмастыруға  болады. 
Бұл  графта  Б,  В  төбелері  өзеннің  жағаларына,  ал  А,  Г  төбелері  аралдар,  ал 
мультиграфтың  қабырғалары  көпірлерге  сәйкес  келеді.  Егер  G  графында 

оның  барлық  қабырғалары  арқылы  өтетін  цикл  табылса  Кенигсберг  туралы 
есеп  шешілді  деп  есептеледі  (Цикл  деп  бірде  бір  қабырға  қайталанбайтын 
циклды маршрутты айтатынын еске саламыз). Демек графтар тілінде есептін 
қойылуы  төмендегідей:  Мультиграфта  оның  барлық  қабырғалары 
болатындай  цикл  бар  ма?  Атақты  ғалым-математик  Л.  Эйлер  байланысты, 
бағытталмаған  мультиграфта  оның  барлық  қабырғалары  болатындай  цикл 
болудың шартын анықтап дәлелдеп берді. 
 
4-сурет 
Теорема  Байланысты  бағытталмаған  мультиграфтың  әр  төбесінің 
дәрежесі жұп сан болса ғана Эйлер циклы болады. 
Анықтама. Мультиграфтың барлық қабырғалары болатын цикл Эйлер 
циклы деп, ал Эйлер циклы бар граф Эйлер графы деп аталады. Жоғардағы 
суреттегі мультиграфта Эйлер циклы жоқ, себебі онда дәрежесі тақ төбе бар. 
Айталық ондай цикл бар деп жориық. Олай болғанда бұл циклдың  бойымен 
жүре отыра графтың  кез келген төбесіне одан шығу  қанша болса сонша рет 
кіреміз.  Демек,  G  графының  әр  төбесінің  дәрежесі  жұп  болуы  керек.  G 
графында керісінше барлық төбелер тақ дәрежелі. 
Бұл тұжырым кез келген бағытталған G графына да жарамды. Сонымен 
бағытталмаған  G  графында  оның  барлық  қабырғалары  арқылы  өтетін  цикл 
бар болу үшін G графының төбелерінің  дәрежесі жұп болуы қажетті.  
Анықтама.  Бағытталмаған  (бағытталған)  G  графындағы  цикл      оның 
барлық  қабырғалары  арқылы  өтсе,  ол-  Эйлер  циклы  деп  аталады.  
Бағытталмаған  графта Эйлер циклы бар болу үшін бұл графтың байланысты 
болуы қажетті. 
Анықтама.  Кез  келген  х,у V(G)  төбелерін  қосатын  жол  бар  болса 
бағытталмаған G графы байланысты граф деп аталады. 
Анықтама.  Егер  С  циклы  Бағытталмаған  G  графының  барлық 
қабырғалары  арқылы  өтетін  болса,  кез-келген  х,у V(G)  төбелері  үшін  C 
циклының  х  төбесінен  у  төбесіне  апаратын  C(x,y)  кесіндісі  х-тен  у-ке 
апаратын жол болып табылады. Олай болса G байланысты. Эйлер циклының 
бар болуы үшін графтың дәрежелерінің жұп болуы және оған қоса графтың 
байланысты болуы жеткілікті екен. 
Эйлер теоремасы. Бағытталмаған графта Эйлер циклы болу үшін оның 
байланысты  болуы  және  оның  барлық  дәрежелерінің  жұп  болуы  қажетті 
және жеткілікті. 
Эйлер  теоремасын  шамалы  өзгеріспен  бағытталған  графтарға  да 
қолдануға  болады.  Ол  үшін  бағытталған  графтардың  да  байланысты  болу 
ұғымын енгізу керек. 

Доғаларының            бағыттарын  алып  тастағаннан  кейінгі  алынған 
бағытталмаған  G  графы  байланысты  болса,      бағытталған  °G    графы 
байланысты деп аталады. 
Теорема.  Бағытталған  G  графында  Эйлер  циклы  болу  үшін  оның  әр 
төбесіне  кіретін  дәрежемен  шығатын  дәрежелердің  бірдей  болуы  қажетті 
және жеткілікті. дәр.+(х) = дәр.- (х) барлық x V(G). 
Байланысты  және  тиелген  бағытталмаған  графтағы  белгіленген  V
0
 
және  Vn  төбелерін  қосатын  ең  қысқа  жолды  іздеуді  жүзеге  асыратын  Форд 
алгоритмі. 
V
0
 төбесіне λ
0
 таңбасы беріледі де, қалған төбелердің таңбалары λ=∞V
0 
болады. 
(Vi,  Vj)  қабырғаларының  ішінен  λ
j
  –  λ
i
>L((V
i
,  V
j
))  орындалатындай 
қабырғалар  ізделеді  және  олардың  λ
j
  индекстері  λ
j
'=λ
i
+L((V
i
,  V
j 
)) 
алмастырылады.  Индекстрді  өзгерту  процесі  одан  әрі  λj  таңбасын  азайту 
мүмкіндігі  болмайтын  бірде  бір  қабырға  қалмағанша  жүргізіледі. 
Нәтижесінде  әр  төбенің  таңбасы  осы  төбенің  V
0
  төбесіне  дейінгі  ең  қысқа 
қашықтықты  көрсетеді.  Ең  қысқа  жолдың  өзін  табу  үшін  Vn    төбесінен  екі 
жағындағы төбелердің таңбаларының айырымы қабырғаның ұзындығына тең 
қабырғалардың бойымен қозғалу қажет. 
Гамильтон  циклдары.  Гамильтон  циклдары  туралы  есептің 
интерпритациясы  ретінде  ең  көп  тараған  коммивояжер  туралы  есепті 
қарастыруға болады. 
Коммивояжер  аралайтын  бірнеше  қалалардың  арақашықтықтары 
белгілі. 
Барлық  қалаларда  бір  реттен  ғана  болып    алғашқы  шыққан  қаласына 
қайтып  келетін  маршрутты  табу  керек.  Егер  мұндай  маршруттар  бірнешеу 
болса,  олардың  ең  қысқасын  табу  керек.  Мұндай  есептер  іс  жүзінде  жиі 
кездеседі,  мысал  үшін    өндіріс  өнімдерін  сауда  орталықтарына  ең  қысқа 
жолмен жеткізу есебі. 
Мұндай  есептерді  шешудің  жалпы  ортақ  теоремалары  мен  көлемі 
жөнінен  шағын,  әрі  тиімді  алгоритмдердің  жоқтығы  есепті  шешуде 
қиындықтар туғызады. 

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

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