Teoría de grafos-arboles

Solo disponible en BuenasTareas
  • Páginas : 3 (640 palabras )
  • Descarga(s) : 0
  • Publicado : 28 de noviembre de 2010
Leer documento completo
Vista previa del texto
Arboles:
Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo con n vértices, los árboles tienen exactamente n - 1 aristas, y hay nn-2  árboles posibles. Suimportancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Un árbol es un grafo simple unidireccional G que satisface alguna delas 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 sele 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 tienearistas 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 recibe el nombrede bosque si no tiene ciclos simples.
 Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un procesoevolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.
Todo árbol es a su vez un grafobipartito. 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 cuyasaristas son aristas de G.
En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad...
tracking img