Графтар матрицасы

Графтар матрицасы

Графтың түрлі тəсілдермен берілетіндігін біз жақсы білеміз. Соның ішіндегі ыңғайлысы деп графтың матрица түрінде берілуін айтуымызға болады. Графтар матрицасы əр алуан түрде болады, бірақ ережеге сəйкес олардың бəрі графтардың негізгі қасиеттерін толық сипаттайды. Графтардың матрицалық түрде берілуі графты кез келген қиындық дəрежесіне қарамастан, жеткілікті жағдайда көрнекті етіп береді. Сонымен қатар, ең маңыздысы, графтар теориясының терминдерінде көрсетілгендей, графты матрица түрінде сипаттау ақпаратты өңдеу үдерісін автоматтандыруға мүмкіндік береді, яғни кез келген графтар матрицасын компьютерге енгізуімізге болады.

Біз n жолдан жəне m бағанадан тұратын матрица тұрғызайық. Матрицаның əрбір жолы графтың төбелеріне, ал бағаналары қабырғасына сəйкес болады. Графтардың матрица түрінде берілуінде олардың сыбайластық (төбесі мен қабырғасы (доғасы)) қатынасы немесе оқиғалық кескіні (төбесі мен қабырғасы (доғасы)) ескерілуі мүмкін. Енді өзімізге таныс матрицалар туралы айтып өтейік.

Сыбайлас матрицалар. Бұл n ретті (n-төбелер саны) квадратты матрица, мұнда бас диагональға нөлдер қойылады (егер графта ілмек болмаса), ал егер k төбесінде ілмек болса (жəне ілмектер саны p-ға тең), онда бас диагональда k нөмірі мен p саны тұрады).

Егер i төбесі j төбесімен бір қабырға арқылы байланысса, онда сыбайлас матрицасының [pic 1] элементі 1-ге тең болады. Егер бұл төбелер s қабырғалармен байланысса, онда [pic 2] болады.

Осыларға ұқсас түрде сыбайлас матрицалар бағытталған графтар мен мультиграфтар үшін де құрастырылады.

Анықтама 1. Бағытталмаған G графының төбелерінің сыбайлас матрицасы деп p = p(G) ( p-графтың төбелерінің саны) ретті [pic 3] квадрат матрицасын айтамыз, мұнда [pic 4] элементі [pic 5] жəне [pic 6] төбелерін қосатын қабырғалар санына тең.

[pic 7]

Сурет – 1

1.-суретте G(X, E) бағытталмаған граф, ал оның оң жағында A(G) төбелеріне сəйкес сыбайлас матрицасы келтірілген.

Жоғарыда айтылған анықтамадан тікелей осы түрдегі матрицаның негізгі қасиеттері шығады:

1. Бағытталмаған A(G) графының төбелерінің сыбайлас матрицасы квадратты жəне бас диагональға симметриялы болып табылады.

2. Бүтін оң сандар мен нөл саны A(G) матрицасының элементі болып табылады.

3. i-жолы бойынша (немесе i-бағанасы бойынша) A(G) матрицасы элементтерінің қосындысы сəйкес δ(xi) төбелерінің дəрежесіне тең.

Бағытталмаған граф төбелерінің сыбайлас матрицасының анықтамасынан жəне оның негізгі қасиеттерінен G(X, E) графы мен оның A(G) матрицасы арасында кейбір ерекше сəйкестіктер шығады. 1-суретте граф төбелерінің нөмірлері көрсетілген; жанында орналасқан матрица дəл осы нөмірлерге сəйкестендірілген.

Осы суретте G(X, E) графына басқа нөмірлеуді енгізсек (мысалы, сағат тіліне сəйкес өлшемдерді жылжытсақ), онда A(G) матрицасының жеке жолдары мен бағандарының арасында ауыстырулар болады. Сондықтан əрбір бағытталмаған графтар сыбайлас матрицаның төбелері жолдар мен бағандардың орнын ауыстырғанға дейін тек бір ғана дəлдігі болады деп айта аламыз.

Жəне керісінше, егер квадратты матрицаның элементтері бүтін оң сандар мен нөлден тұратын бас диагоналіне қатысты симметриялы болып, бағытталмаған граф изоморфталғанға дейін тек бір ғана дəлдікпен анықталса, онда матрица берілген төбелеріне қатысты сыбайлас матрица болып табылады.

1-суретте көрсетілгендей төбелерін басқаша нөмірлеп жəне алынған матрицамызды алдыңғы графта көрсетілген төбелерінің сыбайластық матрицасымен салыстырып, басқа өз бетінше графтың G(X, E) төбелерінен тұратын сыбайлас матрицаны құрайық.