youblisher.com-692643-ciclos de hamilton rboles
TRANSCRIPT
Ingeniería de sistemas
Curso: Lógica y algoritmos
Profesor: Msc. Francisco Carrera
Sede: Heredia
Temas:
Teoría de grafos
Trayectoria y circuitos hamiltonianos
Árboles, altura
Búsqueda de árboles
Pre-orden, entre-orden y post-orden
Colaboradores:
María José Mangas G.
Henry Alvarado Jiménez
Fecha de entrega: 09.08.13
ÍNDICE
1. Trayectoria y Circuitos hamiltonianos
2. Definición
3. Árboles
4. Tipos de Arboles
5. Vertices Internos y terminales
6. Altura y nivel
7. Búsqueda de Arboles (Binario)
8. Recorrido de Arboles:
8.1 Pre-orden
8.2 Entre-orden
8.3 Post-orden
Bibliografía
http://www.youtube.com/watch?v=Vsuo0eKJHEQ
http://www.youtube.com/watch?v=9kxU4wBOhec
http://www.sisman.utm.edu.ec/libros/FACULTAD%20DE%20CIENCIAS%20INFORM%C3%81TICAS/
CARRERA%20DE%20INGENIER%C3%8DA%20DE%20SISTEMAS%20INFORMATICOS/02/estructura%
20de%20datos/arbol%20binario%20de%20busqueda/abb.pdf
http://www.utm.mx/~jahdezp/archivos%20estructuras/DESICION.pdf
INTRODUCCIÓN
Esta información es para completar los conocimientos del estudiante en base a Grafos dirigidos y
Circuitos Hamiltonianos, que en conjunto con la estructura de Arboles que nos permitirán
visualizar de forma organizada y selectiva todas las rutas posibles a la hora de crear futuros
proyectos.
Que es un ciclo hamiltoniano?
• Un ciclo hamiltoniano es un circuito que pasa por todos los vértices de una
gráfica donde no se repiten líneas y el unico vértice que se repite es el primero.
Ejemplos de ciclos hamiltonianos
Trayectoria o camino hamiltoniano
• Una trayectoria o camino hamiltoniano, es una sucesión de aristas adyacentes,
que visita todos los vértices del grafo una sola vez.
Ejemplos de caminos hamiltonianos
QUE ES UN ARBOL?
Es un tipo de estructura jerarquizada alternativo a las listas enlazadas, generalmente
utilizadas en la programación de hojas de cálculo y en IA.
Es una forma de grafos dirigidos útiles para organizar y relacionar datos, por ej.: BD
TIPOS DE ARBOLES
ARBOLES LIBRES
ARBOLES CON RAIZ
ARBOL BINARIO
ARBOL BINARIO COMPLETO
ARBOL DE EXPANSIÓN
ARBOL DE EXPANSIÓN MINIMA
ARBOLES DE DECISIÓN
SUBARBOL
ARBOLES LIBRES
No tienen definido un Vértice raíz específico, es un grafo no dirigido.
ARBOLES CON RAÍZ
Si tienen un Vértice definido especifico
ARBOLES BINARIOS
Son Arboles con raíz y se caracterizan por tener 2,1 ó 0 hijos (H.Izquierdo, H.Derecho) en
cada Vértice.
ARBOL BINARIO COMPLETO
Se caracteriza por tener 2 ó 0 hijos en cada Vértice.
ARBOLES DE EXPANSIÓN
Se obtiene de un Árbol general compuesto por Vértice y Aristas q están relacionadas y
cada arista tiene peso (grafica ponderada).
ARBOLES DE EXPANSIÓN MINIMA
Resulta de la relación de sus Vértices y las Aristas de menor peso, creando un Árbol con
sus Vértices y la suma de sus rutas encontradas (aristas) serán su peso.
ARBOLES DE DECISIÓN
• Técnica que permite analizar decisiones secuenciales basadas en el uso de
resultados y probabilidades asociadas.
Ventajas
• Facilita la interpretación de la decisión adoptada.
• Proporciona un alto grado de comprención.
• Explica el comportamiento respecto a una determinada tarea de decisión.
• Reduce el número de variables.
• Es una magnífica herramienta.
BUSQUEDA DE ÁRBOL BINARIO
• Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor
de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del
nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de
la clave del nodo.
BÚSQUEDA DE ÁRBOL BINARIO
SUB-ARBOLES
Se toma un Vértice ( como V.raíz )especifico con todos sus vértices consecuentes para
crear otro árbol.
VERTICES INTERNOS Y TERMINALES
VERTICES INTERNOS:
Son los vértices q si tienen un V. hijo
a) A,B,E,F,G,H,I
VERTICES TERMINALES:
Son los vértices donde NO se desprende otro vértice.
b) D,C,J,K,L,M
ALTURA Y NIVEL
Para determinar la Altura dependerá del Nivel de un Árbol y se debe partir del V.raíz hasta sus
V.terminales, iniciando de “0”.
RECORRIDO DE ARBOLES
PRE – ORDEN: RAÍZ – IZQUIERDA - DERECHA
ENTRE – ORDEN: IZQUIERDA – RAÍZ - DERECHA
POST – ORDEN: IZQUIERDA – DERECHA - RAÍZ
PRE-ORDEN
ENTRE –ORDEN
POST-ORDEN
CONCLUSIÓN
Después de conocer todos los métodos posibles y disponibles en esta presentación,
serán las pautas suficientes para empezar aplicarlas en nuestros proyectos y sobre todo
para completarlo con nuestros conocimientos y así aplicarlos en nuestra vida laboral,
que serán la base para trabajar de forma organizada y eficiente toda la información que
manejos en una determinada compañía o cualquier puesto de trabajo.
OST-ORDEN