Teoría de grafos-arboles

Páginas: 3 (640 palabras) Publicado: 28 de noviembre de 2010
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...
Leer documento completo

Regístrate para leer el documento completo.

Estos documentos también te pueden resultar útiles

  • teoria de grafos y arboles
  • arboles en la teoría de grafos y un programa en c
  • Grafos y arboles
  • Grafos Y Árboles
  • Arboles (Grafos)
  • Grafos Y Arboles
  • arboles grafoas
  • Grafos Y Árbol

Conviértase en miembro formal de Buenas Tareas

INSCRÍBETE - ES GRATIS