Arbori: rădăcină aleasă, niveluri și construcții (doar matematică-informatică)

Pe scurt

1 minesențialul, de recitit oricând

Culorile din lecție:cifră, datăidee-cheie

• Doar la matematică-informatică.
• Tema lecției sunt itemii în care arborele nu e dat de-a gata cu o rădăcină. Ori o alegi tu, ori e descris prin reguli.
• Lecția de bază, cu vectorul de tați, este cea anterioară. Aici presupunem că poți desena un arbore.

Urmează · 1 min

Aceleași muchii, altă rădăcină

1 min

Un arbore dat prin muchii n-are încă sus și jos. Îl poți „ridica” de orice nod, iar acela devine rădăcină. Muchiile rămân, dar cine e tată și cine e fiu se schimbă.

Două observații rezolvă aproape tot:

• Dacă rădăcina e chiar x, toți vecinii lui x sunt fii ai lui x.
• Dacă rădăcina e altundeva, tatăl lui x este vecinul aflat pe drumul spre rădăcină. Restul vecinilor sunt fiii lui x.

Urmează · 1 min

Oficial: model 2026, II.2

2 min

Arbore cu 9 noduri și muchiile [1,2], [2,8], [2,9], [3,6], [4,6], [5,8], [6,8], [7,8]. Se cer două noduri care pot fi rădăcină, astfel încât nodul 8 să aibă doi frați.

8 trebuie să aibă un tată cu exact trei fii. Tatăl lui 8 e un vecin al lui: 2, 5, 6 sau 7.

• 5 și 7 au doar muchia cu 8, deci n-au alți fii.
• 2 are vecinii 1, 8, 9. Ca toți trei să-i fie fii, rădăcina trebuie să fie chiar 2.
• 6 are vecinii 3, 4, 8. La fel, rădăcina trebuie să fie chiar 6.

Răspuns: 2 și 6. Barem: câte 3 p pentru fiecare.

Urmează · 2 min

Oficial: sesiunea specială 2025, varianta 6, II.2

2 min

Vectorul de tați este (3,0,2,5,2,5,1,5), iar rădăcina curentă e 2. Se cer două noduri, altele decât rădăcina curentă, care pot fi rădăcină astfel încât nodul 4 să aibă aceiași frați.

Acum, 4 are frații 6 și 8, iar tatăl lor este 5. Tatăl trebuie să rămână 5, iar 6 și 8 să nu se mute. Asta se întâmplă dacă rădăcina e de partea cealaltă a lui 5, adică prin nodul 2. Acolo sunt 2, 3, 1, 7. Fără 2, rămân 1, 3, 7.

Barem: câte 3 p pentru fiecare dintre cele două valori, oricare dintre 1, 3, 7.

Urmează · 2 min

Oficial: niveluri și frunze

4 min

August 2023, varianta 7, II.2. Muchiile sunt [1,2], [2,3], [2,6], [3,4], [3,5]. Se cer nodurile care, alese rădăcină, dau un număr minim de niveluri.

Cel mai lung lanț are 3 muchii, de exemplu 1, 2, 3, 4. Mijlocul lui e format din 2 și 3. Dacă rădăcina e la mijloc, cel mai depărtat nod e cât mai aproape.

Răspuns: 2, 3. Barem: 6 p pentru răspunsul corect, numai 3 p dacă ai scris doar un nod corect și numai 4 p dacă ai scris și alte noduri în plus.

Rezervă iunie 2025, varianta 7, I.4. Muchiile sunt [1,2], [1,3], [2,4], [2,5], [2,6]. Se cer două noduri care, alese rădăcină, dau trei frunze.

Nodurile de grad 1 sunt 3, 4, 5, 6: patru capete. Dacă rădăcina e unul dintre ele, el nu mai e frunză, deci rămân trei. Dacă rădăcina e 1 sau 2, rămân patru frunze. Dintre variante, doar 4, 6 merge, varianta d.

Urmează · 4 min

Oficial: arbore transformat în graf eulerian

2 min o întrebare la final

Simulare 2023, II.2. Vectorul de tați este (4,1,1,0,7,4,4). Se cer trei muchii care, adăugate, fac graful eulerian.

Muchiile sunt [4,1], [1,2], [1,3], [7,5], [4,6], [4,7]. Gradele sunt:

Nodurile cu grad impar sunt 1, 2, 3, 4, 5, 6. Le grupezi în perechi, fără muchii deja existente: [2,3], [1,6], [4,5]. Toate gradele devin pare, iar graful rămâne conex.

Barem: 6 p pentru o soluție corectă. Numai 2 p dacă ai adăugat cel puțin o muchie cu extremități cu grad inițial impar, fără să obții un graf eulerian, și numai 4 p dacă ai obținut un graf eulerian, dar numărul de muchii adăugate nu e cel cerut.

Urmează · 2 min

Oficial: arbori descriși prin reguli

9 min o întrebare la final

August 2025, varianta 4, I.5. Arbore cu 50 de noduri, rădăcina 1, iar tatăl lui i este [i/2]. Se cere lungimea lanțului elementar dintre 32 și 23.

Urci din ambele capete, până la primul nod comun.

• 32, 16, 8, 4, 2: 4 muchii.
• 23, 11, 5, 2: 3 muchii.

Lungimea e 7, varianta b.

Model 2027, I.5. Arbore cu cinci niveluri. Nodurile de pe nivelul 2 au câte patru fii, nodurile de pe același nivel au același număr de fii, iar niveluri diferite au numere diferite. Se cere numărul de noduri de pe ultimul nivel, pentru un total minim.

Ultimul nivel, nivelul 4, nu are fii, deci numărul 0 e luat. Pentru nivelurile 0, 1, 3 ai nevoie de numere diferite, nenule, diferite de 4: cele mai mici sunt 1, 2, 3.

Valoarea mare trebuie să fie cât mai jos, deci 3 merge pe nivelul 3, iar 1 și 2 pe primele două. Totalul este 36, cel mai mic posibil. Răspuns: 24, varianta B. Oricum le-ai așeza pe 1, 2, 3, ultimul nivel are 1·2·4·3 noduri, deci tot 24.

Simulare 2026, I.5. Arbore cu 7 noduri, rădăcina 3. Pentru un nod i, numărul de fii e 0 dacă e frunză, altfel i-1. Se cere numărul maxim de frați ai lui 1.

Sunt 6 muchii, deci suma fiilor este 6. Nodul 3 are 2 fii. Rămân 4 fii de repartizat. Nodul 1 e sigur frunză, pentru că 1-1 = 0. Dacă nodul 5 e interior, are 4 fii, toți cei rămași. Pui 5 fiu al lui 3, iar pe 1 fiu al lui 5: are 3 frați. Un tată cu mai mulți fii nu există, pentru că nodul 6 ar avea 5 fii, iar nu mai sunt atâția. Răspuns: 3, varianta c.

August 2026, varianta 1, I.5. Se pornește de la un nod cu eticheta 4 și se adaugă, pe rând, frunzele 2, 3, 1, 5, 7, 6. Fiecare nod nou poate avea cel mult un frate, iar diferența față de eticheta tatălui trebuie să fie minimă. Se cere numărul minim de niveluri.

Când două variante au aceeași diferență, alegi tu, iar de aici vine minimul.

Nivelurile sunt 0, 1, 2, deci 3, varianta b.

Urmează · 9 min

Ce se cere la BAC

2 mincum apare la examen

Urmează · 2 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Crezi că tații rămân aceiași după ce schimbi rădăcina.
• Uiți cazul în care rădăcina e chiar nodul despre care vorbește enunțul.
• Propui rădăcina curentă, deși enunțul o exclude.
• Scrii noduri în plus, când se cer toate nodurile: la august 2023 rămâi cu 4 p din 6.
• Adaugi o muchie deja existentă, când faci graful eulerian. Lucrările precizează că două muchii diferă prin cel puțin o extremitate.
• Alegi prima variantă la egalitate, fără să te uiți ce cere enunțul: minim sau maxim.

Urmează · 1 min