Componente conexe
Fie G=(X,U) un graf neorientat.
Se numește componentă conexă a grafului G un subgrafSubgraful este o partiționare a grafului inițial, obținut prin eliminarea unor noduri. al lui G maximal în raport cu proprietatea de conexitate.
Explicat altfel, subgrafurile („bucățile din graf”) care pot forma separat un graf conexÎntr-un graf conex orice 2 noduri sunt unite între ele printr-un lanț., se numesc componente conexe.
Să analizăm 2 grafuri neorientate:
Putem observa că:
- Primul graf neorientat poate fi împărțit în 4 subgrafuri conexe (cele încercuite), care alcătuiesc de fapt 4 componente conexe.
- Al doilea graf are doar 3 componente conexe, existând 3 subgrafuri care îndeplinesc proprietatea de conexitate.
Proprietăți componente conexe
Numărul maxim de componente conexe
Obținerea unui număr maxim de componente conexe se face prin izolarea unui număr maxim de noduri.
Dat fiind numărul de muchii, strategia pentru maximizarea componentelor conexe este de a folosi muchiile sub cât mai puține noduri, lăsând cât mai multe noduri izolate.
Din 9 noduri și 8 muchii obținem un maxim de 5 componente conexe.
Știind deja că între 4 noduri putem încadra un maxim de 6 muchii, iar între 5 noduri maxim 10, este clar ca ne sunt necesare 5 noduri pentru a folosi toate cele 8 muchii.
Înțelegem că, pentru a ști numărul de noduri necesare, este suficient să găsim cel mai mic n pentru care m ≤ n*(n-1)/2.
Transformarea în graf conex
Unui graf neorientat cu n noduri și p componente conexe îi sunt necesare minim p-1 muchii pentru a deveni graf conexÎntr-un graf conex orice 2 noduri sunt unite între ele printr-un lanț..
Cu alte cuvinte, transformarea în graf conex se face prin unirea componentelor conexe:
În acest exemplu, adăugarea unui număr minim de muchii pentru a obține un graf conex se face prin unirea celor 4 componente conexe cu 3 muchii (colorate în figură).
Un graf conex este format dintr-o singură componentă conexă. Un nod izolatUn nod este izolat dacă are gradul 0. reprezintă, la rândul lui, o singură componentă conexă.
Deducem astfel că un graf nul cu n noduri are n componente conexe, iar un arbore (graf conex aciclic), de exemplu, formează o singură componentă conexă.