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

жүктеу 21,8 Mb.

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

1 ... 94 95 96 97 98 99 100 101 ... 214

Теорема .

Анықтама: Егер бағытталмаған G графының әртүрлі а,в төбелері үшін (а,в) және в,а)маршруттары бар болса,онда G мықты байланысқан граф деп аталады.

Мұндай ұғымды мультиграф үшін де енгізуге болады.

Мысалдар:

Кез келген байланысты бағытталмаған графтар мықты байланысқан граф екендігін байқауға болады.

Маршрутпен байланысты төбелер қарапайым шынжыр мен де байланысқан болады.

Байланыстылық қатынастың эквиваленттік қасиеті бар және ол граф төбелерін өзара қиылыспайтын V_i, i=1, 2,…,k ішкі жиындарға бөлінуін анықтайды. Сондықтан барлық ішкі графтар G(V_i) байланысқан және олар графтың байланыс компоненттері деп аталады. Бағытталған G графы доғалардың бағыты ескерілмесе байланысқан делінеді, ал егер кез келген V¹ төбесінен V¹¹ төбесіне жол болса мықты байланысқан болады.

Мысалы, мына суреттегі графта екі {1, 2, 3, 4} және {5, 6, 7} байланыс компонент тері бар. Ал мына төмендегі суреттегі бағытталған графта{1,2,3},{4}және {5} төбелерімен берілген 3 мықты компоненттері бар.

Теорема. Кез келген графты қиылыспайтын байланыс компоненттерінің бірігуімен өрнектеуге болады. Графтың байланыс компоненттеріне жіктелуі бір мәнді анықталады. G=U_i G(V_i)

Сонымен, төбелердің байланысты компоненттері мен мықты компоненттер жиыны төбелер жиындарын бөлшектейді, ал байл. компоненттерінің саны бір мәнді анықталады.

Келесі теорема сыбайлас A_G матрицасы бойынша G графының маршруттарын зерттеуге мүмкіндік береді.

Теорема. Егер A_G-G графыың іргелестік матрицасы болса, онда

матрицасының (i, j)-ші элементі ұзындығы к-ға тең (а_i,j)-маршруттарының санын анықтайды.

жүктеу 21,8 Mb.

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

1 ... 94 95 96 97 98 99 100 101 ... 214