Inicio · Parte 04 — Matemática discreta para computación
|E| = |V| − 1
existe un único camino entre cada par de vérticesUn árbol es un grafo conexo sin ciclos, y esa doble condición tiene una consecuencia numérica exacta: con n vértices tiene exactamente n−1 aristas. Ni una más —eso crearía un ciclo— ni una menos —eso lo desconectaría—. Es la estructura conexa mínima.
La unicidad del camino entre cualquier par de vértices se sigue de la ausencia de ciclos, y es la propiedad que hace útiles a los árboles: no hay ambigüedad sobre cómo llegar de un nodo a otro. De ahí que se usen para jerarquías, sistemas de archivos, índices de bases de datos y estructuras de decisión.
La altura de un árbol determina el coste de las operaciones. Un árbol binario equilibrado con n nodos tiene altura log₂ n, y por eso las búsquedas cuestan logarítmicamente; uno degenerado en lista tiene altura n y el coste se vuelve lineal. Todo el diseño de árboles balanceados (AVL, rojo-negro, B-tree) existe para garantizar esa altura logarítmica.
En machine learning, los árboles de decisión (clase 291) usan esta estructura para particionar el espacio de features, y su profundidad es el hiperparámetro que controla directamente el compromiso sesgo-varianza: más profundo, menos sesgo y más varianza.
Verificar la relación en un árbol de seis nodos.
raiz
/ \
a b
/ \ \
c d e
vértices: 6 (raiz, a, b, c, d, e)
aristas: 5
n − 1 = 5 ✓ es un árbol
hojas: c, d, e
altura: 2
profundidades:
raiz 0, a 1, b 1, c 2, d 2, e 2Un árbol con n nodos tiene exactamente n-1 aristas.
python classes/part-04-matematica-discreta-para-computacion/095-arboles-y-arboles-de-expansion/lab.py
compmath run 095nodosaristasn-1es_arbolhojasalturaprofundidades{
"nodos": 6,
"aristas": 5,
"n-1": 5,
"es_arbol": true,
"hojas": [
"c",
"d",
"e"
],
"altura": 2
}Sistemas de archivos, índices de bases de datos, árboles de decisión, parseo sintáctico y árboles de expansión mínima.
Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.
9780262046305 verificado en International ISBN Agency (2026-08-19).