EXPOSICION

TEMA 6.2.1

RECORRIDO DE UN ARBOL

RECORRIDO DE UN ARBOL

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden especifico, nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo.

RECORRIDO DE UN ARBOL binario

Recorrido en Profundidad

Recorrido en amplitud

FORMAS DE RECORRER UN ARBOL BINARIO

PRE-ORDEN

IN-ORDEN

POST-ORDEN

POR NIVELES

PRE-ORDEN

proceso

Visita el nodo raíz del árbol.

paso 1

Atraviese el sub-árbol izquierdo

paso 2

Atraviese el sub-árbol derecho

paso 3

F,D,A,E,H,I

APLICACIÓN COMÚN:

Copiar o clonar árbol.

Ejemplo: PRE-ORDEN

Orden de visita: Raíz → Sub-árbol izquierdo → Sub-árbol derecho.

in-ORDEN

proceso

Atraviesa el sub-árbol izquierdo

paso 1

Visite la raíz

paso 2

Atraviese el sub-árbol derecho

paso 3

A,D,E,F,H,I

APLICACIÓN COMÚN:

Árboles binarios de búsqueda (BST) Garantiza que los nodos se visiten en orden ascendente.

ejemplo: IN-ORDEN

Orden de visita: Sub-árbol izquierdo → Raíz → Sub-árbol derecho.

post-ORDEN

proceso

Atraviesa el sub-árbol izquierdo

paso 1

Atraviese el sub-árbol derecho

paso 2

Visite la raíz

paso 3

A,E,D,I,H,F

APLICACIÓN COMÚN:

Liberar los nodos de un árbol

Ejemplo: POSt-ORDEN

Orden de visita: Sub-árbol izquierdo → Sub-árbol derecho → Raíz.

por niveles

APLICACIÓN COMÚN:

Buscar el nodo mas cercano, determinar la distancia entre nodos.

TEMA 6.3

REDES

RED

Estructura algebraica formada por vértices y aristas que representa relaciones entre objetos o eventos. Un grafo "dirigido" con "pesos" es también conocido como una red.

TEMA 6.3.1

teorema de flujo maximo

Establece una relación entre el valor máximo de flujo que se puede enviar desde un nodo de fuente (s) a un nodo de sumidero (t) en un grafo, y el corte mínimo en la red.

fuente

sumidero

PROCEDIMIENTO

1.-Preparar el grafo. Se van a poner flechas en el sentido del flujo para una mejor visualización, y se pone a cero la capacidad usada de todos los arcos. 2.-Obtener una trayectoria de aumento, siguiendo el criterio de ir siempre por el camino que proporcione una mayor capacidad residual en cada nodo. 3.-Determinar el flujo de la trayectoria de aumento. Será el mínimo de las capacidades residuales de los arcos que la forman. 4.-Actualizar el grafo. Se modifican las capacidades residuales y usadas de cada arco, así como el flujo total. 5.-Volver al punto 2 hasta que no existan más trayectorias de aumento.

EJEMPLO

SENTIDO DE FLUJO

SENTIDO DE FLUJO

CAPACIDAD USADA

CAPACIDAD USADA

NODO DESTINO

NODO FUENTE

CAPACIDAD RESIDUAL

CAPACIDAD RESIDUAL

PREPARAR EL GRAFO

TRAYECTORIA DE AUMENTO 1

TRAYECTORIA DE AUMENTO 1

ACTUALIZAMOS EL GRAFO

TRAYECTORIA DE AUMENTO 2

ACTUALIZAMOS EL GRAFO

TRAYECTORIA DE AUMENTO 3

ACTUALIZAMOS EL GRAFO

TRAYECTORIA DE AUMENTO 4

ACTUALIZAMOS EL GRAFO

FLUJO MAXIMO : 12

REFERENCIAS

Villalpando Becerra, J. F. (2014). Matemáticas discretas: aplicaciones y ejercicios: ( ed.). Grupo Editorial Patria. https://elibro.net/es/lc/itsteziutlan/titulos/39454 https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/ https://mate-discretasj2.blogspot.com/p/blog-page.html http://dis.um.es/~ginesgm/files/doc/aed/sec5.6.3-5.8.pdf https://es.slideshare.net/AngelesQuezada/unidad-6-76643539 https://youtu.be/DRwWwwyl3CI?si=oUOnOlAtFT_LnuRD

¡GRACIAS!

¡GRACIAS!

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.

Tus contenidos gustan, pero solo enganchan si son interactivos. Capta la atención de tu público con una fotografía o ilustración interactiva.