Анықтама: Егер бағытталмаған G графының әртүрлі а,в төбелері үшін (а,в) және в,а)маршруттары бар болса,онда G мықты байланысқан граф деп аталады.
Мұндай ұғымды мультиграф үшін де енгізуге болады.
Мысалдар:
Кез келген байланысты бағытталмаған графтар мықты байланысқан граф екендігін байқауға болады.
Маршрутпен байланысты төбелер қарапайым шынжыр мен де байланысқан болады.
Байланыстылық қатынастың эквиваленттік қасиеті бар және ол граф төбелерін өзара қиылыспайтын Vi, i=1, 2,…,k ішкі жиындарға бөлінуін анықтайды. Сондықтан барлық ішкі графтар G(Vi) байланысқан және олар графтың байланыс компоненттері деп аталады. Бағытталған G графы доғалардың бағыты ескерілмесе байланысқан делінеді, ал егер кез келген V1 төбесінен V11 төбесіне жол болса мықты байланысқан болады.
Мысалы, мына суреттегі графта екі {1, 2, 3, 4} және {5, 6, 7} байланыс компонент тері бар. Ал мына төмендегі суреттегі бағытталған графта{1,2,3},{4}және {5} төбелерімен берілген 3 мықты компоненттері бар.
 
Теорема. Кез келген графты қиылыспайтын байланыс компоненттерінің бірігуімен өрнектеуге болады. Графтың байланыс компоненттеріне жіктелуі бір мәнді анықталады. G=Ui G(Vi)
Сонымен, төбелердің байланысты компоненттері мен мықты компоненттер жиыны төбелер жиындарын бөлшектейді, ал байл. компоненттерінің саны бір мәнді анықталады.
Келесі теорема сыбайлас AG матрицасы бойынша G графының маршруттарын зерттеуге мүмкіндік береді.
Теорема. Егер AG-G графыың іргелестік матрицасы болса, онда  матрицасының (i, j)-ші элементі ұзындығы к-ға тең (аi,j)-маршруттарының санын анықтайды.
Достарыңызбен бөлісу: |
