ARBOLES GENERADORES


ÍNDICE
DEDICATORIA
AGRADECIMIENTO
I. INTRODUCCION………………………………...……………………….…6
II. EL PROBLEMA……………………………...………………….…………...7
A. Planteamiento Del Problema…………………………………………......7
B. Justificación……………………………………………………………….7
III. OBJETIVOS DE LA INVESTIGACION………………………………….…8
A. Objetivo General
B. Objetivo Especifico
IV. MARCO TEORICO………………………..…………………….……….…..9
A.ARBOLES………………….……………………………….……………..9
1. Arboles Con Raíz O Enraizados……………………………………...11
2. Tipos De Arboles……………………………………….....………….12
B. ARBOLES GENERADORES……………………...……………………13
1. Introducción……………………………………………….…………13
2. Definición 1……………………………….………………………….13
3. Teorema 1…………………………………………………………….15
B.1. BUSQUEDA EN PROFUNDIDAD…….……………………………….18
B.2. BUSQUEDA EN ANCHURA…………………..…………………….…23
B.3.APLICACIONES DE VUELTA ATRÁS………………………………..26B.4. BUSQUEDA EN PROFUNDIDAD EN GRAFOS DIRIGIDOS…….…30
V. CONCLUSIONES……………………………………………….………….32
VI. SUGERENCIAS INVESTIGATIVAS……………..…………………….…32
VII. REFERENCIAS……………………………………………………………..32
VIII. ANEXOS……………………………………………………………...…….33





I. INTRODUCCION
En matemática discreta muchos problemas pueden resolverse considerándolos como casos especiales de un problema más general.
Porejemplo, dada una sucesión de números enteros, encontrar el mayor; dado un conjunto, enumerar todos sus subconjuntos; dado un conjunto de enteros, escribirlos en orden creciente; dada una red de ordenadores, encontrar el camino más corto entre dos nodos.
Para resolver un problema como estos debemos construir un modelo que traduzca el problema a un contexto matemático. Las estructuras discretasutilizadas en estos modelos incluyen conjuntos, sucesiones, funciones, relaciones, grafos, arboles, redes y máquinas de estado finito.
Fijar el modelo matemático apropiado es proporcionar un algoritmo que especifique una secuencia de pasos que conduzcan a una solución en el caso general.
La combinatoria, el estudio de las posibles agrupaciones de objetos, contar el número de objetos que verificanciertas propiedades, es una parte importante de la matemática discreta, pues se necesita para resolver problemas de muy diversos tipos.
La teoría de grafos y de árboles se emplea para resolver problemas en una variedad de disciplinas. Los grafos pueden utilizarse, por ejemplo, para determinar si se puede implementar un circuito sobre una placa de una sola capa. También se pueden utilizar grafospara estudiar la estructura de la Red de Internet. Los árboles en informática se usan para construir algoritmos eficientes que localizan elementos de una lista.
II. EL PROBLEMA
A. PLANTEAMIENTO DEL PROBLEMA
La importancia de la estructura discreta del árbol en el contexto del desarrollo científico y tecnológico de la humanidad, está determinada por la posibilidad de elaborar modelos matemáticos delos objetos estudiados por las diferentes ramas de la ciencia y la técnica es decir, describir mediante el lenguaje vigoroso de la matemática, las propiedades de los objetos reales. En la matemática actual no basta desarrollar una teoría para encontrar la solución de un problema, hoy en día el estudiante de ingeniería actual se enfrenta desarmado al campo experimental por falta de conocimiento.B. JUSTIFICACION
La matemática del siglo XX ha sido predominantemente la matemática del continuo en la que el análisis, por su potencia y repercusión en las aplicaciones técnicas, ha jugado un papel predominante.
El advenimiento de los ordenadores, con su inmensa capacidad de cálculo, con su enorme rapidez, versatilidad, potencia de representación gráfica, posibilidades para la modelización sinpasar por la formulación matemática de corte clásico, ha abierto multitud de campos diversos, con origen ya no en la física, como los desarrollos de siglos anteriores, sino en otras muchas ciencias como la economía, las ciencias de la organización, biología, cuyos problemas resultaban opacos, en parte por las enormes masas de información que había que tratar hasta...