Қазақстан республикасының білім және ғылым министірлігі

жүктеу 21,8 Mb.

бет	89/214
Дата	09.01.2018
өлшемі	21,8 Mb.
	#7265
түрі	Мазмұндама

1 ... 85 86 87 88 89 90 91 92 ... 214

н-графта 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 графын оның әр төбесіне

жүктеу 21,8 Mb.

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

1 ... 85 86 87 88 89 90 91 92 ... 214