Graf conex

Un graf se numește graf conex dacă între oricare două noduri există cel puțin un lanțUn lanț este o succesiune de noduri unite prin muchii existente..

  Cu alte cuvinte, într-un graf neorientat conex toate nodurile „comunică între ele”, adică putem găsi o succesiune de muchii unite între orice 2 noduri.

Graf neorientat conex si Graf neorientat neconex
  • Primul graf este un graf neorientat conex. Este conex deoarece putem găsi un lanț care să unească oricare două noduri.
  • Al doilea graf este un graf neconex. Nu este conex deoarece se poate observa că este format „din mai multe bucăți”. De exemplu, spre nodul izolatUn nod este izolat dacă are gradul 0. 8 nu găsim niciun lanț, prin urmare graful nu este un graf conex.

  Pentru al doilea graf, cel neconex, putem observa din figură că se împarte în 3 subgrafuri 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..

Proprietățile grafului conex

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)..

Graf conex minimal


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.

Graf partial conex minimal