Metoda backtracking, arbori, grafuri, greedy, divide et impera, metoda programării dinamice, algoritmi

• Arbori

Numim arbore un graf neorientat conex şi fără cicluri.

Aceasta nu este singurul mod în care putem defini arborii. Câteva definiţii echivalente apar în următoarea teoremă, expusă fără demonstraţie.

Teoremă. Fie G un graf cu n1 vârfuri. Următoarele afirmaţii sunt echivalente:

1) G este un arbore;

2) G are n-1 muchii şi nu conţine cicluri;

3) G are n-1 muchii şi este conex;

4) oricare două vârfuri din G sunt unite printr-un unic drum;

5) G nu conţine cicluri şi adăugarea unei noi muchii produce un unic ciclu elementar;

6) G este conex, dar devine neconex prin ştergerea oricărei muchii.

În foarte multe probleme referitoare la arbori este pus în evidenţă un vârf al său, numit rădăcină. Alegerea unui vârf drept rădăcină are două consecinţe:

• Arborele poate fi aşezat pe niveluri astfel:

- rădăcina este aşezată pe nivelul 0;

- pe fiecare nivel i sunt plasate vârfurile pentru care lungimea drumurilor care le leagă de rădăcină este i;

- se trasează muchiile arborelui.

Această aşezare pe niveluri face mai intuitivă noţiunea de arbore, cu precizarea că în informatică "arborii cresc în jos".

Exemplul 3. Considerăm următorul arbore şi modul în care el este aşezat pe niveluri prin alegerea vârfului 5 drept rădăcină.

• Arborele poate fi considerat un graf orientat, stabilind pe fiecare muchie sensul de la nivelul superior către nivelul inferior.

Reprezentarea pe niveluri a arborilor face ca noţiunile de fii (descendenţi) ai unui vârf, precum şi de tată al unui vârf să aibă semnificaţii evidente. Un vârf fără descendenţi se numeşte frunză.

• Arbori binari

Un arbore binar este un arbore în care orice vârf are cel mult doi descendenţi, cu precizarea că se face distincţie între descendentul stâng şi cel drept. Din acestă definiţie rezultă că un arbore binar nu este propriu-zis un caz particular de arbore.

Primele probleme care se pun pentru arborii binari (ca şi pentru arborii oarecare şi pentru grafuri, aşa cum vom vedea mai târziu) sunt:

- modul de reprezentare;

- parcurgerea lor.

Forma standard de reprezentare a unui arbore binar constă în:

- a preciza rădăcina rad a arborelui;

- a preciza pentru fiecare vârf i tripletul st(i), dr(i) şi info(i), unde acestea sunt respectiv descendentul stâng, descendentul drept şi informaţia ataşată vârfului.

Trebuie stabilită o convenţie pentru lipsa unuia sau a ambilor descendenţi, ca de exemplu specificarea lor prin simbolul .

Exemplul 4. Considerăm de exemplu următorul arbore binar:

Presupunând că informaţia ataşată fiecărui vârf este chiar numărul său de ordine, avem:

- rad = 1;

- st = (2,3,4,,6,,,,);

- dr = (8,5,,,7,,,9,);

- info= (1,2,3,4,5,6,7,8,9).

Dintre diferitele alte reprezentări posibile, mai menţionăm doar pe cea care se reduce la vectorul său tata şi la vectorul info. Pentru exemplul de mai sus:

tata=(,1,2,3,2,5,5,1,8).

Problema parcurgerii unui arbore binar constă în identificarea unei modalităţi prin care, plecând din rădăcină şi mergând pe muchii, să ajungem în toate vârfurile; în plus, atingerea fiecărui vârf este pusă în evidenţă o singură dată: spunem că vizităm vârful respectiv. Acţiunea întreprinsă la vizitarea unui vârf depinde de problema concretă şi poate fi de exemplu tipărirea informaţiei ataşate vârfului.