Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

Графтың байланыс компоненттері

жүктеу 0,75 Mb.

бет	12/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 ... 8 9 10 11 12 13 14 15 ... 23

лекция

Графтың байланыс компоненттері.

Анықтама. Бірдей емес екі төбесі ( , ) G маршрутпен қосылған ( -басы, -соңы) бағытталмаған G графы байланысты граф деп аталады.

Анықтама: Егер бағытталмаған 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 мықты компоненттері бар.

жүктеу 0,75 Mb.

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

1 ... 8 9 10 11 12 13 14 15 ... 23