Дәрістер тезистері

Граф және оның түрлері. Графтардың берілу тәсілдері. Графтарға қолданылатын амалдар. Граф бөліктеріне қолданылатын амалдар

жүктеу 324,07 Kb. бет 12/14 Дата 15.12.2023 өлшемі 324,07 Kb. #44759

Навигация по данной странице:

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

Граф және оның түрлері. Графтардың берілу тәсілдері. Графтарға қолданылатын амалдар. Граф бөліктеріне қолданылатын амалдар. Анықтама: 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-ші тұрады. 2 14 №14 дәріс жүктеу 324,07 Kb. Достарыңызбен бөлісу:

©g.engime.org 2024
әкімшілігінің қараңыз