Árbol (teoría de grafos)

Árbol (teoría de grafos)
Para otros usos de este término, véase Árbol (desambiguación).
Á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

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 alguna arista se forma un ciclo simple.
  • 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 K3 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 aristas.
  • G no tiene aristas simples y tiene n − 1 aristas.
  • La cantidad de hojas de un árbol siempre es mayor o igual a la mitad de la totalidad de los nodos.


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 cada vértice ha sido designado raíz, en cuyo 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

Todo árbol es a su vez un grafo bipartito. Todo árbol 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 primerlos 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

  • Árbol (programación)

Wikimedia foundation. 2010.

Поможем решить контрольную работу

Mira otros diccionarios:

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Grado (teoría de grafos) — Para otros usos de este término, véase Grado. Un grafo con vértices etiquetados según su grado. El vértice aislado se etiqueta con 0, pues su grado es igual a cero. En Teoría de grafos, el grado o valencia de un vértice es el número de aristas… …   Wikipedia Español

  • Estrella (teoría de grafos) — Estrella S7. En teoría de grafos, una estrella Sk es el grafo bipartito completo K1,k, un árbol con un vértice interno y k hojas. Una estrella con 3 aristas se conoce en inglés como claw (garra o garfio). La estrella Sk es tran …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Teoría de Bass-Serre — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Árbol binario — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Árbol de expansión — Un árbol de expansión (aristas azules gruesas) de un grafo de rejilla. En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas)… …   Wikipedia Español

  • Árbol k-ario — En la teoría de grafos, un árbol k ario es un arraigado árbol en el que cada nodo no tiene más que hijos k. También es conocido a veces como una manera de árbol k, un árbol N ario, o un árbol M ario. Un árbol binario es el caso especial en que… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”