Grafuri orientate și arbori cu rădăcină

Grafuri — grafuri orientate, tare conexitate, arbori cu rădăcină

Determinarea arcelor, a gradelor interioare și exterioare și a drumurilor dintr-o matrice de adiacență a unui graf orientat.
Deosebirea dintre conexitate și tare conexitate și identificarea componentelor tare conexe.
Reconstituirea unui arbore cu rădăcină din vectorul de tați și determinarea rădăcinii, a frunzelor, a nivelurilor și a înălțimii.

Într-un graf orientat arcul este o pereche ordonată, iar (i, j) și (j, i) sunt arce diferite.
Gradul exterior se citește pe linia matricei de adiacență, gradul interior pe coloană; suma fiecăruia dintre cele două tipuri de grade este m.
Matricea de adiacență a unui graf orientat nu este simetrică, iar numărul de arce este chiar numărul de valori 1, fără împărțire la 2.
Un drum respectă sensul arcelor; un circuit este un drum care se închide în vârful de pornire fără a repeta arce.
Tare conex înseamnă drum în ambele sensuri între oricare două vârfuri; un vârf cu grad exterior 0 face imposibilă tare conexitatea.
Într-un arbore cu rădăcină, rădăcina nu are tată, frunzele nu au fii, iar descendenții unui vârf sunt tot subarborele lui, nu doar fiii.
În vectorul de tați, rădăcina este indicele cu t[i] = 0, frunzele sunt indicii care nu apar ca valoare, iar nivelul se obține urcând din tată în tată.