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

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

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-симметриялы, яғни . Төбені өзімен қайта қосатын доға–ілгек деп аталады. Егер графта ілгек доғалар болмаса, онда іргелестік 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-ге тең элементінің нөмірі көрсетіледі. Тізім жолындағы нөмірлер бірдей болған жағдайда, инцидентті матрицаның жолындағы аталған элементке 2 қойылады.

2. Іргелес матрица бойынша, қабырғалар тізімін құру.

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