Question

numarul de componente conexe a unui graf cu 6 noduri si 7 muchii

Answer 1

Putem avea intre 1, 2 sau 3 componente conexe:

• Putem avea o minimul (o componenta conexa) legand toate nodurile (7 muchii sunt mai mult decat suficiente)
• Putem avea maximul incercand sa legam cat mai putine noduri prin cat mai multe muchii. Vezi imaginea atasata.

Numarul maxim de muchii pe care le putem avea intr-o componenta conexa cu n noduri este $\frac{n*(n-1)}{2}$. Deci intr-o componenta cu 4 noduri putem avea maxim 6 muchii. Intr-o componenta cu 5 noduri putem avea maxim 10 muchii. In concluzie putem folosi cele 7 muchii pentru a crea o componenta cu 5 noduri (acesta fiind numarul minim), lasand celelalte noduri izolate ca propriile componente conexa.