ANALISIS DE REDES

ANALISIS DE REDES

CONCEPTOS PREVIOS

2.1 Problema De Transporte

2.1.1 Método Esquina Noroeste

2.1.2 Procedimiento De Optimizacion

2.2 Problema Camino Más Corto

2.3 Problema Árbol Expandido Mínimo

2.4 Problema Flujo Máximo

2.5 Ruta Crítica Pert Cpm

CONCEPTOS BÁSICOS SOBRE GRAFOS

Grafo: Un grafo G es una dupla G = (X, U), donde X es un conjunto finito y no vacío de elementos llamados vértices y U es el conjunto cuyos elementos se componen de subconjuntos de X de cardinalidad dos (2), llamados aristas.

Los vértices de X se llaman usualmente x1, x2, x3,…, xn y se representan como puntos, las aristas u1, u2, u3,…, um se dibujan como líneas.

Grafo orientado: Un grafo G* es orientado, cuando sus aristas tienen asignadas direcciones, o sea cuando existe una relación de precedencia entre los elementos. Sus puntos se llaman nodos, y sus líneas arcos. En estos casos U es una familia de pares ordenados resultantes del producto cartesiano de X.

U XxX = { ui = (xk,xj): 1 i |U|, 1 j, k |X|, xk, xj X}

Ejemplo:

G* = ({x1,x2,x3}, {(x1,x2), (x3,x1), (x3,x2)}) .

En realidad, no existen dos especies de grafos, orientados y no orientados, sino que todos los grafos son orientados, pero por razones conceptuales, es poco cómodo considerar las líneas x3 orientadas para los problemas de naturaleza no orientada.

Cada vez que apliquemos un concepto orientado en un grafo G = (X,U) ese concepto deber ser considerado como aplicable de hecho, en un grafo orientado G* al que le corresponde la orientación en los dos sentidos de cada arista.

Orden es el número de vértices del grafo, el cardinal del conjunto X de vértices: |X|

Arcos incidentes a un nodo

Si un vértice x es extremidad inicial de un arco u = (x,y) y x y, diremos que el arco es incidente a x hacia el exterior. I+(x)={y / (x,y) U}. I-(x)={y / (y,x) U}

El número de los arcos incidentes hacia el exterior se llama semigrado exterior de x y se nota d+(x) = |I+(x)|

De igual forma se define arco incidente a x hacia el interior y semigrado interior de x. Este último se nota como d-(x) = |I-(x)|.

Grado de x, es la suma del semigrado exterior e interior de x. O sea, es el número de arcos con una extremidad en x.

d(x) = d+(x) + d-(x)

Si todos los vértices tienen el mismo grado, el grafo al que pertenecen se llama grafo regular.

Recorrido de grafos.

Cadena (concepto no orientado):

Es una secuencia de aristas de G, tal que cada arista de la secuencia tiene un extremo común con el arco precedente y otra con el siguiente.

Largo de una cadena, es el número de aristas de la secuencia.

Cadena elemental, es aquella que no repite vértices. Cadena simple, es aquella que no repite aristas. Camino (concepto orientado)

Es una cadena = {u1, u2,…, uq} en la que para todo ui (con i q) el

extremo terminal de ui coincide con el extremo inicial de ui+1.

Las definiciones de largo de un camino, camino elemental y camino simple son análogas a las de cadenas, con la salvedad de la orientación.

Sendero, es un camino elemental (que no repite nodos).

Vía, es un camino cuyos arcos se pueden recorrer en su sentido directo o contrario.

Ejemplo: roblema del camino entre dos puntos. El siguiente es un ejemplo de como modelar una porción del universo, su problemática y como resolverla.

Supongamos que un hombre debe pasar a la otra orilla de un río llevando consigo una oveja, un repollo y un lobo. El inconveniente que se le plantea es que sólo puede cruzar con uno de ellos a la vez y sospecha que si deja solos a la oveja con la repollo ó con el lobo, la oveja se comerá al repollo ó el lobo se comerá a la oveja. Teniendo en cuenta estas restricciones, el sujeto dibuja sobre la arena de la orilla un grafo y aplicando alguna heurística o algún algoritmo conocido, encuentra el camino que debe seguir para llegar a la otra orilla con su carga intacta.

Utilice el siguiente procedimiento:

0) Dibuja el grafo: Existen 4 elementos que determinan las situaciones en cada orilla, ellos son:

H – Hombre C – Repollo L – Lobo O – Oveja

1) Enumera las situaciones en una de

...