Grafuri-Conexitate

Conexitate.

Definiţie: Un graf se numeşte conex dacă pentru oricare două vârfuri x şi y diferite ale sale, există un lanţ care le leagă.

Definiţie: Se numeşte componentă conexă a grafului G=(X,U), un subgraf C=(X₁,U₁) conex al lui G care are proprietatea că nu există nici un lanţ în G care să lege un vârf din mulţimea X₁ cu un vârf din mulţimea X-X₁.

Exemplu 1: GRAF CONEX

GRAF CONEX - format dintr-o singură componentă conexă

(conţine toate nodurile grafului)

Exemplu 2: GRAF NECONEX

Graf NECONEX - alcătuit din trei componente conexe

Componenta conexa 1 conţine nodurile: 1,3,5,2,6

Componenta conexa 2 conţine nodurile: 4, 8

Componenta conexa 3 contine nodurile: 7