1 пєнініњ ОЌу программасы syllabus

-Дәріс тақырыбы: Графтар. Қасиеттері. Операциялар (2 сағат)

жүктеу 19,56 Mb.

бет	24/34
Дата	31.05.2018
өлшемі	19,56 Mb.
	#18555

1 ... 20 21 22 23 24 25 26 27 ... 34

Графтардың берілу тәсілдері.

11-Дәріс тақырыбы: Графтар. Қасиеттері. Операциялар (2 сағат)

Дәріс конспектісі:

Графтар теориясының элементтері

Граф ұғымы. Көптеген қолданбалы есептерде айналамызды қоршаған ортаның әртүрлі объектілер арасындағы байланыстар жүйесі зерттеледі. Объектілер төбелер деп аталып, нүктелер арқылы белгіленеді, ал төбелер арасындағы байланыстар доғалар деп аталып, сәйкес нүктелерді қосатын бағытталған түзулермен белгіленеді. Қала көшелерін граф арқылы кескіндеуге болады: көше қиылысуларын графтардың төбесі деп, ал көшелерді доғалар деп алуға болады;

Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф төбелері, ал операцияның орындалу кезегін көрсететін стрелкалар доғалар.

Анықтама: G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R

M² элементтері доғалар деп аталады. Сонымен граф төбелері дегеніміз –айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз оларды натурал сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. Граф қабырғаларын әдетте латын әріптерімен белгілейді. 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₁, v₂, v₃, v₄; Қабырғалары:e₁,e₂, e₃, e₄ e₅; Бұл графтағы v₁ мен v₂; v₂ мен v₃; v₃ пен v₄; v₄ пен v₅ іргелес төбелер, v₁, v₃- сыбайлас емес. Сол сияқты: e₁,e₂; e₂,e₃; e₃,e₄; e₄,e₁; e₁,e₅; e₂,e₅; e₃,e₅; e₄,e₅; - қабырғалары сыбайлас.e₁,e₃; e₂,e₄;- сыбайлас емес қабырғалар.

Егер G={M,R} орграфындағы әр (a,b)

R доғасына, (b,a) жұбын қосса нәтижесінде берілген G графына сәйкес Н-граф шығады, оны F(G) деп белгілейді.

Анықтама: Егер граф элементтерінің (төбелері мен қабырғалары) жиыны ақырлы болса, графта ақырлы деп, ал қабырғалар жиыны бос болса, бос граф деп аталады.

Ілгексіз, әрі еселі қабырғалары жоқ және әрбір төбелер жұбы қабырғамен қосылған граф толық граф деп аталады.

Анықтама: Берілген G графындағыдай төбелері және G графына қосқанда оны толық графқа айналдыра тындай ғана қабырғалары бар графы G-ң толықтауыш графы деп аталады.

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

Анықтама: Еселі доғаларсыз бағытталған графты көбіне диграф деп атайды. G= - V-бос емес (төбелерінің) жиын; E

VxV;

Анықтама G н-графының

төбесіне инцидентті қабырғалар саны () V

төбесінің локальді дәрежесі деп аталады. Н-графта барлық төбелердің

G₁-ге кононды граф.

локальды дәрежелерінің қосындысы графтың 2 еселенген қабырғалар санына тең, яғни жұп сан. Ілгек төбе дәрежесіне 2-ге тең үлес қосады:

Анықтама Егер локальды дәреже жұп болса,төбе жұп деп,ал тақ болса төбе тақ төбе деп аталады. 0 дәрежелі төбе оқшауланған төбе деп аталады.

V= {1,2,3,4}.

; Мұндағы,

= 7 –графтың қабырға ларының саны. Бағытталған графтың төбелері үшін 2 локаль ды дәреже анықталады.

төбесінен шығатын қабырғалар саны.

төбесіне кіретін қабырғалар саны. Бағытталған графта барлық төбелердің локальды

дәрежелері

осы графтың қабырғалар санына тең, демек олар өзара

тең

; Мысалы:

1-ші,2-ші типті дәрежелер қосындысы бірдей қабырғалар санына тең..Егер G1 төбелері мен қабырғалары G2 графының төбелері мен қабырғалары бірдей болса,яғни: Vl = V2, El = E2 болса, онда Gl = G2

. Графтардың берілу тәсілдері.

Графтардың берілуі дегеніміз оның төбелері мен қабырғаларынан тұратын жиындарды сипаттау болып табылады. Төбелер мен қабырғаларды жай ғана нөмірлеуге болады.

1. Төбелері:

₁,

₂, ..... ,

_n; Қабырғалары: e₁, e₂, …. ,e_n

2. Граф құрылымы туралы ақпарат бинарлы қатынас матрицасы арқылы да беріледі. Мысалы, G=‹M,R› граф болсын. М төбелер жиыны М={a₁, a₂, … ,a_n}.R граф төбелерінің арасындағы бинарлы қатынас болсын. G- графының сыбайлас матрицасы деп төмендегідей анықталған n ретті A _G={A_ij} матрицаны айтамыз.

н-графта 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- симметриялы, яғни =A_G. Төбені

өзімен қайта қосатын доға – ілгек деп аталады. Егер графта ілгек доғалар болмаса, онда

іргелестік A_G матрицаның бас диагоналінде нөлдік элементтер тұрады.

3. Графының инциденттік матрица арқылы берілуі.

Анықтама: mxn мөлшерлі инциденттік матрица B_G деп төмендегі ережемен анықталатын матрицаны

айтамыз. G-н-граф болса

G орграф болса

4. Графтың қабырғаларының тізімімен берілуі:

Граф екі бағанмен беріледі: біріншісінде барлық қабырғалар е_і, ал оң жақ бағанда оған инцидентті төбелер жазылады; н-граф үшін төбелердің жазылу реті еркін түрде, ал орграф үшін қабырғаның басталатын төбесі 1-ші тұрады.

1-мысал: суреттегі графты іргелес және инциденттік матрицалармен және қабырғалар тізімімен беру керек.

G₁ ,G₂– графтары мен олардың инциденттік матрицалары

G₁, G₂графтарының сыбайлас (іргелес) матрицалары және қабырғалары мен төбелерінің тізімімен берілуі. G₁-бағытталмаған граф болғандықтан төбелердің бағыты еркін түрде көрсетіледі
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 нөмірлері жазылған қабырғалар тізімінің

жолы сәйкес келеді.(

=0 болсо бір де бір жол жоқ). н-граф үшін бұл жолдар іргелес матрицаның тек жоғарғы оң жақ үшбұрышындағы элементтерге сәйкес болады,яғни j>і орындалатын

элементтер үшін, ал орграф үшін барлық

элементтерді қарастыру керек.

жүктеу 19,56 Mb.

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

1 ... 20 21 22 23 24 25 26 27 ... 34