Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación.
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos.
Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
Otro ejemplo de la utilización de árboles son los diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
En esta monografía introducirán los siguientes temas: árboles de expansión, su definición; arboles de expansión mínima, su definición y la explicación de los algoritmos que permiten hallar un árbol de expansión mínima; y arboles binarios, su definición y propiedades
Estos temas forman parte del programa de la asignatura Matemática Discreta, correspondiente al 2º año de la carrera Ingeniería en Informática.
La bibliografía utilizada para el desarrollo de este trabajo será "Matemáticas Discretas" de Johnsonbaugh Richard - Sexta Edición - Prentice Hall y para consulta otros mencionados en la Bibliografia.
Definiciones
básicas
Un Grafo (o grafo no dirigido) es un
conjunto V de vértices y un conjunto E de aristas tales
que cada arista e ? E(queda asociada a un par no ordenado de
vértices. Si existe una única arista e asociada con
los vértices v y w, escribimos e = (v,w). En este contexto
(v,w) denota una arista en un grafo no dirigido y no un par
ordenado.
Un grafo dirigido (o digrafo) consta
de un conjunto finito de vértices V y un conjunto de arcos
E ? V × V (obsérvese que cada arco es un par
ordenado de vértices).
Grafo conexo: un grafo G es conexo
si dados cualesquiera dosvértices v y w en G, existe un
camino de v a w.
Camino: sean v0 y vn vértices
de un grafo. Un camino de v0 a vn de longitud n es una
sucesión alternante de n+1 vértices y n aristas que
comienza con el vértice v0 y termina con el vértice
vn.
Longitud del camino: es el
número de aristas que contiene.
Ciclo: sean v y w vértices en
un grafo G, un ciclo o circuito es un ca
mino de longitud distinta
de 0 de v a w, sin aristas repetidas.
Subgrafo: sea G (V, E) un grafo.
(V", E") es un subgrafo de G si
-
a) V" ( V y E"( E.
-
b) Para cada arista e" ( E", si e" es incidente en v" y w", entonces v", w" ( V.
No hay comentarios:
Publicar un comentario