Fie G=(V, E) un graf neorientat, unde V are n elemente (n noduri) si E are m elemente (m muchii).
Definitie: G1=(V1, E1)este o componenta conexa daca:
- pentru orice pereche x,y de noduri din V1 exista un lant de la x la y (implicit si de la y la x)
- nu exista alt subgraf al lui G, G2=(V2, E2) care sa indeplineasca prima conditie si care sa-l contina pe G1
Exemplu:
Definitie: G1=(V1, E1)este o componenta conexa daca:
- pentru orice pereche x,y de noduri din V1 exista un lant de la x la y (implicit si de la y la x)
- nu exista alt subgraf al lui G, G2=(V2, E2) care sa indeplineasca prima conditie si care sa-l contina pe G1
Exemplu:
![Picture](/uploads/2/8/6/9/28694867/5897962.gif?196)
Graful alaturat are doua componente conexe:
-subgraful care contine nodurile:
1 2 3 4 5
-subgraful care contine nodurile:
6 7
-subgraful care contine nodurile:
1 2 3 4 5
-subgraful care contine nodurile:
6 7
Observatie: subgraful 1, 2, 3, 4 nu este componenta conexa pentru ( chiar daca pentru orice pereche x,y de noduri exista un lant de la x la y) deoarece exista subgraful 1, 2, 3, 4, 5 care il contine si indeplineste aceeasi conditie.