Graf neorientat conex

Avem următoarele 2 grafuri neorientate:

Pe rând, despre grafuri, putem spune:

1. Este un graf neorientat conex . Găsim câte un lanț care să unească oricare două noduri (vârfurile se unesc două câte două);
2. Este un graf neorientat neconex . Nu putem găsi un lanț între orice două vârfuri ale grafului.

Existența unui nod izolat va invalida întotdeauna proprietatea de graf conex. El nu are legătură cu niciun alt nod din graf.

Tot în exemplul anterior observăm la graful neconex că se împarte în 3 subgrafuri conexe (nodul izolat $8$ este și el tot un subgraf conex). Aceste subgrafuri sunt de fapt numite componente conexe.

Numărul minim de muchii

Numărul minim de muchii pe care le poate avea un graf neorientat conex cu $n$ noduri este $n-1$.

Un astfel de graf cu număr minim de muchii se mai numește și graf conex minimal și stă la baza noțiunii de arbore. În acest graf dacă eliminăm orice muchie vom pierdem proprietatea de conexitate.

Exemple de grafuri conexe minimale:

Ambele grafuri sunt conexe și aciclice. Prin urmare, putem spune că sunt și arbori.

Graf parțial conex

Putem elimina un maxim de $m-(n-1)$ muchii dintr-un graf neorientat conex cu $n$ noduri si $m$ muchii pentru a obține un graf partial conex al acestuia.

Deducție: Din totalul de $m$ muchii, vom scădea cele $n-1$ muchii minime pe care le poate avea un graf conex; astfel, rămânem cu un număr maxim de muchii pe care le putem elimina pentru ca graful parțial obținut să fie tot conex.

Acest tip de calcul este des întâlnit în exercițiile de tip grilă unde se cere să se determine numărul maxim de muchii ce pot fi eliminate pentru a păstra proprietatea de conexitate a grafului.