Definiția. Un arbore orientat (sau o ordine) este un grafic orientat fără cicluri, toate vârfurile cărora, cu excepția unuia, conțin exact un singur arc. Singurul punct de la care ieșim numai arcele este numit rădăcina copacului. Restul vârfurilor sunt numite noduri de copaci.
Din definiția unui copac rezultă că rădăcina este conectată printr-o cale unică cu orice alt vârf al copacului.
În Fig. 5 prezintă diagrame ale tuturor copacilor orientați non-izomorf cu trei și patru vârfuri.
Aprobarea. Fiecare copac poate fi orientat.
Dovada. Alegem un vertex arbitrar u al arborelui și îi atribuim o rădăcină. Marginile care intră în punctul u. ne orientăm de la vârful u. Repetăm această procedură: după ce intrăm într-un vertex v de-a lungul unui arc, orientăm toate celelalte margini care intră în punctul vertex v. de la vârful v. Deoarece arborele nu conține cicluri, orientarea marginilor nu duce la contradicții.
În Fig. Figura 6 prezintă un exemplu de arbore orientat. Vârful ales de rădăcină este indicat de un cerc dublu.
Alegerea radacinii determină în mod unic orientarea arborelui. Prin urmare, pentru fiecare arbore cu vârfuri p corespunde arborilor orientați p.
Un top suspendat al unei comenzi este numit o frunză. Calea de la rădăcină la frunză se numește ramură. Lungimea celei mai mari ramuri a copacului este numită înălțimea pomului. Distanța de la rădăcină la un anumit vârf se numește nivelul vârfului. Rădăcina însăși are un nivel de 0. Vârfurile unui nivel formează nivelul firului.
Vârfurile care pot fi accesate de la vârf și. sunt numiți descendenți ai vârfului u. Dacă există un arc în copac. atunci vertexul u este numit tatăl vârfului v. iar vârful v este numit fiul vârfului u. Fiii unui tată sunt numiți frați.
Notă. Când sunt arbori orientați, este obișnuit să se pună rădăcina în partea de sus și toate săgețile arcilor să fie orientate de sus în jos, ceea ce elimină nevoia de a reprezenta aceste săgeți.
În Fig. 7 arborele din Fig. 6, ilustrate în conformitate cu aceste reguli. Vârfurile copacului sunt împărțite în 4 straturi. Nivelul zero conține rădăcina copacului. În primul și al doilea nivel există 4 vârfuri, în al treilea nivel există 8 vârfuri.
Articole similare
Trimiteți-le prietenilor: