Se define como árbol a un grafo no
dirigido en el que cualesquiera dos vértices están conectados por exactamente un camino
y cumple las siguientes propiedades:
- Es simple, conexo y sin ciclos.
- Es conexo y |V|=n entonces |A|=n-1.
- G no contiene ciclos y si a, b ∈ V con {a, b) ∉ E, entonces el grafo que se obtiene de añadir la arista {a, b] a G tiene precisamente un ciclo.
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 y la
producción. En la informática se utiliza para, por ejemplo:
- Representar un dato jerárquicamente
- Almacenar un dato de tal modo que su búsqueda sea eficiente (ver búsqueda en árboles binarios y recorrido de árboles)
- Representar listas ordenadas de datos
- Como un flujo de trabajo para la composición de imágenes digitales
- Algoritmos de encaminamiento
No hay comentarios:
Publicar un comentario