matematicas 33
Post on 16-Jul-2015
44 Views
Preview:
TRANSCRIPT
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 1/14
ÁRBOLES
MODELOS DE REDES Y REDES DE PETRI
Asignatura:Matemáticas Computacionales
Elaborado por. Eduardo Martínez López
Profr.Gabriel Flores González
Atlacomulco, Edo de Mex, 20
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 2/14
ARBOLES
INTRODUCCIÓN
Los árboles forman una de las subclases de gráficas que más se utilizan. La
ciencia de la computación hace uso de los árboles ampliamente, especialmente
para organizar y relacionar datos en una base de datos. Los árboles surgen en
problemas teóricos como el tiempo óptimo para ordenar.
TERMINOLOGÍA Y CARACTERIZACIÓN DE LOS ÁRBOLES
Un árbol T (libre) es una gráfica simple que satisface lo siguiente; si v y w son
vértices en T, existe una trayectoria simple única de v a w. Se muestra un ejemplo:
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 3/14
Un árbol con raíz es un árbol en el que un vértice específico se designa como raíz,
se presenta un ejemplo:
Como la trayectoria simple de la raíz a cualquier vértice dado es única, cada
vértice esta en un nivel determinado de manera única. Así, el nivel de la raíz es el
nivel 0, los vértices que están debajo de la raíz están en el nivel 1, y así
sucesivamente. Por lo tanto podemos decir que: el nivel de un vértice v es la
longitud de la trayectoria simple de la raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que ocurre.
Ejemplo:
Tomando como referencia el gráfico del árbol con raíz determine el nivel del
vértice a, b, g y determine también la altura del árbol.
Para el vértice a su nivel es 0
Para el vértice b su nivel es 1
Para el vértice g su nivel es 2
La altura del árbol es de 2
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 4/14
ÁRBOLES DE EXPANSIÓN
Un árbol T es un árbol de expansión de una gráfica G si T es una subgráfica de G
que contiene a todos los vértices de G. Una grafica G tiene un árbol de expansión
si y solo si G es conexa.
El árbol de expansión para la grafica G que se presenta, se muestra con línea
seguida.
Existen dos métodos para encontrar el árbol de expansión de una grafica G:
1. Por búsqueda a lo ancho: permite procesar todos los vértices en un nivel
dado antes de moverse al nivel más alto que lo sigue; primero se
selecciona un orden de los vértices, considerando el primer vértice de ese
orden como raíz.
2. Por búsqueda en profundidad: o conocido también como de regreso.
Ejemplo
Utilice la búsqueda a profundidad con el orden h, g, f, e, d, c, b, a de los
vértices para determinar un árbol de expansión de la grafica G.
Tomado h como vértice raíz tenemos:
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 5/14
Árboles de expansión mínimo
Un árbol de expansión comprende un grafo que posee nodos, arcos cada uno con
longitud (peso) no negativa. Para encontrar el árbol de expansión mínima se debe
recorrer todos los vértices del árbol en el que la suma de los pesos de sus aristas
sea mínima, no se incluyen ciclos en la solución.
Un árbol de expansión mínima de G es un árbol de expansión de G con peso
mínimo.
Algoritmo de la ruta más corta en un árbol
Se lo obtiene aplicando el algoritmo de Dijkstra, al recorrer el árbol se lo hace
desde un Vo a un Vf por las aristas cuyos pesos sean menores y la suma del
recorrido sea menor, no es necesario que se abarque todos los vértices.
Ejemplo:
Utilizando el algoritmo de la ruta más corta.
Luego de haber recorrido las diferentes alternativas de la gráfica propuesta
en el texto básico obtenemos como resultado la que Si realizamos la suma
de sus pesos es de 35; sumatoria mínima.
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 6/14
ÁRBOLES BINARIOS
Están entre los tipos de árboles binarios especiales con raíz, su característica es
que todo vértice tiene cuando mucho dos hijos. Donde cada hijo se designa como
un hijo izquierdo o un hijo derecho, además, su posición en el árbol los identifica.
Formalizando se dice que un árbol binario es un árbol con raíz en el que cada
vértice tiene ningún hijo, un hijo o dos hijos. Si el vértice tiene un hijo se designa
como un hijo izquierdo o como derecho (pero no ambos). Si un vértice tiene dos
hijos, un hijo se designa como hijo izquierdo y el otro como hijo derecho.
Un árbol binario completo es un árbol binario en el que cada vértice tiene dos o
cero hijos.
Ejemplo
La altura de este árbol es de 2.
RECORRIDO DE UN ÁRBOL
Existen tres métodos extras que permiten recorrer un árbol, ellos son:
Recorrido pre orden: considera para el recorrido del árbol el siguiente orden (raíz -
izquierda - derecha)
Recorrido entre orden: considera para el recorrido del árbol el siguiente orden
(izquierda -raíz - derecha)
Recorrido post orden: considera para el recorrido del árbol el siguiente orden
(izquierda ± derecha - raíz)
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 7/14
Respuesta:
PREORDEN: * - + A B - * C D / E F A
ENTREORDEN: A + B ± C * D ± E / F * A
POSTORDEN: A B + C D * E F / - - A *
ISOMORFISMOS DE ÁRBOLES
Dos graficas simples G1 y G2 son isomorfas si y solo si existe una función f uno a
uno y sobre del conjunto de vértices de G1 al conjunto de vértices de G2 que
preserva la relación de adyacencia en el sentido de que los vértices vi y vj son
adyacentes en G1 si y solo si los vértices f(vi) y f(vj) son adyacentes en G2.
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 8/14
Existe isomorfismo porque:
f(a) = 1, f(b) = 3, f(c) = 2 , f(d) = 4, f(e) = 5
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 9/14
MODELOS DE REDES Y REDES DE PETRI
MODELOS DE REDES
En un modelo de redes el objetivo consiste en maximizar el flujo del muelle a la
refinería y calcular el valor de este flujo máximo.
INTRODUCCIÓN
En este capítulo se estudian los modelos de redes, que usan gráficas dirigidas, en
esta sección aprenderemos a maximizar el flujo a través de una red. La red podría
ser una red de transporte por la que fluyen bienes, una red de tuberías a través de
la cual fluye el petróleo, una red de computadoras a través de la cual fluyen los
datos, etc. En cada caso el problema consiste en determinar el flujo máximo. La
maximización del flujo en una red es un problema que pertenece a la teoría de
gráficas como a la investigación de operaciones. Las redes de Petri modelan
sistemas en los que el procesamiento puede ocurrir de manera concurrente. El
modelo proporciona un marco de referencia para tratar cuestiones como la posible
operación de estancamiento en un sistema o el hecho de exceder la capacidad de
los componentes de un sistema.
RED DE TRANSPORTE
Considerando la siguiente gráfica dirigida (red de transporte), que representa una
tubería de petróleo. El petróleo se descarga en el muelle a y se bombea por toda
la red de la refinería z. Los vértices b,c,d y e representan estaciones de bombeo
intermedias. Las aristas dirigidas representan subtuberías del sistema y muestran
la dirección en que puede fluir el petróleo. Las etiquetas de las aristas indican las
capacidades de las subtuberías. El problema es encontrar la manera de maximizar
el flujo del muelle a la refinería y calcular el valor de este flujo máximo.
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 10/14
Una red de transporte es una grafica dirigida, simple con pesos que satisface:
a) Un vértice fijo, designado como el origen o fuente, no tiene aristas de
entrada.
b) Un vértice, designado como destino o sumidero, no tiene aristas
salientes.
c) El peso Cij de la arista dirigida (i, j) llamada capacidad de (i, j) es un
número no negativo.
Si observamos la gráfica, el origen es el vértice a y el destino es el vértices z. La
capacidad de la arista (a, b), C_{a, b} es 3 y la capacidad de la arista (b, c), C_{b,
c} es 2. Un flujo en una red asigna un flujo a cada arista dirigida que no excede la
capacidad de esa arista. Más aun, si se supone que el flujo que entra a un vértice
v, que no es el origen y el destino, es igual al flujo que sale de v.
Ejemplo de red de transporte
Tomado con referencia la gráfica
Sea G una red de transporte. Sea C_{ij} la capacidad de la arista dirigida (i, j) . Un
flujo F en G asigna a cada arista dirigida (i, j) un numero no negativo F_{ij} tal que:
a. F_{ij} C_{ij}
b. Para cada vértice j, que no es la fuente ni el destino.
Conservación de flujo b
Conservación de flujo
F_{ij} recibe el nombre de flujo en la arista (i, j). Para cualquier vértice j
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 11/14
Se llama flujo que entra a j y
Se llama flujo que sale de j.Conservación de flujo significa para el ejemplo, que el
petróleo no se usa ni se suministra en las estaciones de bombeo b, c, d y e.
Ahora, vamos a definir un flujo para la red del ejemplo asignando los valores:
F_{ab} = 2, F_{bc} = 2, F_{cz} = 3; F_{ad} = 3, F_{dc} = 1, F_{de} = 2,
F_{ez} = 2
La gráfica quedaría,
Analizando, El flujo que entra al vértice d F_{ad} = 3 y es el mismo que sale del
vértice d,
F_{dc} + F_{de} = 1 + 2 = 3Se debe considerar que una arista e se etiqueta ³x, y´ si la capacidad de e es x y
el flujo en e es y.
Observemos que el flujo que sale del origen (a) Fab + Fad, es igual al flujo que
entra al destino (z) Fcz + Fez
F_{ab} + F_{ad} = 2 + 3 = 5
F_{cz} + F_{ez} = 3 + 2 = 5
Ambos valores son iguales a 5; a este valor lo denominamos valor del flujo F.
Sea F un flujo en una red G. el valor
Se llama el valor del flujo F.
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 12/14
ALGORITMO DE FLUJO MÁXIMO
Si G es una red de transporte, un flujo máximo en G es un flujo con valor máximo.
Diseñar un algoritmo para determinar un valor máximo, consiste en iniciar con
cierto flujo inicial e incrementar de manera interactiva el valor del flujo hasta queno pueda mejorarse más.
Podemos considerar un flujo inicial aquel en el que el flujo en cada arista es igual
a cero.
Para incrementar el valor de un flujo dado, debemos determinar un camino del
origen al destino e incrementar el flujo a lo largo de este camino.
Notación
G denota una red con origen a, destino z y capacidad C
En principio denotaremos aristas no dirigidas
(Camino) P = (V0, V1,«««««., Vn) Vo = a, V = z
Si una arista e en P está dirigida de Vi-1 a Vi decimos que está orientada en forma
propia.
Si podemos determinar un camino P de la forma del origen al destino en donde
cada arista P está orientada en forma propia y el flujo en cada arista es menor que
la capacidad de la arista es posible aumentar el valor del flujo.
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 13/14
Uso del algoritmo para determinar el flujo máximo.
Dada la siguiente red de transporte:
Desarrollo:
Las líneas 1 y 2 del algoritmo, nos permite inicializar el flujo con 0 para cada
una de las aristas de la red.
Las líneas 5 al 9 del algoritmo, permiten etiquetar los vértices como
NULOS.
Las líneas 10 y 11 del algoritmo permite etiquetar el vértice a como (-,) quees un par o dupla de valores, donde el primer elemento identifica el vértice
³predecesor o anterior´ y el segundo valor es el mínimo entre el incremento
(¨) y la diferencia dada por Cvw - Fvw, donde la red resultante es:
En la línea 12 al conjunto U le añadimos el vértice a en este caso (vértice fuente o
inicial).
A continuación la línea 13, da inicio al ciclo WHILE, que permite etiquetar los
vértices que conectan las aristas que salen de a y al mismo tiempo elimina el
5/14/2018 matematicas 33 - slidepdf.com
http://slidepdf.com/reader/full/matematicas-33 14/14
vértice a de U, para nuestro caso las aristas (a, b) y (a, d) controlando que los
vértices b y d no estén etiquetados. Luego de etiquetar los vértices anteriores,
regresamos a la línea 13 y repetimos el ciclo WHILE, pero esta vez tomamos el
vértice b y nos dirigimos a etiquetar el vértice c que se conecta con la arista (b, c)
y c no está etiquetado, se elimina el vértice b y se añade el vértice c a U.
Regresamos a la línea 13 y repetimos el ciclo WHILE, como el vértice z no está
etiquetado, tomamos cualquiera de los vértices que se encuentran en U pero
observando que con los vértices que se conecta no se encuentren etiquetados,
para nuestro caso tomamos el vértice c y cumplimos los requisitos que nos pide el
algoritmo en las líneas que hagamos referencia, para nuestro caso c se conecta
con z y z no está etiquetado, dando como resultado lo siguiente:
Regresamos a la línea 13, ciclo WHILE, pero como z está etiquetado, saltamos a
la línea 35, donde las líneas que le siguen nos permite determinar el conjunto P
con el camino de los vértices comenzando desde z hacia atrás hasta llegar a a,
donde el camino está dado por:
P = (a, b, c, z)
En la línea 43 del algoritmo hacemos ¨ = val(z) y asignamos el flujo a todas las
aristas del camino identificado, conforme lo señalan las líneas del algoritmo que
están a continuación de la línea 43.
La red con estos nuevos datos es la siguiente:
Luego de obtener este primer camino, regresamos al inicio del algoritmo o sea a la
línea 3 y volvemos a ejecutar las instrucciones como se lo hizo al inicio, con esto
se determina otro camino y los flujos respectivos; pero hay que considerar que
ahora algunas de las aristas ya tienen un flujo asignado por el anterior proceso.
top related