Граф және оның түрлері. Графтардың берілу тәсілдері. Графтарға қолданылатын амалдар. Граф бөліктеріне қолданылатын амалдар. Анықтама: G=(M,R) алгебралық жүйе граф деп аталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R M2 элементтері доғалар деп аталады. Сонымен граф төбелері дегеніміз – айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз оларды натурал сандармен белгілейміз. Ал граф қабырғалары оның кейбір төбелерін қосады. Граф қабырғаларын әдетте латын әріптерімен белгілейді. G= ‹M,R› графының геометриялық кескіні жазықтықта графтың әр төбесін нүкте арқылы белгілеп, егер (a,b) R болса а төбесінен b төбесіне доға жүргізу арқылы алынады.
Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы туралы ақпараттар маңызды емес.Төбелердің арасында байланыс бар екендігі және ол байланыс туралы ақпарат R доғалар жиынында екендігі болса болды.
Графтардың берілу тәсілдері. Графтардың берілуі дегеніміз оның төбелері мен қабырғаларынан тұратын жиындарды сипаттау болып табылады. Төбелер мен қабырғаларды жай ғана нөмірлеуге болады.
1. Төбелері: 1, 2,..., n; Қабырғалары: e1, e2, …. ,en 2. Граф құрылымы туралы ақпарат бинарлы қатынас матрицасы арқылы да беріледі. Мысалы, G=‹M,R› граф болсын. М төбелер жиыны М={a1, a2,…,an}. R граф төбелерінің арасындағы бинарлы қатынас болсын. G-графының сыбайлас матрицасы деп төмендегідей анықталған n ретті A G ={Aij} матрицаны айтамыз.
н-графта ai, aj төбелері іргелес болады, егер Aij=1 немесе Aji=1, яғни н-графта Aij= Aji=1 . Егер G мультиграф болса оның іргелестік AGматрицасының Aij элементтері анықтама бойынша ai төбесінен шығып aj төбесіне кіретін доғалардың санына тең (i,j {1,…,n}).
Егер АG–н-граф болса, оның іргелестік матрицасы АG-симметриялы, яғни . Төбені өзімен қайта қосатын доға–ілгек деп аталады. Егер графта ілгек доғалар болмаса, онда іргелестік AG матрицаның бас диагоналінде нөлдік элементтер тұрады.
3. Графының инциденттік матрица арқылы берілуі.
Анықтама: mxn мөлшерлі инциденттік матрица BG деп төмендегі ережемен анықталатын матрицаны айтамыз.
4. Графтың қабырғаларының тізімімен берілуі:
Граф екі бағанмен беріледі: біріншісінде барлық қабырғалар еі, ал оң жақ бағанда оған инцидентті төбелер жазылады; н-граф үшін төбелердің жазылу реті еркін түрде, ал орграф үшін қабырғаның басталатын төбесі 1-ші тұрады.
