Arbori la BAC: frunze, grade și număr de muchii

Într-un arbore neorientat cu cel puțin două vârfuri, frunzele sunt vârfurile de grad unu. Arborele are cu o muchie mai puțin decât numărul vârfurilor, iar suma gradelor este dublul numărului muchiilor. Din aceste două relații poți afla câte frunze lipsesc dintr-o descriere parțială a arborelui.

Lecția este destinată capitolului arbori pentru BAC la matematică-informatică. Lucrăm cu arbori neorientați, fără rădăcină aleasă; la arborii cu rădăcină, „frunză” se referă la lipsa fiilor și trebuie verificată separat situația rădăcinii. Exemplele de mai jos nu cer numărarea tuturor arborilor posibili.

Cum recunoști ipoteza de arbore?

Un arbore este un graf simplu, neorientat, conex și fără cicluri. Între oricare două vârfuri există un singur lanț elementar. Existența rezultă din conexitate, iar unicitatea din absența ciclurilor: două trasee elementare distincte ar închide undeva un ciclu.

Pentru un graf cu n vârfuri, relația m=n−1 nu dovedește singură că ai un arbore. De exemplu, un triunghi și un vârf izolat au patru vârfuri și trei muchii, dar graful nu este conex. Trebuie să ai și o proprietate suplimentară, precum conexitatea.

Într-o problemă care spune explicit „arbore”, poți folosi proprietățile sale. Dacă enunțul spune numai „graf”, nu importa automat formulele arborilor. Subliniază această diferență înainte de calcul: ea schimbă informațiile pe care ai voie să le deduci.

Schema celor două numărători

Informație	Relația pentru un arbore cu n vârfuri
Număr de muchii	n−1
Suma tuturor gradelor	2n−2
Gradul unei frunze, când n este cel puțin doi	1
Gradul unui vârf care nu este frunză	Cel puțin 2

Un arbore cu un singur vârf are gradul zero și nicio muchie. De aceea, afirmația despre frunze de grad unu trebuie folosită cu ipoteza indicată. În toate problemele numerice care urmează avem cel puțin două vârfuri.

Exemplu: frunze și trei vârfuri interioare

Un arbore are trei vârfuri care nu sunt frunze, de grade patru, trei și doi. Toate celelalte vârfuri sunt frunze. Câte frunze și câte vârfuri are arborele?

Notăm numărul frunzelor cu L. Numărul total de vârfuri este L+3, iar suma gradelor este L+4+3+2=L+9. Din relația generală rezultă L+9=2(L+3)−2. Reducând termenii, obținem L=5.

Arborele are opt vârfuri și șapte muchii. Verificarea sumei gradelor dă cinci plus patru plus trei plus doi, adică paisprezece, egal cu dublul celor șapte muchii. Această verificare confirmă calculul, dar merită să arătăm și o construcție.

Leagă cele trei vârfuri interioare într-un lanț A–B–C. Atașează trei frunze lui A, o frunză lui B și o frunză lui C. Gradele devin patru, trei și doi; graful este conex și nu are cicluri. Descrierea cerută este realizabilă.

O formulă care explică rolul ramificațiilor

Dacă L este numărul frunzelor și celelalte vârfuri au gradele d, rezultă relația: L este doi plus suma valorilor d−2 pentru toate vârfurile care nu sunt frunze. Un vârf de grad doi contribuie cu zero, unul de grad trei cu unu, unul de grad patru cu doi.

Poți deduce formula, nu trebuie să o înveți izolat. Scrii suma gradelor ca L plus suma gradelor interioare. Numărul total de vârfuri este L plus numărul vârfurilor interioare. Înlocuiești în egalitatea sumei gradelor și muți termenii.

Interpretarea este utilă: vârfurile de grad doi prelungesc trasee fără să adauge ramificații. Vârfurile cu grad mai mare cer mai multe capete de drum, adică frunze. Aceasta explică de ce adăugarea unor vârfuri pe muchiile unui lanț nu îi schimbă cele două extremități.

Această deducție este un exercițiu de înțelegere a formulelor. Reproduce egalitatea inițială pe hârtie, apoi verifică rezultatul pe un lanț și pe o stea, cele două forme ușor de desenat.

Ce poți spune despre numărul minim și maxim de frunze?

Un arbore cu cel puțin două vârfuri are minimum două frunze. Un lanț care trece prin toate vârfurile realizează acest minim: numai extremitățile au grad unu, iar toate vârfurile din interior au grad doi.

Pentru n cel puțin trei, maximul este n−1 frunze, realizat de o stea. Un singur centru se leagă de toate celelalte vârfuri, iar acestea au grad unu. Cazul n=2 se tratează separat: ambele vârfuri sunt frunze.

Nu poți avea toate vârfurile de grad unu când n este mai mare decât doi și graful trebuie să fie conex. Fiecare vârf și-ar consuma singura muchie într-o pereche, fără posibilitatea de a lega toate perechile între ele.

Ce se întâmplă când elimini o frunză?

Ștergi frunza și unica sa muchie. Graful rămas este tot arbore, dacă mai are vârfuri: orice două vârfuri păstrate rămân legate, deoarece frunza nu putea fi un punct interior pe drumul lor. Niciun ciclu nou nu poate apărea prin ștergere.

Numărul frunzelor rămase depinde de gradul vechi al vecinului. Dacă vecinul avea grad doi și graful rămas are cel puțin două vârfuri, el devine frunză: pierzi una și câștigi una. Dacă avea grad cel puțin trei, nu devine frunză și totalul scade cu unu.

Pentru arborele cu două vârfuri, ștergerea unei frunze lasă un vârf izolat de grad zero. Acest caz nu se descrie prin regula obișnuită de înlocuire a unei frunze; verifică separat dimensiunile foarte mici.

Exerciții cu răspunsuri

1. Un arbore are patru vârfuri de grad trei, două de grad doi și restul frunze. Relația ramificațiilor dă două plus patru, deci șase frunze. Numărul total de vârfuri este doisprezece, iar suma gradelor este douăzeci și doi.
2. Un arbore cu nouă vârfuri are un vârf de grad cinci, două de grad doi și restul frunze. Descrierea ar impune șase frunze, deci suma gradelor ar fi cincisprezece, în loc de șaisprezece. Datele nu pot descrie un arbore; nu ajusta răspunsul ignorând contradicția.
3. Un arbore are numai grade unu și trei, iar numărul frunzelor este șapte. Există cinci vârfuri de grad trei, deoarece fiecare contribuie cu unu peste cele două frunze de bază. Totalul este doisprezece vârfuri.
4. Într-un lanț cu șase vârfuri eliminăm o extremitate. Rămâne un lanț cu cinci vârfuri și tot două frunze. Vecinul extremității eliminate a trecut de la gradul doi la gradul unu.

Întrebări frecvente

Poate o listă de grade corectă numeric să țină loc de desen?

Pentru o problemă de calcul, relațiile pot determina răspunsul. Dacă se cere o construcție sau verificarea unui graf concret, trebuie să prezinți și muchiile relevante. Egalitatea sumelor nu verifică singură conexitatea unui desen dat.

Rădăcina este întotdeauna frunză când are grad unu?

Nu în convenția arborilor cu rădăcină: o rădăcină cu un fiu nu este frunză, deși gradul ei neorientat este unu. Precizează modelul înainte să numeri.

Cum exersez fără să memorez desene?

Alege cerințe despre arbori din arhiva BAC, notează separat numărul vârfurilor din fiecare categorie și verifică suma gradelor. Dacă vrei corectarea argumentului, compară anunțuri de informatică și prezintă și o construcție cu muchii etichetate.