Apicultura Wiki
Advertisement

En teoría de grafos, un árbol es un grafo en el que dos vértices están conectados por exactamente un camino. Un bosque es un grafo en el que dos vértices cualquiera están conectados por al menos un camino. Una definición equivalente es que un bosque es una unión disjunta de árboles (de aquí el nombre). Un árbol a veces recibe el nombre de árbol libre.

Definiciones[]

Un árbol es un grafo simple unidireccional G que satisface alguna de las siguientes condiciones equivalentes:

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

Si G tiene muchos vértices, n, entonces las definiciones anteriores son también equivalentes a cualquiera de las siguientes condiciones:

  • G es conexo y tiene n − 1 arcos.
  • G no tiene arcos simples y tiene n − 1 arcos.

En gráfico unidireccional simple G se recible el nombre de bosque si no tiene ciclos simples.

Un árbol direccional es un grafo direccional que sería un árbol si se hiciera caso omiso de las direcciones de los arcos. Algunos autores restringen la frase al caso en el que todos los arcos 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 cada vértice ha sido designado raíz, en cuyo caso los arcos 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 ( homogéneo) es un árbol en el que cada vértice tiene el mismo grado. Véase grafo regular.

Archivo:Tree graph.svg

Un árbol etiquetado con 6 vértices y 5 arcos

Ejemplo[]

En árbol de ejemplo mostrado a la derecha tiene 6 vértices y 6 − 1 = 5 arcos. El único camino simple que conoecta los vértices 2 y 6 es 2-4-5-6.

Hechos[]

Cada árbol es un grafo bipartito. Cada árbol con sólo un conjunto contable de vértices es un grafo planar.

Cada grafo conexo G admite un árbol de cobertura, que es un árbol que conotiene cada vértice de G y cuyos arcos son arcos 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 cono n vértices de grado d1,d2,...,dn es:

que es un coeficiente multinomial.


No se conoce fórmula para el número t(n) de árboles con n vértices de un isomorfismo de grafos. Sin embargo, el comportamiento asintótico de t(n) se conoce; hay números α ≈ 3 y β ≈ 0.5 tales que

Véase también[]

  • árbol (programación)

References[]

Advertisement