top of page

 

 

Componente conexe

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

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.

            Definitie:Un graf G=(V, E)este conex daca pentru orice pereche x,y de noduri din V exista un lant de la x la y (implicit si de la y la x).

Observatii:

  • Un graf este conex daca admite o singura componenta conexa.

  • Graful anterior nu este conex pentru ca admite doua componente conexe.Graful urmator este conex:

 

 

 

 

 

 

 

 

 

 

 

 

 

bottom of page