Componente conexe

Să analizăm 2 grafuri neorientate:

Observăm 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.

Un graf conex este format dintr-o singură componentă conexă. Un nod izolat reprezintă, la rândul lui, o singură componentă conexă.

Deducem astfel că un graf nul cu $n$ noduri are $n$ componente conexe, iar spre exemplu un arbore (graf conex aciclic), formează o singură componentă conexă.

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 toate muchiile sub cât mai puține noduri, lăsând cât mai multe 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.

Cu alte cuvinte, transformarea în graf conex se face prin unirea componentelor conexe.

În acest exemplu, dacă trebuie să adăugăm un număr minim de muchii pentru a obține un graf conex, vom realiza acest lucru prin unirea celor 4 componente conexe cu 3 muchii (colorate în imagine).