3.3 Байланыстылық және күшті байланыстылық компоненталары

 

Егер (M, N, T) графтың кез келген екі төбесі арасында тізбе болса, онда бұл граф байланысты деп аталады. Әрбір графты байланыстылық компоненталары деп аталатын максималды байланысты ішграфтарға бөлектеуге болады. Графтың әртүрлі байланыстылық компоненталарының саны оның байланыстылық саны деп аталады.

Мысал 1 7 суретте көрсетілген граф үш байланыстылық компоненталардан тұрады.

Сурет 7. Байланысты емес граф.

 

Егер (M, N, T) графтың кез келген екі төбесі арасында жол бар болса, онда бұл граф күшті байланысты деп аталады. Әрбір графты күшті байланыстылық компоненталары деп аталатын максималды күшті байланысты ішграфтарға бөлектеуге болады. Графтың әртүрлі күшті байланыстылық компоненталарының саны оның күшті байланыстылық саны деп аталады.

7 суретте көрсетілген графтың  күшті байланыстылық саны 9 тең.