Математикалық тұжырымдар мен анықтамаларды

Предикаттар  логикасының  тілі  математикалық  тұжырымдар  мен 
анықтамаларды  жазу  үшін  ыңғайлы.  Ол  ұғымдар  арасындағы  логикалық 
байланыстарды өрнектеу, анықтамаларды, теоремаларды, дәлелдеулерді жазу 
мүмкіндігін береді. Мұндай жазылулардың бірнеше мысалдарын келтірейік. 
Мысал  1.  Е  облыста  анықталған  ƒ(х)  функцияның  x
0 
нүктедегі 
b
  шегінің 
анықтамасы.: 
)
)
(
0
(
0
0
)
(
lim
0
0
b
x
f
x
x
E
x
x
f
b
x
x
. 
)
,
,
(
x
P
 
үш орынды предикатты қолданып жазамыз:  
))
,
,
(
(
0
0
)
(
lim
0
x
P
E
x
x
f
b
x
x
, мұнда 
)
)
(
0
(
)
,
,
(
0
b
x
f
x
x
x
P
. 
 
Мысал 2. Нүктедегі үзіліссіз функцияның анықтамасы.  
Егер 
))
,
,
(
(
0
0
x
P
E
x
, мұндағы 
)
)
(
)
(
0
(
)
,
,
(
0
0
x
f
x
f
x
x
x
P
, онда Е жиыныдағы 
анықталған 
)
(x
f
 функциясы 
E
x
0
 нүктеде үзіліссіз деп аталады.  
 
 
11-дәріс. Бағытталған және бағытталмаған графтар 
 
Графтар теориясының элементтері  
Граф  ұғымы.  Көптеген  қолданбалы  есептерде  айналамызды  қоршаған 
ортаның  әртүрлі  объектілер    арасындағы  байланыстар  жүйесі  зерттеледі. 
Объектілер  төбелер  деп  аталып,  нүктелер  арқылы  белгіленеді,  ал  төбелер 
арасындағы  байланыстар  доғалар  деп  аталып,  сәйкес  нүктелерді  қосатын 
бағытталған  түзулермен    белгіленеді.  Қала  көшелерін  граф  арқылы 
кескіндеуге  болады:  көше  қиылысуларын  графтардың  төбесі  деп,  ал 
көшелерді  доғалар деп алуға болады; 
Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф 
төбелері, ал операцияның орындалу кезегін көрсететін стрелкалар доғалар. 
Анықтама: G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—
жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, 
ал  бинарлы  R  қатынасының  R 
  M
2
  элементтері  доғалар  деп  аталады. 
Сонымен      граф  төбелері  дегеніміз  –айналамызды  қоршаған  ортаның  кез 
келген  объектісі.  Олардың  саны  шектеулі  болғандықтан,біз  оларды  натурал 
сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. 
Граф  қабырғаларын  әдетте  латын  әріптерімен  белгілейді.  G=  ‹M,R› 
графының  геометриялық  кескіні  жазықтықта  графтың  әр  төбесін  нүкте 
арқылы белгілеп ,  егер (a,b)   R болса а төбесінен b төбесіне доға жүргізу 
арқылы 
алынады. 
Мысалы: 
төбелері 
М={1,2,3,4}, 
ал 
доғалары 
R={(1,1),(1,2),(2,3),(3,4),(4,3),(4,1)}  болатын  G  графының  геометриялық 
кескіні төмендегідей: 

 
Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде 
қисық), 
сызықтардың 
ұзындығы 
туралы 
ақпараттар 
маңызды 
емес.Төбелердің  арасында  байланыс  бар  екендігі  және  ол  байланыс  туралы 
ақпарат  R  доғалар  жиынында  екендігі  болса  болды.Төбелерді  қосатын 
сызықтардың  бағыты  көрсетілген  болуы  мүмкін  (мысалдағы  сияқты). 
Мұндай граф бағытталған граф деп аталады (оргграф). Оған математикалық 
түрде мынандай анықтама беруге болады. 
Анықтама:  Егер  R  қатынасы  симметриялы  болмаса,  яғни 
(a,b) R,(b,а) R онда G= графы бағытталған (оргграф) деп аталады, ал 
R  қатынасы  симметриялы  болса  (a,b)  R,  (b,а)  R  онда  G  бағытталмаған 
(неоргграф)  немесе  н-граф  деп  аталады  Айталық:  a,b-граф  төбелері,  e=(a,b) 
оларды  қосатын  доға  болсын.  Мұндай  жағдайда  а,  b  төбелері  мен  е  доғасы 
инцидентті  деп  аталады.  b    мен  e  доғасы  да    инцидентті.  Әр  доға  e E    өзі 
қосатын  екі  төбеге  инцидентті  болады.  Бір  доғамен  қосылатын  2  төбе 
сыбайлас ( бүйірлес) деп аталады. 
Анықтама:  Төбелердің  бір  жұбына  инцидентті  доғалар  еселі  немесе 
параллель доғалар деп аталады 
Анықтама: Еселі доғалары бар граф мультиграф деп аталады. 
Анықтама: Шығатын және кіретін төбесі біреу болатын доға ілгек деп 
аталады. 
 
Анықтама: Егер (a,b), (b,а) доғалары бір уақытта R қатынасына жатса, 
онда  бұл  доғалар  туралы  ақпаратты  [a,b]  =  {(a,b),  (b,a)}  жиыны  арқылы 
көрсетуге болады. [a,b] жиыны қабырға деп аталады. 
Мысалы,мына суреттегі графтың 4 төбесі, 5   қабырғасы бар. 
Төбелері: v
1
, v
2
, v
3
, v
4
;  Қабырғалары:e
1
,e
2
, e
3
, e
4
 e
5
;  Бұл графтағы v
1
 мен v
2
; v
2
 
мен v
3
; v
3
 пен v
4
; v
4
 пен v
5
 іргелес төбелер, v
1
, v
3
-сыбайлас емес. 
Сол  сияқты:  e
1
,e
2
;  e
2
,e
3
;    e
3
,e
4
;  e
4
,e
1
;  e
1
,e
5
;  e
2
,e
5
;  e
3
,e
5
;  e
4
,e
5
;-қабырғалары 
сыбайлас.e
1
,e
3
; e
2
,e
4
;- сыбайлас емес қабырғалар. 
Егер  G={M,R}  орграфындағы  әр  (a,b) R  доғасына,  (b,a)  жұбын  қосса 
нәтижесінде  берілген  G  графына  сәйкес  Н-граф  шығады,  оны  F(G)  деп 
белгілейді. 

Анықтама:  Егер  граф  элементтерінің  (төбелері  мен  қабырғалары) 
жиыны ақырлы болса, графта ақырлы деп, ал қабырғалар жиыны бос болса, 
бос граф деп аталады. 
 
Ілгексіз,  әрі  еселі  қабырғалары  жоқ  және  әрбір  төбелер  жұбы 
қабырғамен қосылған граф толық граф деп аталады.  
 
Анықтама:  Берілген  G  графындағыдай  төбелері  және  G  графына 
қосқанда  оны  толық  графқа  айналдыра  тындай  ғана  қабырғалары  бар   
графы G-ң толықтауыш графы деп аталады. 
Анықтама:  Бағытталмаған  графтың  әр    қабырғасын    қарама  қарсы 
бағытталған  доғалармен  алмастырғаннан  алынған  граф  берілген  графқа 
сәйкес канонды граф деп аталады. 
Анықтама:  Еселі  доғаларсыз  бағытталған  графты  көбіне  диграф  деп 
атайды. G= - V-бос емес (төбелерінің) жиын; E VxV; 
Анықтама  G  н-графының    төбесіне 
инцидентті 
қабырғалар 
саны 
( ) 
V төбесінің  локальді  дәрежесі  деп 
аталады.  Н-графта  барлық  төбелердің 
локальды 
дәрежелерінің 
қосындысы 
графтың  2  еселенген  қабырғалар  санына 
тең, яғни жұп сан. Ілгек төбе дәрежесіне 2-ге тең үлес қосады: 
G
v
m
v
2
)
(
 
Анықтама Егер локальды дәреже жұп болса,төбе жұп деп,ал тақ болса 
төбе тақ төбе деп аталады. 0 дәрежелі төбе оқшауланған төбе деп аталады. 
V= {1,2,3,4}.
,
4
)
4
(
,
3
)
3
(
,
4
)
2
(
,
3
)
1
(
:
1
G
 
G
v
m
v
2
14
)
(
; 
Мұндағы, 
m =7–графтың 
қабырға  ларының  саны.  Бағытталған  графтың 
төбелері  үшін  2  локаль  ды  дәреже  анықталады. 
)
(
1
-
v
төбесінен  шығатын  қабырғалар  саны. 
)
(
2
-
v
  төбесіне  кіретін  қабырғалар  саны. 
Бағытталған  графта  барлық  төбелердің  локальды 

дәрежелері
)
(
1
, 
)
(
2
  осы  графтың  қабырғалар  санына  тең,  демек  олар 
өзара тең 
G
v
G
v
m
v
v
)
(
)
(
2
1
; Мысалы: 
;
3
)
4
(
,
2
)
3
(
,
1
)
2
(
,
1
)
1
(
;
1
)
4
(
,
1
)
3
(
,
3
)
2
(
,
2
)
1
(
2
2
2
2
1
1
1
1
 
G
v
G
v
m
v
v
7
)
(
)
(
2
1
 
1-ші,2-ші  типті  дәрежелер  қосындысы  бірдей  қабырғалар  санына  тең..Егер 
G
1
 төбелері мен қабырғалары G
2
 графының төбелері мен қабырғалары бірдей 
болса,яғни:  V
1
=V
2
, E
1
=E
2
 болса, онда G
1
=G
2
. 
 
 
12  –дәріс.  Графтардың  изоморфтылығы.  Графтардың  берілу 
тәсілдері. 
Графтардың  берілуі  дегеніміз  оның  төбелері  мен  қабырғаларынан 
тұратын  жиындарды  сипаттау  болып  табылады.  Төбелер  мен  қабырғаларды 
жай ғана нөмірлеуге болады. 
1. Төбелері: 
v
1
, 
v
2
,..., 
v
n
; Қабырғалары: e
1
, e
2
, …. ,e
n 
2.  Граф  құрылымы  туралы  ақпарат  бинарлы  қатынас  матрицасы 
арқылы  да  беріледі.  Мысалы,  G=‹M,R›  граф  болсын.  М  төбелер  жиыны 
М={a
1
, a
2
,…,a
n
}. R граф төбелерінің арасындағы бинарлы қатынас болсын. G-
графының  сыбайлас  матрицасы  деп  төмендегідей  анықталған  n  ретті  A 
G 
={A
ij
} матрицаны айтамыз. 
R
a
a
егер
R
a
а
егер
а
j
i
j
i
ij
)
,
(
,
0
)
,
(
,
1
 
н-графта a
i
, a
j 
 төбелері іргелес болады, егер A
ij
=1 немесе A
ji
=1, яғни н-графта 
A
ij
=   A
ji
=1 . Егер G мультиграф болса оның іргелестік A
G
 матрицасының A
ij
 
элементтері  анықтама  бойынша  a
i
  төбесінен  шығып  a
j
  төбесіне  кіретін 
доғалардың санына тең (i,j {1,…,n}). 
 
Егер  А
G
–н-граф  болса,  оның  іргелестік  матрицасы  А
G
-симметриялы, 
яғни 
G
T
G
A
A
.  Төбені  өзімен  қайта  қосатын  доға–ілгек  деп  аталады.  Егер 
графта  ілгек  доғалар  болмаса,  онда  іргелестік  A
G
  матрицаның  бас 
диагоналінде нөлдік элементтер тұрады.  
3. Графының инциденттік матрица арқылы берілуі. 
Анықтама:  mxn  мөлшерлі  инциденттік  матрица  B
G
  деп  төмендегі 
ережемен анықталатын матрицаны айтамыз. G-н-граф болса 

болса
керісінше
егер
болса
инцидентті
тµбесіне
v
ќабырѓа
e
егер
B
j
i
ij
0
,
1
0
0
*
0
*
0
0
G
A
 
G орграф болса 
;
0
;
,
),
0
,1
,1
(
;
,1
;
   
,1
жа аа аа
аал а
болса
т б
инцидентті
о а
v
ал
ілгек
e
егер
сан
келген
кез
бас а
болса
со о
аабыр ааб
e
т б
v
егер
болса
басы
аабыр ааб
e
бе
т
v
егер
В
j
i
i
j
i
j
ij

 
4. Графтың қабырғаларының тізімімен  берілуі: 
Граф  екі  бағанмен  беріледі:  біріншісінде  барлық  қабырғалар  е
і
,  ал  оң 
жақ  бағанда  оған  инцидентті  төбелер  жазылады;  н-граф  үшін  төбелердің 
жазылу реті еркін түрде, ал орграф үшін қабырғаның басталатын төбесі 1-ші 
тұрады. 
1-мысал:  суреттегі  графты  іргелес  және  инциденттік  матрицалармен 
және қабырғалар тізімімен беру керек. 
 
G
1
 ,G
2
– графтары мен олардың инциденттік матрицалары 
 
G
1
, G
2 
графтарының сыбайлас (іргелес) матрицалары және қабырғалары 
мен  төбелерінің  тізімімен  берілуі.  G
1
-бағытталмаған  граф  болғандықтан 
төбелердің бағыты еркін түрде көрсетіледі 
G  графын  оның  әр  төбесіне  v
i 
  V(G)  сыбайлас  төбелердің  жиыны 
арқылы  да  өрнектеуге  болады.  Ол  жиынтықты  v
i
.  Төбесінің  аймағы  деп 
атайды және О(vi) деп белгілейді. Сонымен  
О(v
i
) = { v
j 
| [v
i
, v
j
 ]   V(G)}. 
G диграфын оның әр төбесіне vi   V(G) шығунемесе кіру аймақтарын 
көрсету арқылы да өрнектеуге болады: O-(vi)={vj| (vi, vj) E(G)}, 
O+(vi)={vj|(vj,vi) E(G)} . 
1. Қабырғаларының тізімі бойынша инцидентті матрица құру. 

Тізімнің  әр  жолы  сол  нөмірмен  алынған  матрица  жолына  сәйкес.  Н-
граф  үшін  тізім  жолында  инцидентті  матрица  жолындағы  1-ге  тең 
элементтердің (төбелердің) нөмірлері көрсетілген. 
Орграф  үшін  бұл  жолда  бірінші  болып  матрицаның  -1-ге  тең 
элементінің нөмірі, екіншісі болып  матрицаның 1-ге тең элементінің нөмірі 
көрсетіледі.  Тізім  жолындағы  нөмірлер  бірдей  болған  жағдайда,  инцидентті 
матрицаның жолындағы аталған элементке  2 қойылады. 
2. Іргелес матрица бойынша, қабырғалар тізімін құру. 
i-жол  мен    j-баған  қиылысуында  орналасқан  матрица  элементіне  әр 
қайсысында  i,j  нөмірлері  жазылған  қабырғалар  тізімінің 
ij
  жолы  сәйкес 
келеді.(
ij
=0  болсa  бір  де  бір  жол  жоқ).  н-граф  үшін  бұл  жолдар  іргелес 
матрицаның    тек  жоғарғы  оң  жақ  үшбұрышындағы  элементтерге  сәйкес 
болады,яғни  j>і  орындалатын 
ij
  элементтер  үшін,  ал  орграф  үшін  барлық 
ij
 элементтерді қарастыру керек. 
Салмақтанған графтар. 
Көп  есептерде  графтардың  төбесі  мен  доғалары  туралы  қосымша 
ақпарат  қажет  болады,  мысалы,  егер  граф  қалааралық  жолдарды  бейнелесе 
салмақтанған графтар қолданылады. 
Айталық    S
M
,  S
R 
-  таңбалар  жиыны  болсын.  f:  M→S
M   
(төбелерді 
таңбалау),  g:  R→S
R
  (доғаларды  таңбалау)  функциялары  G=  графын 
таңбалау  бөлінуі  деп  аталады.      G=  таңбаланған  немесе 
салмақтанған граф деп аталады. 
f(a)-a төбесінің салмағы деп, ал g(e) e доғасының салмағы деп аталады. 
Доға мен төбенің біреуінің ғана таңбалануы жиі кездеседі. 
Мысалы: Айталық M={a
1
, a
2
, a
3
, a
n
}, R={[a
1
a
2
], [a
2
 a
3
], [a
1
 a
4
], [a
2
 a
4
]}; 
f:M→C мұндағы, С- қалалар жиыны, g:R→W. 
f(a
1
)=Омск, f(a
2
)=Новосибирск, f (a
3
)=Кемерово, f (a
4
)=Павлодар 
g([a
1
  a
2
])=681;  g([a
2
  a
3
])=274,  g([a
1
  a
4
])=413;  g([a
2
  a
4
])=589.  Таңбалаған 
  графты–белгілі  бір  қалалар  арасындағы  ұзындығы  көрсетілген 
автомобиль  жолдарының  схемасы.  Салмақталған  графтардағы  доғалардың 
салмағы  туралы  ақпаратты  салмақ  матрицасы  арқылы  кескіндеуге  болады. 
W=(
ij
) – мұндағы 
ij
 – (a
i
,a
j
) доғасының салмағы жоқ доғалар әдетте ноль 
немесе 
  белгісімен  белгіленеді.  Қарастырылған  мысал  үшін  салмақтылық 
матрицасының түрі 
 
Графтарға қолданылатын амалдар. Графқа төбе қосу. 
G= графына а төбесін қосқаннан <М {a}, R> графы құралады. 
Графқа  доға  қосу  операциясының  нәтижесінде  <М {(a,b)}, 
R
{(a,b)}> графы құрылады. 

Графтан  доға  алу–R  доғалар  жиынынан  (a,b)  жұбы  алынады. 
 
Графтан  төбе алу операциясының нәтижесінде.  G  графынан  а  төбесі 
оған инцидентті доғалармен бірге алынады  деп айтады.  =a немесе c = a}> 
Графтың  a,b  төбелерін  теңестіру  деп  графтан  a,b  төбелерін  алып 
тастап мына тәртіппен төбе мен  қабырға қосу:  жаңа а
1 
төбесі мен (а
1
, с), егер 
(а, с)  R немесе (b, с)   R және (с, а
1
) доғасын егер (с, а)  R немесе (с, b)   
R  болса:<(M\{a,b}) {a
1
},  (R\{(с,  d)│c=a  немесе  d=a,  немесе  c=b,  немесе 
d=b})
{(a
1
,c)│(a,  c) R,  немесе  (b,  c) R} {(c,  a
1
)│(c,  a)R,  немесе  (c, 
b) R}). 
Алынған  граф  G  графынан  a,b  төбелерін  теңестіргеннен  алынды 
делінеді. 
a,b  төбелері  доғамен  қосылса,  төбелерді  теңестіру  a,b  доғасын 
созғаннан алынады дейді. Мысалдар: Берілген=<{1,2,3,4},{[1,2],[2,3],,(3,4)}> 
графынан суреттегі G
1
-G
6
 графтары қандай операциялармен алынды? 
 
G графына 5 төбені қосқаннан G
1
 графы алынды. 
G графына (3,1)–доғасын қосқаннан G
2
 графы алынды. 
G графына (3,2) доғасы алынады G
3
 графы алынды. 
G графына 2 – төбені алғаннан G
4
 графы алынды. 
G графының (1,4) төбелерін теңестіргеннен G
5 
 графы алынды. 
G графының  (2,3)  доғасын қысқаннан G
6 
 графы алынды. 
G
=2
\R
Id
М
> графы ілгексіз G= графының толықтырушы 
графы деп аталады.  
Мысал: Айталық, G
1
=1
,R
1
>, G
2
=2
,R
2
> графтары берілсін. 
 
G= ; 
G
=2 
\R
Id
М
> 
Анықтама:  G
1
,  G
2 
графтарының  бірігуі  деп  G
1
UG
2
=1
UM
2
,R
1
UR
2
> 
графын айтады. 
Анықтама:ЕгерМ
2
∩М
2
=
онда  G
1
,G
2 
графының  қиылысуы  деп, 
G
1
∩G
2
=1
∩M
2
,R
1
∩R
2
> графын айтады. 
Анықтама:  G
1
, 
G
2 
графтарының  сақиналы  қосындысы  деп 
G
1
G
2
=1
UM
2
,R
1
R
2
>, мұндағы R
1
R
2
=( R
1
\R
2
)U(R
2 
\R
1
). 
Мысалы G
1
 және G
2
 графтары берілсін.  
G
1
= < {a
1
, a
2
, a
3
}, {[a
1
, a
2
], (a
2
, a
3
)}  >; 
G
2
= < {a
1
, a
2
, a
4
}, {(a
1
, a
2
, ), (a
4
, a
1
)}>; 

 
Табу керек: G
1
U G
2
, G
1
∩G
2
, G
1
G
2
? 
Шешуі: Анықтама бойынша:  
G
1
UG
2
=<{a
1
, a
2
, a
3
, a
4
},{[a
1
, a
2
], (a
2
, a
3
), (a
4
, a
1
)}>; 
G
1
∩G
2  
= < {a
1
, a
2
}, {(a
1
, a
2
)} >. 
G
1
G
2
=<{ a
1
, a
2
, a
3
, a
4
}, {( a
2
, a
1
), (a
2
, a
3
), (a
4
, a
1
)} >; 
G
1
, G
2
 графтарының қосылуы деп 
G
1
+ G
2
 =
.
b
a
,
M
b
,
M
a
b
,
a
R
R
,
M
M
2
1
2
1
2
1



 
 
Мына суреттің а пунктіндегі G
1
, G
2
 графтарының қосындысы б пунктте 
көрсетілген. 
 
G
1
,  G
2
  графтарының  көбейтіндісі  деп  G
1
xG
2
=1
xM
2
,  R>,  мұндағы 
((a
1
,b
1
),  (a
2
,  b
2
)) R  тек  сонда  ғана,  егер  a
1
=a
2
  және  (b
1
,b
2
) R
2 
  немесе  b
1
=b
2
 
және (a
1
,a
2
)   R
1
. 
Ішкі графтар және графтардың бөлігі. 
Граф бөліктерімен операциялар. 
Анықтама:  Егер  М
1
М  және  R
1
R∩(M
1
)
2
  болса,  яғни  G
1
  графының 
төбелер  жиыны  G  графы  төбелер  жиынына,  ал  G
1 
қабырғалар  жиыны  G 
графының қабырғалар жиынына жатса G
1
- G бөлігі деп аталады. 
Анықтама  Айталық.  G=,G
1
=1
,R
1
>  графтары  берілсін.  Егер 
М
1
М  және  R
1
=R∩(M
1
)
2
  болса,  яғни  G
1
  графының  төбелер  жиыны  G-ң 
төбелер жиынында жатса ал G
1
-ң доғалары екі жағымен де G графына жатса 
G
1
–G графының ішкі графы деп аталады. 
Анықтама.Егер  Н  графының  төбелер  жиыны  V(H)  мен  қабырғалар 
жиыны  E(H)  G  графының  сәйкесінше  төбелері  мен  қабырғалар  V(G),  E(G) 
жиындарында  жатса 
)
(
)
(
G
V
H
V
  және 
)
(
)
(
G
E
H
E
,  онда  Н  графы  G 
графының бөлігі деп аталады 
G
H
. 
Анықтама Егер 
)
(
)
(
G
V
H
V
, G графының бөлігі  Н суграф деп аталады. 
Егер  G  графының  кез  келген  төбесі    Н    графының  ең  болмаса  бір 

қабырғасына  инцидентті  болса  ,  онда  бағытталмаған  Н    графы  G  графын 
жабады дейміз. 
 
Мысалы:а) G=<{1, 2, 3, 4}, {[1, 2], [1, 3], [1,4], [2,3], [3,4]}> 
б)  G
1
=<{1,  2,  3},  {[1,  2],  [1,  3],  [2,  3]}>-G  ішкі  графы  (М
1
МR
1
, 
R
1
=R∩R
1
) 
в) 
G
11
=<{1,2,3},{[1,2],(2,3)}>-G 
графының 
бөлігі 
(M
11
М,R
11
R∩(M
11
)
2
) 

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

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