Grafos

Prof. Ing. Claudio L. R. Sturla

REPÚBLICA ARGENTINA

GRAFOS
Se puede reproducir libremente. Se agradecerá citar la fuente. THE RECORDING, COPYING, LOAN, UNAUTHORIZED HIRE, PUBLIC SHOWING OR BROADCAST OF THIS DATAGRAM IS STRONGLY ENCOURAGED.

Claudio L. R. Sturla
 Bibliografía: • Chang, Yih—Long, WinQSB, Decision Support Software for MS/OM, John Wiley & Sons, Inc., EE.UU., ISBN0—471—24812—6, 1.998. • Winston, Wayne L., Investigación de Operaciones, Grupo Editorial Iberoamérica S. A. de C. V., México, ISBN 970-625-029-8, 1.994. • Prado, Darci, Administración de Proyectos con PERT/CPM,Editorial Paraninfo, Madrid, ISBN 84-283-161349, 1.988

Introducción
Un casillero cuadrado puede considerarse que representa una bipartición entre una parte de casillas sombreadas, que poseen lapropiedad Ρ y otras que no poseen la propiedad Ρ La matriz de aplicaciones multívocas es: 1 1 2 3 4 5 6 7 8 9 10 El gráfico de la página anterior parece un perro. También existen plazas donde la circulación es: redes_grafos-1.doc 13 2 3 4 5 6 7 8 9 10

Prof. Ing. Claudio L. R. Sturla 2 1

7

8 6

3

4

5 Algunos problemas importantes de optimización pueden analizarse mejor mediante unarepresentación gráfica o en forma de una red. Nosotros sólo estudiaremos los grafos orientados.

Definiciones básicas
Se define un grafo, o una red, mediante dos conjuntos de símbolos: nodos (o nudos) y arcos. Primero definimos un conjunto (llámelo V) de puntos, o vértices. Los vértices de un grafo o red se llaman también nodos. También definimos un conjunto de arcos A DEFINICIÓN: Un arco estáformado por un par ordenado de vértices y representa una dirección posible de movimiento que puede ocurrir entre vértices. Si una red contiene un arco (j, k); es posible tener un movimiento desde el nodo j hacia el nodo k Supóngase que los nodos 1, 2, 3 y 4 de la Figura 1, representan ciudades, y que cada arco representa una carretera (de un solo sentido) que comunica dos ciudades. Para esta red, V= { l,2,3,4} y A = {(l,2), (2,3), (3,4), (4,3), (4,l)} Para el arco (j, k), el nodo j es el nodo inicial del arco, y cl nodo k es el nodo final del arco. Se dice que el arco (j, k) va del nodo j al nodo k Así, el arco (2,3) tiene como nodo inicial el nodo 2, y como nodo final el nodo 3, y va del nodo 2 al nodo 3. Se puede considerar el arco (2,3) como una carretera (de un solo sentido) en la cualpodemos viajar de la ciudad 2 a la ciudad 3. En la Figura 1, los arcos muestran que se permite viajar de la ciudad 3 a la ciudad 4, y de la ciudad 4 a la ciudad 3, pero que los viajes entre las otras ciudades se pueden realizar solamente en un solo sentido. redes_grafos-1.doc 14

Prof. Ing. Claudio L. R. Sturla Figura 1 Ejemplo de una red 1 4

2

3

Frecuentemente estudiaremos un grupo ocolección de arcos. Las siguientes definiciones proporcionan maneras convenientes para describir ciertos grupos o colecciones de arcos. DEFINICIÓN: Una sucesión de arcos, en la cual cada arco tiene exactamente un vértice en común con el arco anterior, se llama cadena. DEFINICIÓN: Una ruta es una cadena, en la cual el nodo final de cada arco es idéntico al inicial del arco siguiente. Por ejemplo,en la Figura 1, (1, 2) — (2, 3) — (4, 3) es una cadena, pero no una ruta; (1, 2) — (2, 3) — (3 ,4) es una cadena. La ruta (1, 2) — (2, 3) — (3,4) representa un camino para viajar del nodo 1 al nodo 4.

Problemas del Camino Óptimo
En esta sección suponemos que se asocia a cada arco una función de valor. Suponga que empezamos en un nodo en particular (por ejemplo, el nodo 1). El problema deencontrar el camino más corto (el camino de longitud mínima) desde el nodo 1 hasta cualquier otro nodo de la red se llama problema del camino más corto. Ejemplo 1 Powerco tiene tres plantas de generación de energía eléctrica que la suministran a cuatro ciudades. Cada planta puede suministrar las siguientes cantidades (kwh) de energía eléctrica: la planta 1, 35 millones; la planta 2, 50 millones;...