Graf neorientat conex

Avem desenate 2 grafuri neorientate:

1. Primul graf este un graf neorientat conex. Putem găsi câte un lanț care să unească oricare două noduri (vârfurile se unesc două câte două);
2. Al doilea graf este neconex. Nu putem găsi un lanț care să unească toate nodurile grafului.
   În plus, doar din prezența unui nod izolatUn nod este izolat dacă nu are nicio muchie incidentă (are gradul 0). 8, ne dăm seama că graful nu este conex.

Tot pentru al doilea graf, cel neconex, putem observa (grafic) că se împarte în 3 subgrafuriSubgraful este o partiționare a grafului inițial, obținut prin eliminarea unor noduri. conexe (nodul izolat reprezintă și el tot un subgraf conex), numite și componente conexeO componentă conexă este un subgraf maximal în raport cu proprietatea de conexitate..

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 se mai numește și graf conex minimal (eliminând încă o muchie pierdem proprietatea de conexitate) și stă la baza noțiunii de arboreArborele este un graf conex aciclic (minimal)..

Iată două grafuri conexe minimale:

Ambele grafuri sunt conexe și aciclice. Prin urmare, putem spune că sunt și arboriArborele este un graf conex fără cicluri..

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țialEste graful cu aceleași noduri, dar mai puține muchii. 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.