Árbol (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Árbol
Tree graph.svg
Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2-4-5-6.
Vértices v
Aristas v-1
Número cromático 2 si v > 1
Propiedades Bipartito, expandible y plano (si el conjunto de vértices es numerable)

En teoría de grafos, un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.

Definiciones[editar]

Un árbol es un grafo simple no dirigido G que satisface:

  • G es conexo y no tiene ciclos .
  • G no tiene ciclos y, si se añade alguna arista se forma un ciclo.
  • G es conexo y si se le quita alguna arista deja de ser conexo.
  • G es conexo y el grafo completo de 3 vértices K_3 no es un menor de G.
  • Dos vértices cualquiera de G están conectados por un único camino simple.

Las condiciones anteriores son todas equivalentes, es decir, si se cumple una las demás se cumplirán.

Si un árbol G tiene un número finito de vertices, n, entonces tiene n − 1 aristas.

Un grafo unidireccional simple G es un bosque si no tiene ciclos simples.

Un árbol dirigido es un grafo dirigido que sería un árbol si no se consideraran las direcciones de las aristas. Algunos autores restringen la frase al caso en el que todos las aristas se dirigen a un vértice particular, o todas sus direcciones parten de un vértice particular.

Un árbol recibe el nombre de árbol con raíz si un vértice ha sido designado raíz. En este caso las aristas tienen una orientación natural hacia o desde la raíz. Los árboles con raíz, a menudo con estructuras adicionales como orden de los vecinos de cada vértice, son una estructura clave en informática; véase árbol (programación).

Un árbol etiquetado es un árbol en el que cada vértice tiene una única etiqueta. Los vértices de un árbol etiquetado de n vértices reciben normalmente las etiquetas {1,2, ..., n}.

Un árbol regular u homogéneo es un árbol en el que cada vértice tiene el mismo grado.

Propiedades[editar]

Todo árbol es a su vez un [[grafo mensobol con sólo un conjunto numerable de vértices es además un grafo plano.

Todo grafo conexo G admite un árbol de expansión, que es un árbol que contiene cada vértice de G y cuyas aristas son aristas de G.

Dado n vértices etiquetados, hay n n−2 maneras diferentes de conectarlos para construir un grafo. El resultado se llama fórmula de Cayley. El número de árboles con n vértices de grado d1,d2,...,dn es:

 {n-2 \choose d_1-1, d_2-1, \ldots, d_n-1},

que es un coeficiente multinomial.

Contar el número de árboles no etiquetados es un problema complicado. De hecho, no se conoce ninguna fórmula para el número de árboles t(n) con n vértices (debe entederse aquí el número de árboles diferentes salvo isomorfismo de grafos). Los primeros valores de t(n) son 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, ... (sucesión A000055 en OEIS). Otter (1948) probó que

 {t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,}

Una fórmula más exacta para el comportamiento asintótico de t(n) implica que hay dos números α y β (α ≈ 3 y β ≈ 0.5) tales que:

\lim_{n\to\infty} \frac{t(n)}{\beta \alpha^n n^{-5/2}} = 1.

Véase también[editar]

Enlaces externos[editar]