Есептеу мысалы

1. Құрылымдық матрицасын құру

G=(X,U) граф берілген, мұндағы X – бүтін сандармен белгіленген шыңдар көпшілігі,

Х= {1,2,…,N};

U – латын әріптермен белгіленген қабырғалар көпшілігі;

U= {a,b,c,…,z}.

Құрылымдық матрица квадрат кестесі ретінде ұсынылады, жолдары мен бағаналар шыңдарға сәйкес болады, кірістер келесі шарттар бойынша анықталады:

 

 

Берілген граф бойынша (5 – сурет) құрылымдық матрицасын құрайық.

 

1 – кесте. Құрылымдық матрицасын

 

		а	b	с
			n		d
				m
					x

 

2. УК_i коммутация түйінінен УК_j түйініне дейін барлық мүмкін жолдарын табу.

Бұл үшін матрицаның i-бағана мен j- жолын өшіріп шығарылған анықтағышты математикалық логика заңдары бойынша есептейміз.

Мысал үшін бірінші шыңдан бесінші шыңына мүмкін жолдарын құрайық. Құрылымдық матрицаның бірінші бағана мен бесінші жолын өшіріп шығарылған минорды анықтағыш түрінде жазайық.

 

 

 

3. Граф шыңдар арасындағы белгіленген ранг бойынша жолдар көпшілігін құру.

Барлық белгіленген ранг n бойынша құрылымдық сұлбасын n-деңгейіне тұрғызу қажет. Мысал үшін r£2 рангтың барлық жолдарын есептейік. Барлық диагональдық элементтер В² бірлікке тең.

 

- 2 аспайтын ранг үшін 1 және 2 шыңдар

 

арасындағы жолдар:

 

элементті есептеу үшін бірінші жолды үшінші бағансына көбейту қажет.

 

- 1 және 3 шыңдар

 

арасындағы жолдар.

 

 

- 1 және 4 шыңдар арасындағы жолдар.

 

 

- 1 және 5 шыңдар арасындағы жолдар.

 

Матрицаның екінші жолдың элементтерін В² шығару үшін екінші жолды барлық бағаналарға көбейтеді.

 

 

 

 

 

Аналогия бойынша есептер шығарып екіден аспайтын рангпен барлық жолдар матрицасын шығарамыз.

 

 

Матрицаны үшінші деңгейіне тұрғызып, яғни В²хВ, ранг үштен аспайтын барлық жолдарын табамыз (яғни 1,2,3 ранг жолдары).

Жолдардың максималды ранг N-1 аспайды, мұндағы N- графтың шыңдар саны.