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.

Grafuri neorientate neconex
  • 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.

Restaurarea conexitatii unui graf neconex