Ce este un arbore în informatică?

Un graf neorientat conex și fără cicluri. Are exact n − 1 muchii, iar cu o rădăcină aleasă se reprezintă prin vectorul de tați.

Un arbore este un graf neorientat conex și fără cicluri. Amândouă condițiile contează: un graf fără cicluri dar neconex este o pădure.

Proprietățile cerute la teorie decurg una din alta. Un arbore cu n vârfuri are exact n − 1 muchii. Între oricare două vârfuri există un singur lanț. Dacă adaugi o muchie, apare exact un ciclu, iar dacă ștergi una, graful se rupe în două. Oricare două dintre „conex”, „fără cicluri” și „n − 1 muchii” o implică pe a treia.

Dacă alegi un vârf drept rădăcină, arborele capătă niveluri: fiecare vârf are un tată (vecinul de deasupra), eventual fii, iar cele fără fii sunt frunze. Cea mai compactă reprezentare este vectorul de tați: t[i] este tatăl lui i, iar rădăcina are t[rad] = 0. Din el se citesc rădăcina, fiii unui vârf, frunzele și drumul până la rădăcină, urcând din tată în tată.

Un item tipic: „un arbore are 3 vârfuri de grad 3, 2 de grad 2 și restul frunze; câte vârfuri are?” Scrii suma gradelor în două feluri și rezolvi ecuația. Lecția despre arbori o face pas cu pas.

Lecția care merge mai departe: Arbori