miniatura|Un exemple d'arbre m-ari amb m=5 En teoria de grafs, un arbre m-ari (per a nombres enters no negatius m) (també conegut com a arbre n-ary, k-ary o k-way) és una arborescència (o, per a alguns autors, un arbre ordenat) en què cada node no té més de m fills. Un arbre binari és el cas especial on m = 2, i un arbre ternari és un altre cas amb m = 3 que limita els seus fills a tres.
Tipus d'arbres m-aris Un arbre m-ari complet és un arbre m -ari on dins de cada nivell cada node té 0 o m fills. Un arbre m-ari complet (o, menys habitualment, un arbre m-ari perfecte) és un arbre m -ari complet en el qual tots els nodes de fulles es troben a la mateixa profunditat.
Propietats dels arbres m-aris Per a un arbre m -ari amb alçada h, el límit superior del nombre màxim de fulles és . L'alçada h d'un arbre m -ari no inclou el node arrel, amb un arbre que només conté un node arrel amb una alçada de 0. L'alçada d'un arbre és igual a la profunditat màxima D de qualsevol node de l'arbre. El nombre total de nodes en un arbre m -ari perfecte és , mentre que l'alçada h és Segons la definició de Big-Ω, la profunditat màxima
L'alçada d'un arbre m -ari complet amb n nodes és . El nombre total de possibles arbre m -ari amb n nodes és (que és un número català).
Referències
Categoria:Teoria de grafs