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 las orillas comenzando por H,C,L,O.

2) Luego las ordena considerando:

a) se encuentra el hombre en esa orilla o no:  H vs noH.

b) pasaje o secuencia de una situación a otra. (obs. que no se puede pasar de una situación en la que esté el hombre a otra en la que también esté)

3) Por último  busca en el grafo un camino del estado inicial al  estado final.

 

 

Clasificacion De Grafos

Multigrafo, es un grafo no orientado con múltiples aristas entre pares de nodos.

Grafo simple, es un grafo sin bucles, sin múltiples aristas entre pares de vértices.

Grafo completo

Para todo par de vértices de G, existe por lo menos una arista que los une.

Por lo tanto, un grafo completo de n vértices  es aquel que tiene sus n vértices mutuamente adyacentes.

n-clique, es un grafo completo simple de n vértices. Se nota Kn.

 

Subgrafo de G = (X,U) engendrado por el conjunto A       X, es un grafo  cuyos vértices pertenecen al conjunto A y cuyas aristas son aquellas de G que tienen las dos extremidades en A.

Grafo parcial de G = (X,U) engendrado por V       U, es el grafo G’ = (X,V) cuyos vértices son los mismos de G y cuyas aristas son las que conforman el conjunto V     U.

Subgrafo parcial de G, es un subgrafo de un grafo parcial de G.

Grafo bipartito, es un grafo cuyo conjunto de vértices puede ser particionado en dos clases X1 y X2 de tal forma que dos vértices de la misma clase no sean jamás adyacentes. Se nota  G = (X1,X2,U)

 

 

Grafo bipartito completo, es aquel en el que    para todo elemento de X1 y todo elemento de X2 existe por lo menos un arco que los liga.

Un grafo simple bipartito completo con p elementos en X1 y q elementos en X2 se nota Kp,q.

Grafo Regular, es aquel en el que todos sus vértices tienen el mismo grado.

Grafo Ponderado G = (X, U, W) donde (X, U,) es un grafo y W es una función W: U Z+ (Z+: enteros positivos) .

Si u      U, w(u) es llamado el peso de la arista u. Estos pesos corresponden, según la aplicación, a costos, capacidades u otras propiedades de las aristas o arcos.

Cuando se desea asignar valores negativos o reales a los pesos de las aristas, se debe tener especial cuidado en la elección de los algoritmos ya que la correctitud de los mismos puede depender de la restricción a Z+.

Grafo Conexo, es aquel en el que  para cada par de vértices de G, existe una cadena que los une.

En grafos orientados se definen 2 conceptos

a)  Débilmente  conexo: si  existe  una  cadena  (sin  tener  en  cuenta  la orientación) que une cada par de nodos distintos.

b) Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y.

Una componente conexa de un grafo G, es un subgrafo de G engendrado por los vértices que pueden unirse a un vértice xi dado, mediante una cadena (puede ser todo el grafo G)

 

Ciclos y Circuitos

Ciclo, es  una  cadena  simple,  cuyos     dos  vértices  extremos,  inicial  y  terminal, coinciden (no tiene en cuenta  la orientación).

Si queremos describir la orientación en un ciclo designamos como:

u+ = {ui : ui orientada en el sentido del ciclo}

u– = {ui : ui orientada en el sentido contrario al ciclo}

Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el  primero  que coincide con el último). Lo notamos uE = (u1,…,un).

Propiedad 1: Todo ciclo uC es una suma de ciclos elementales sin aristas comunes.

Propiedad 2: Un ciclo es elemental si y solo si es un ciclo minimal (es decir que no se pueden deducir otros ciclos por supresión de aristas).

Seudociclo, es una cadena donde los extremos coinciden pero que una misma  arista puede figurar más de una vez (también consecutivamente).

Cociclo del conjunto de vértices A, es el   conjunto de aristas incidentes a A, del tipo  I(A) no  vacío  y particionado en dos clases I+(A) y I-(A).

 

 

Ciclo  Euleriano es  aquel  que  incluye  todas  las  aristas  del  grafo  una  sola  vez, conteniendo cada vértice por lo menos una vez.

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple) tocando todos los vértices del grafo.

Todo multigrafo que posee un ciclo Euleriano es  conexo y todos sus  vértices tienen grado par .

VIDEO SOBRE TEORIA DE GRAFOS

 

Tema 2.1: Problema de Transporte