Árbol (Grafo)
| ||||||
Árbol(Grafo). En álgebra, matemática discreta, programación, informática, dícese del grafo que es simple conexo y que no contiene ciclos.
El árbol es una estructura grafoidea de gran aplicación dentro de varias ciencias dentro de las matemáticas y la computación, donde existen no pocas implementaciones de los mismos y usos; pero que sirve para modelar muchos otros aspectos en otros campos de la ciencia, la producción y la vida cotidiana.
Sumario
Definiciones
Se entiende por árbol al grafo G=<V,A> que cumple con las propiedades de ser simple, conexo y sin ciclos.
Otra definición equivalente sería:
Sea un grafo G=<V,A> las siguientes propiedades son equivalentes entre sí:
- G es un árbol.
- G es simple, conexo y sin ciclos.
- G es conexo y |V|=n entonces |A|=n-1.
O la siguiente de carácter constructiva:
Un árbol es un grafo G definido recursivamente por las siguientes proposiciones:
- Un árbol es un solo nodo.
- Un árbol es un nodo conectado mediante sendas aristas a varios árboles denominados ramas.
Normalmente se identifica a un vértice como raíz o padre de la cual deriva aristas a otros nodos que se llaman hijos de dicho padre o raíz. A los nodos que no tienen descendencia se les llama hojas.
Tipos de árboles y su representación
Los árboles se clasifican según la cantidad máxima de hijos que produce cada nodo. Uno de los casos más estudiados es el de los árboles binarios cuyos nodos tienen hasta dos hijos, los que poseen hasta tres se denominan ternarios y el resto árboles generales o sencillamente árboles.
Los árboles independientemente de su tipo, suelen representarse de la raiz hacia las hojas (arriba-abajo), estructurando jerárquicamente cada piso o generación a un mismo nivel.
Consecuencias e importancia
Los árboles son modelos de gran utilidad pues su representación normalmente alude a una estructura jerárquica y este es una de sus principales usos. También se usan mucho en las modelación de búsquedas o problemas que dependan de la representación de una búsqueda en un espacio representable como un grafo.
Computacionalmente aparecen representados como:
entre otras formas.
En todos los casos tienen gran utilidad como por ejemplo las estructuración de los sistemas de archivo en UNIX, Linux, Windows, MS-DOS y otros sistemas operativos del lado del usuario a quien se le da la impresión de que se trata de una raíz (/) y que cada subdirectorio es un hijo de / que puede contener a otros subdirectorios dentro y así sucesivamente en una clara estructura arbórea.
Operatoria
Es común que en los árboles se realicen una serie de operaciones como:
- Enumerar los nodos.
- Buscar un vértice.
- Dado un nodo, listar sus hijos o sucesores.
- Borrar un elemento.
- Eliminar un subárbol (podar una rama).
- Añadir un subárbol (injertar una rama).
- Encontrar la raíz de un nodo cualquiera.
- Recorrer el árbol:
- Azar.
- Primero a lo ancho.
- Primero en profundidad.
- De manera infija: hijo-padre-hijo.
Véase también
Fuentes
- K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988.
- Grafo en Wikipedia. Consultado 27 de noviembre de 2013.
- Árbol en Wikipedia. Consultado 27 de noviembre de 2013.
