Ce este o diagramă arborescentă?

Lecția pe scurt · clasa a X-a · Diagrame arborescente

Este un desen care pune în ordine alegerile făcute una după alta. Pornești dintr-un punct de plecare, tragi câte o linie pentru fiecare variantă a primei alegeri, apoi din fiecare capăt câte o linie pentru variantele următoare. Numărul posibilităților este numărul capetelor finale, adică al drumurilor complete. Când din fiecare punct pleacă tot atâtea linii, rezultatul se obține înmulțind; când ramurile mari diferă între ele, se calculează separat și se adună.

O diagramă arborescentă (arbore) organizează alegerile succesive dintr-o problemă de numărare: rădăcina e situația de dinaintea oricărei alegeri, o ramură e o alegere concretă, un nod e un punct la care ai ajuns după una sau mai multe alegeri, iar o frunză e o posibilitate completă. Regula de citire: numărul posibilităților este numărul frunzelor, adică al drumurilor distincte de la rădăcină la capăt.

Când arborele este uniform — din fiecare nod al unui nivel pleacă același număr de ramuri — numărul frunzelor este produsul numerelor de ramuri: dacă la etapa întâi ai $2$ variante și la a doua $3$ , ai $2 \cdot 3 = 6$ frunze. Când arborele e neuniform, ramurile mari (care oferă un număr diferit de variante) se tratează separat, iar rezultatele se adună.

Arborele mai arată clar și alte două lucruri: diferența dintre «cu repetiție» (oferta rămâne aceeași la fiecare nivel) și «fără repetiție» (oferta scade cu unu), respectiv dacă ordinea contează — testul e simplu: dacă schimbi între ele două elemente alese și obții altceva, ordinea contează; dacă nu, fiecare grup a fost numărat de mai multe ori.

De reținut

numărul posibilităților = numărul frunzelor
arbore uniform: se înmulțesc numerele de ramuri
ramuri mari diferite: se calculează separat și se adună

Greșeala tipică

Se păstrează același număr de ramuri la fiecare nivel și atunci când elementele nu se repetă. Fiecare alegere scoate o variantă din ofertă, deci nivelurile următoare au cu una mai puțin.

Exerciții din această mini-lecție

O cofetărie are $3$ mărimi de pahar și $4$ arome de înghețată. Câte comenzi (mărime, aromă) există, desenate ca un arbore uniform?
- a) $12$
- b) $7$
- c) $3$
- d) $4$
Vezi răspunsul

Răspuns corect: a) $12$

Arborele are $3$ ramuri la primul nivel (mărimile) și, din fiecare, $4$ ramuri (aromele), deci $3 \cdot 4 = 12$ frunze — atâtea comenzi diferite.
O firmă de curierat merge din $A$ în $D$ prin $B$ sau prin $C$ . De la $A$ la $B$ sunt $3$ drumuri, de la $B$ la $D$ sunt $2$ ; de la $A$ la $C$ sunt $2$ drumuri, de la $C$ la $D$ sunt $4$ . Câte trasee complete există?
- a) $11$
- b) $14$
- c) $44$
- d) $9$
Vezi răspunsul

Răspuns corect: b) $14$

Arborele e neuniform: prin $B$ sunt $3 \cdot 2 = 6$ trasee, prin $C$ sunt $2 \cdot 4 = 8$ trasee. Un traseu trece ori prin $B$ , ori prin $C$ , deci se adună: $6 + 8 = 14$ .
Câte coduri de două cifre distincte se pot forma cu cifrele $1$ , $2$ , $4$ ?
- a) $3$
- b) $9$
- c) $6$
- d) $4$
Vezi răspunsul

Răspuns corect: c) $6$

Primul nivel are $3$ ramuri, al doilea are $2$ ramuri (cifra deja folosită dispare din listă): $3 \cdot 2 = 6$ coduri — $12, 14, 21, 24, 41, 42$ .

Întrebări conexe

Ce este o frunză într-o diagramă arborescentă?

Este capătul unui drum complet, adică o posibilitate întreagă, în care toate alegerile au fost făcute. Numărul frunzelor dă răspunsul problemei. Punctele intermediare, numite noduri, arată doar situații parțiale, iar liniile dintre ele, numite ramuri, arată câte o alegere concretă.

Ce se scrie pe o ramură și ce se scrie într-un nod?

Pe ramură se trece alegerea făcută, adică varianta luată la acel pas; în nod se trece situația la care ai ajuns după alegerile de până acolo. Etichetele acestea fac desenul citibil și arată de unde provine fiecare posibilitate.

Cum arată arborele când primul pas are mai multe variante decât al doilea?

Din punctul de plecare pornesc multe linii, iar din fiecare capăt al lor pleacă mai puține. Desenul iese lat la început și se îngustează spre dreapta. Forma lui spune dintr-o privire câte opțiuni are fiecare etapă.

Ce arată un arbore în care o ramură se oprește mai devreme?

Că pe acel drum una dintre alegeri nu mai era posibilă, deci posibilitatea se închide acolo. Capetele nu mai stau toate pe același nivel, iar numărarea nu se mai poate face prin înmulțire: se numără drumurile întregi unul câte unul.

Cum îmi dau seama că am uitat o ramură din desen?

Numeri liniile care pleacă din fiecare punct și le compari cu numărul de variante din enunț; dacă undeva ies mai puține, ai sărit una. Un al doilea control: capetele finale numărate trebuie să dea același rezultat ca înmulțirea pe niveluri.

De ce numărul posibilităților nu depinde de ordinea etapelor?

Fiindcă înmulțirea dă același rezultat oricum ai așeza factorii. Alegând întâi aroma și apoi mărimea paharului obții tot atâtea comenzi ca în ordinea inversă, chiar dacă desenul arată altfel. Ordinea etapelor se alege deci după cum e mai comod de desenat.

Oamenii mai întreabă și: diagramă arborescentă · arbore de numărare a posibilităților · cum număr cu ajutorul unui arbore · ramuri și frunze în numărare · desen pentru probleme de numărare