Componentă conexă
Fie G=(X,U) un graf neorientat.
Se numește componentă conexă a grafului G un subgrafSubgraful unui graf conține mai puține noduri, păstrând toate muchiile valide. al lui G maximal în raport cu proprietatea de conexitate.
Explicat altfel, subgrafurile („bucățile”) 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.
- 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
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ă.
Unui graf neorientat cu n noduri și p componente conexe îi sunt necesare p-1 muchii pentru a deveni graf conexÎntr-un graf conex orice 2 noduri sunt unite între ele printr-un lanț..
În exemplul de mai jos, pentru a transforma graful neconex într-un graf conex, vom avea nevoie de un minim de 3 muchii, necesare pentru simpla unire a celor 4 componente conexe.
