Arboles
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 como máximo 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.
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
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 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 ( 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 bipartito. Todo árbol con sólo un conjunto contable de vértices es además un grafo plano.
Todo grafo conexo G admite un árbol de cobertura, 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:
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
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 como máximo 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.
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
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 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 ( 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 bipartito. Todo árbol con sólo un conjunto contable de vértices es además un grafo plano.
Todo grafo conexo G admite un árbol de cobertura, 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:
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
No hay comentarios:
Publicar un comentario