Matricea de adiacenta a unui graf neorientat cu 2021 de noduri are 202 elemente nenule. indicati numarul minim de componente conexe ale grafuluim dar si cel maximm va rog mai explicit daca ca nu am inteles asa bine lectia asta
Răspunsuri la întrebare
Explicatie
Fiecare element al unei matrice de adiacenta poate avea valoarea 1 sau 0. Deci "202 valori nenule" inseamna 202 valori de 1.
Orice element de pe linia i si coloana j al matricei de adiacenta are valoarea 1 daca nodurile i si j sunt adiacente sau valoarea 0 daca nodurile nu sunt adiacente.
Stiind ca graful este neorietat, relatia de adiacenta dintre noduri este reciproca (a[i][j] = a[j][i]). Astfel, o muchie intre noduri corespunde a doua valori de 1 in matricea de adiacenta.
202 valori nenule in matricea de adiacenta corespund pentru 101 muchii in graf.
Deci cerinta devine :
"Un graf neorientat cu 2021 de noduri are 101 muchii. Indicati numarul minim de componente conexe".
Pentru a avea un numar minim de componente conexe trebuie sa legam cat mai multe noduri folosind cat mai putine muchii. Astfel, legam cat mai multe noduri intr-o configuratie de arbore (arborele este cel mai eficient mod de a lega cat mai multe noduri cu cat mai putine muchii pentru ca nu exista cicluri).
Stim ca un arbore cu n+1 noduri poate fi alcatuit folosind n muchii.
Avand la dispozitie 101 muchii putem 'lega' un arbore cu 102 noduri. Acest arbore reprezinta o componenta conexa. Restul nodurilor sunt noduri izolate si fiecare reprezinta propria componenta conexa.
Cate noduri izolate avem : 2021-102 = 1919 de noduri izolate
Cate componente conexe avem : 1919 (pentru fiecare nod izolat) + 1 (pentru arbore) = 1920 componente conexe
Raspuns : 1920 de componente conexe
Avand la dispozitie 101 muchii si stiind ca formula pentru numarul de muchii al unui graf complet ajungem la relatia :
n(n-1)/2 = 101
n(n-1)=202
unde n este numarul de noduri.
Daca in aceasta relatie n nu este nu numar intreg atunci luam cel mai mic numar intreg mai mare sau egal decat n.
14x13=182
15x14=210
Deci numarul de noduri folosite pentru a incerca construirea unei componente conexe care reprezinta un subgraf complet (sau aproape complet) este 15.
Astfel cele 15 noduri reprezinta o singura componenta conexa. Celelalte 2021-15=2006 noduri sunt izolate si fiecare reprezinta cate o componenta.
Astfel, avem in total numarul maxim de componente conexe = 2006+1 = 2007.