Анықтама: G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R M2 элементтері доғалар деп аталады. Сонымен граф төбелері дегеніміз –айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз оларды натурал сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. Граф қабырғаларын әдетте латын әріптерімен белгілейді. 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 төбе сыбайлас ( бүйірлес) деп аталады.
Анықтама: Төбелердің бір жұбына инцидентті доғалар еселі немесе параллель доғалар деп аталады
Анықтама: Еселі доғалары бар граф мультиграф деп аталады.
Анықтама: Шығатын және кіретін төбесі біреу болатын доға ілгек деп аталады.
1
№8 дәріс
Қарастырылатын сұрақтар (дәріс жоспары):
Графтарға қолданылатын амалдар.
Граф бөліктеріне қолданылатын амалдар.
Дәрістің қысқаша мазмұны:
G= графына а төбесін қосқаннан <М {a}, R> графы құралады.
Графқа доға қосу операциясының нәтижесінде <М {(a,b)}, R {(a,b)}> графы құрылады.
Графтан доға алу–R доғалар жиынынан (a,b) жұбы алынады. Графтан төбе алу операциясының нәтижесінде. G графынан а төбесі оған инцидентті доғалармен бірге алынады деп айтады. Графтың a,b төбелерін теңестіру деп графтан a,b төбелерін алып тастап мына тәртіппен төбе мен қабырға қосу: жаңа а1 төбесі мен (а1, с), егер (а, с) R немесе (b, с) R және (с, а1) доғасын егер (с, а) R немесе (с, b) R болса:<(M\{a,b}) {a1}, (R\{(с, d)│c=a немесе d=a, немесе c=b, немесе d=b}) {(a1,c)│(a, c) R, немесе (b, c) R} {(c, a1)│(c, a)R, немесе (c, b) R}).
Алынған граф G графынан a,b төбелерін теңестіргеннен алынды делінеді.
a,b төбелері доғамен қосылса, төбелерді теңестіру a,b доғасын созғаннан алынады дейді. Мысалдар: Берілген=<{1,2,3,4},{[1,2],[2,3],,(3,4)}> графынан суреттегі G1-G6 графтары қандай операциялармен алынды?
G графына 5 төбені қосқаннан G1 графы алынды.
G графына (3,1)–доғасын қосқаннан G2 графы алынды.
G графына (3,2) доғасы алынады G3 графы алынды.
G графына 2 – төбені алғаннан G4 графы алынды.
G графының (1,4) төбелерін теңестіргеннен G5 графы алынды.
G графының (2,3) доғасын қысқаннан G6 графы алынды.
=2\R IdМ> графы ілгексіз G= графының толықтырушы графы деп аталады.
Мысал: Айталық, G1=1,R1>, G2=2,R2> графтары берілсін.
