youblisher.com-692643-ciclos de hamilton rboles

12
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

Upload: cevym85

Post on 20-Jan-2016

14 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: Youblisher.com-692643-Ciclos de Hamilton Rboles

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

Page 2: Youblisher.com-692643-Ciclos de Hamilton Rboles

Í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

Page 3: Youblisher.com-692643-Ciclos de Hamilton Rboles

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

Page 4: Youblisher.com-692643-Ciclos de Hamilton Rboles

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

Page 5: Youblisher.com-692643-Ciclos de Hamilton Rboles

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.

Page 6: Youblisher.com-692643-Ciclos de Hamilton Rboles

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).

Page 7: Youblisher.com-692643-Ciclos de Hamilton Rboles

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.

Page 8: Youblisher.com-692643-Ciclos de Hamilton Rboles

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

Page 9: Youblisher.com-692643-Ciclos de Hamilton Rboles

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”.

Page 10: Youblisher.com-692643-Ciclos de Hamilton Rboles

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

Page 11: Youblisher.com-692643-Ciclos de Hamilton Rboles

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.

Page 12: Youblisher.com-692643-Ciclos de Hamilton Rboles

OST-ORDEN