Informatică
Informatică BAC: parcurs cu 50 de lecții
Pregătește informatica pentru BAC în 50 de lecții: algoritmi, tablouri, texte, subprograme și grafuri. Exersează prin exemple, grile și fișe de verificare.
Hola25
3 min citire
21 octombrie 2026
Înapoi la blog
21 octombrie 2026
7 min citire
Problemele despre componente conexe la BAC cer adesea un număr minim sau maxim de muchii. Primul pas este să stabilești ce se păstrează fix: numărul vârfurilor, numărul componentelor, dimensiunile lor sau graful concret de la care pornești. Aceeași formulă nu răspunde tuturor acestor întrebări.
Lecția privește grafurile simple neorientate de la matematică-informatică. Considerăm n vârfuri și k componente conexe, cu k între unu și n. Vârfurile izolate se numără și ele drept componente. Folosește această convenție când rezolvi un subiect de BAC și verifică dacă enunțul fixează suplimentar dimensiunea fiecărei componente.
O componentă conexă este un grup maximal de vârfuri între care există lanțuri. Cuvântul maximal înseamnă că nu poți adăuga un alt vârf al grafului păstrând această proprietate. Componentele nu se suprapun și acoperă toate vârfurile.
Două vârfuri din componente diferite nu sunt unite printr-o muchie. Dacă ar exista o asemenea muchie, ea ar permite un lanț între cele două grupuri, care ar forma de fapt o singură componentă.
Un vârf izolat formează o componentă cu un singur vârf și zero muchii. Nu îl ignora doar pentru că nu participă la niciun segment din desen. Numărul componentelor se referă la toate vârfurile declarate.
O componentă cu s vârfuri are nevoie de cel puțin s minus unu muchii pentru a fi conexă. Minimul este atins de un arbore. Pentru o componentă izolată, aceeași expresie dă zero, deci regula include și acest caz.
Adunând minimele tuturor componentelor, suma dimensiunilor este n și scădem unu de k ori. Rezultă minimul n minus k muchii. El poate fi realizat alegând câte un arbore pentru fiecare componentă.
Pentru șapte vârfuri și trei componente, minimul este patru muchii. O realizare are componente de dimensiuni trei, trei și unu: două lanțuri cu câte trei vârfuri și un vârf izolat. Fiecare lanț are două muchii, deci totalul este patru.
Dacă dimensiunile componentelor sunt date, maximul se obține făcând fiecare componentă completă. O componentă cu s vârfuri poate avea cel mult s înmulțit cu s minus unu, împărțit la doi, muchii.
Pentru dimensiunile trei, trei și unu, maximele sunt trei, trei și zero. Totalul este șase. Nu poți adăuga o muchie între componente, fiindcă ai reduce numărul lor și ai încălca cerința.
| Dimensiuni ale componentelor | Minim de muchii | Maxim cu aceste dimensiuni |
|---|---|---|
| 3, 3, 1 | 4 | 6 |
| 4, 2, 1 | 4 | 7 |
| 5, 1, 1 | 4 | 10 |
Toate rândurile au șapte vârfuri și trei componente. Minimul rămâne același, dar maximul depinde de distribuirea vârfurilor. Tabelul arată de ce trebuie citit atent ce anume fixează enunțul.
Dacă dimensiunile nu sunt impuse, maximul se obține cu o componentă completă de n minus k plus unu vârfuri și k minus unu vârfuri izolate. Componenta mare folosește toate vârfurile rămase după rezervarea unui vârf pentru fiecare dintre celelalte componente.
Numărul maxim este produsul dintre n minus k plus unu și n minus k, împărțit la doi. Pentru șapte vârfuri și trei componente, componenta mare are cinci vârfuri și zece muchii, iar celelalte două componente sunt izolate.
De ce nu este mai bine să împarți vârfurile egal? Mutarea unui vârf dintr-o componentă mai mică, dar cu cel puțin două vârfuri, într-una cel puțin la fel de mare crește numărul perechilor care pot fi unite. Repetarea mutării lasă o singură componentă mare și restul de dimensiune unu.
Pentru un graf concret cu k componente, trebuie adăugate cel puțin k minus unu muchii pentru a-l face conex. O muchie nouă poate uni cel mult două componente, deci poate reduce numărul lor cu cel mult unu.
Minimul este realizabil: alegi câte un reprezentant din fiecare componentă și legi componentele într-un lanț sau într-o structură de arbore. Muchiile adăugate între componente sunt inexistente inițial, tocmai fiindcă grupurile erau distincte.
Pentru patru componente sunt suficiente și necesare trei muchii noi. Nu contează câte muchii există deja în interiorul componentelor pentru acest minim. Contează câte grupuri separate trebuie reunite.
Un graf cu n vârfuri, m muchii și k componente poate fi redus la o pădure care păstrează aceleași componente. În fiecare componentă alegi un arbore care conține toate vârfurile ei. Pădurea rezultată are n minus k muchii.
Prin urmare, elimini m minus n plus k muchii. Acesta este numărul minim de eliminări necesare pentru a elimina toate ciclurile fără să schimbi componentele. Nu înseamnă că poți alege arbitrar orice asemenea mulțime de muchii: eliminările trebuie să păstreze conexitatea fiecărui grup.
De exemplu, pentru șapte vârfuri, opt muchii și două componente, pădurea finală are cinci muchii. Trebuie eliminate trei muchii alese astfel încât să dispară ciclurile, fără separarea componentelor.
Un graf cu n minus unu muchii nu este automat conex. Un triunghi și un vârf izolat au patru vârfuri și trei muchii, dar două componente. Triunghiul conține un ciclu, iar vârful izolat rămâne separat.
Afirmația corectă este că un graf conex cu n vârfuri și n minus unu muchii este arbore. Dacă lipsește ipoteza conexă, simpla egalitate numerică nu ajunge. La fel, un număr suficient pentru a construi un graf conex nu înseamnă că orice distribuție a acelor muchii este conexă.
Separarea dintre condiție numerică și proprietate structurală este utilă pentru învățarea prin înțelegere. Caută o justificare a legăturilor, nu doar o egalitate convenabilă.
| Cerință | Răspuns, în ipotezele precizate |
|---|---|
| Minim de muchii, n vârfuri și k componente | n − k |
| Maxim de muchii, doar n și k fixate | (n − k + 1)(n − k) / 2 |
| Muchii minime adăugate pentru conexitate | k − 1 |
| Muchii eliminate până la o pădure cu aceleași componente | m − n + k |
Înainte de calcul, scrie ce reprezintă fiecare literă și ce operație este permisă. Adăugarea de muchii pentru conexitate și eliminarea de muchii pentru înlăturarea ciclurilor sunt probleme diferite, chiar dacă folosesc aceleași date inițiale.
Un graf are zece vârfuri și patru componente. Minimul de muchii este șase. Maximul, dacă dimensiunile nu sunt fixate, este douăzeci și unu, realizat de o componentă completă cu șapte vârfuri și trei izolate.
Componentele au dimensiunile patru, trei și doi. Minimul este șase, iar maximul este zece: șase plus trei plus unu. Pentru a reuni graful, adaugi minimum două muchii.
Numărul componentelor este egal cu numărul vârfurilor. Toate vârfurile sunt izolate, deci există zero muchii. Minimul și maximul coincid.
Un graf cu șase vârfuri, șapte muchii și două componente trebuie făcut aciclic fără separare. Păstrezi patru muchii și elimini trei, alegând câte un arbore în fiecare componentă.
Da. Orice vârf din prima poate ajunge la orice vârf din a doua folosind lanțurile interne și noua muchie. Cele două grupuri devin o singură componentă.
Nu automat. Atunci însumezi maximele componentelor cu dimensiunile cerute. Concentrarea într-o componentă mare ar schimba datele problemei.
Oferă atât o limită justificată, cât și o construcție care o atinge. Pentru feedback pe demonstrație, poți consulta un profesor de informatică.
Official curriculum reference
Official curriculum reference (www.edu.ro)Primary university reference: degree sum, connectivity and tree definitions; examples and exercises original
Primary university reference: degree sum, connectivity and tree definitions; examples and exercises original (ocw.mit.edu)Folosim cookie-uri pentru a îmbunătăți experiența ta pe Hola25. Cookie-urile esențiale sunt necesare pentru funcționarea platformei. Poți personaliza setările pentru cookie-uri de analiză și marketing.
Politica de cookies | Politica de confidențialitatePregătește informatica pentru BAC în 50 de lecții: algoritmi, tablouri, texte, subprograme și grafuri. Exersează prin exemple, grile și fișe de verificare.
Înțelege complexitatea buclelor la BAC. Compară parcurgeri succesive, imbricate și împărțiri repetate, apoi justifică timpul și memoria algoritmului.
