Extensiones
Matrices y Determinantes.- Extensiones
Modelización con grafos. Un ejemplo clásico
Un grafo es, como vamos a precisar más adelante, una generalización de un diagrama del tipo de una red, donde hay varios puntos o nodos que se interconectan de algún modo. Este tipo de diagramas son muy comunes en diferentes campos; algunos ejemplos pueden ser una red de carreteras, una cadena de montaje, el organigrama de una corporación, el diagrama de flujo de un programa informático...
Figura 1: Plano de Könisberg en la época del trabajo de Euler
La primera publicación donde se utilizaron los grafos, fue hecha por el matemático suizo Leonhard Euler en 1741 (Commentarii academiae scientiarum Petropolitanae, 8)donde recogía una aportación que había presentado a la Academia de San Petesburgo en 1735. Su trabajo tiene que ver con la resolución de un problema que se podría considerar casi como un acertijo de matemática recreativa: el conocido como problema de los puentes de Könisberg. Este consistía en ver si era posible en dar un paseo por Könisberg, saliendo de cualquier punto de la ciudad, pasar una sola vez por todos y cada uno de los siete puentes que cruzaban los diferentes ramales del río Pregel y volver al punto de partida. En la Figura 1 se puede ver un plano de la época de Euler esta ciudad, que fue capital de Prusia Oriental y en la actualidad pertenece a Rusia. Hemos marcado con una línea azul los distintos ramales del río, los puentes están rodeados por una circunferencia y hemos numerado las distintas zonas terrestres aisladas por el río.
Euler modelizó la situación, centrándose en ver la conexiones que existían entre estas 4 regiones terrestres distintas en que el río dividía a la ciudad y las conexiones existentes entre las mismas, con lo que el esquema que estudió fue más o menos el de la Figura 2, y el problema consiste en saber si existe un recorrido que comience y acabe en cada uno de uno de los nudos de esta red pasando por todos los demás y sin recorrer dos veces el mismo arco (puente). La respuesta de Euler fue que no era posible, puesto que entonces el número de arcos que llega a cada nodo intermedio del recorrido ha de ser par (puesto que se ha de entrar por uno y salir por otro distinto), y lo mismo ocurriría con el propio nodo inicial, puesto que ha de coincidir con el final. Si se observa el esquema (grafo) de la Figura 2 nos encontramos con que a todos los nodos (vértices) llega un número impar de arcos. Está claro que el diagrama (modelo) permite observar el problema mucho más fácilmente y determinar cuáles son los elementos importantes del mismo.
Figura 2: Grafo asociado al problema de los puentes de Könisberg
No resulta difícil identificar otras muchas situaciones que son susceptibles de una modelización similar. Entre ellas están todas las que implican operaciones secuenciales en distintas etapas, que se relacionan entre sí. En ocasiones los grafos se utilizan para representar proyectos con múltiples tareas que guardan relaciones de prelación. Pondremos algún ejemplo en este sentido y además vamos a utilizar el álgebra matricial para resolverlo, por medio de la asociación a cada grafo de su matriz de incidencia.
Grafos orientados. Representación gráfica y matricial
Definición: Llamaremos grafo orientado al par G = (X,I'), donde X es un conjunto y I' un subconjunto de X x X. A los elementos de X los denominaremos vértices o nodos y si (x,x') ∈ I'(x) diremos que hay un arco orientado que va de x a x',(x,x')
En esta introducción representaremos los grafos fundamentalmente de dos modos. El primero es un gráfico en el que se asigna a cada vértice un punto del plano y, si existe el arco (x,y), entonces se traza un segmento orientado que une el punto correspondiente a x con el punto correspondiente a y. La otra representación la haremos a través de una matriz cuadrada A. Para ello hemos de numerar los vértices (X = {v1,...,vn}) y A = (aij) será una matriz cuadrada de orden n tal que aij = 1 si (vi,vj) ∈ I' y aij = 0 si (vi,vj) ∉ I'
Por ejemplo, sea el grafo G = (X I') donde X = {1, 2, 3, 4, 5) e I' = {(1,2), (1,5),(2,3), (2,5),(3,2),(3,4), (4,5),(5,4)}. Su diagrama sería:
Figura 3: Diagrama de grafo (X,I')
Y la matriz asociada:
\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right)
La matriz asociada a un grafo recoge toda la información sobre él de un modo que es, además, muy fácil de manejar en entornos informáticos. La fila i-ésima de la matriz indica a qué vértices se puede llegar por un arco desde el vértice i-esimo y la columna j-ésima desde qué vértices se puede llegar por un arco al vértice j-ésimo. Así, por ejemplo, si la matriz asociada a un grafo es simétrica esto indica que cada vez que existe un arco entonces también existe un arco (vi,vj), que es precisamente la definición de grafo simétrico (los grafos de este tipo son muy abundantes: por ejemplo una red de carreteras es un grafo simétrico puesto que cada trayecto entre dos puntos es de ida y vuelta).
Estas matrices binarias, formadas solamente por ceros y unos se denominan matrices booleanas y en numerosas aplicaciones de todo tipo se utiliza este lenguaje binario, vinculado directamente a la lógica bivalente.
Aplicación I: Función ordinal en un grafo sin circuitos. Algoritmo de Kaufmann
En ocasiones los grafos se utilizan para representar proyectos con múltiples tareas que guardan entre sí una relación de prelación del tipo "la tarea A ha de realizarse antes de la B". En una primera aproximación a una situación de este tipo es preciso establecer una cierta jerarquización en el grafo, es decir, una partición del mismo en niveles Ni de modo que si un vértice vi precede a otro vj el nivel al que el primero pertenece es anterior al nivel al que pertenece el segundo. De entre los algoritmos que facilitan esta clasificación vamos a ver uno de Kaufmann.
En primer término construyamos el grafo asignando a cada tarea un vértice y trazando un arco (vi, vj ) cada vez que la tarea vi preceda obligatoriamente a la vj . Hay que hacer notar que un grafo que representa una situación de este tipo no puede tener una sucesión de arcos que nos lleven desde un vértice hasta él mismo (lo que se denomina un circuito) porque de ser así estaríamos ante un círculo vicioso, donde una actividad se precede a sí misma.
Una vez escrita la matriz del grafo sumamos todas sus columnas, con lo cual, en la columna C0 resultante la i-ésima componente indica el número de tareas a las que precede obligatoriamente la tarea vi. Eliminaremos aquellas tareas cuyo índice correspondiente sea 0, que pertenecerán al último de los niveles, y repetimos lo mismo con el subgrafo resultante de eliminarlas, o lo que es lo mismo, restamos a C0 la suma de las columnas correspondientes a estas tareas. Así ob- tenemos C1 y se itera el proceso. Pertenecerán a la fase i aquellas tareas cuya coordenada en la columna Ci sea nula. Si el algoritmo se hace por filas tendríamos la ordenación inversa, pero hay además otra diferencia: mientras antes cada tarea aparece incluida en el nivel más tardío de todos los que puede estar, al hacerlo por filas lo hace en el más temprano, de modo que la combinación de ambas posibilidades ofrece una mayor información sobre el proyecto.
Ejemplo 1
Vamos a ilustrar el algoritmo en primer lugar con un ejemplo muy sencillo. Su- pongamos que el jefe del departamento de ventas de una empresa ha de preparar un informe sobre las actividad del último trimestre. Para ello necesita recibir cier- tos datos del servicio de contabilidad. Con algunos de estos datos, junto con otros que ya posee, el equipo de analistas le elaborará un informe técnico. También ha de hacer una reunión con el equipo de comerciales para preparar su informe.
Las tareas que ha de realizar por tanto son cuatro:
A .- Solicitar y recibir los datos del servicio de contabilidad
B .- Solicitar y recibir el informe de los analistas
C .- Mantener la reunión con los vendedores
D .- Preparar el informe
Figura 4: Grafo del ejemplo 1
Los órdenes de prelación serían: A precede a B y a D, B precede a D y C precede a D . Con estos datos el grafo sería el de la figura 4, y la matriz asociada (manteniendo el orden natural A1, B2, C3 y D4)
M=\left( \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right)
Sumamos todas las columnas y la columna C0 resultante es:
C_0=\left( \begin{array}{c} 2 \\ 1 \\ 1 \\ 0 \end{array} \right)
En la que solo es 0 el elemento correspondiente a la D que se situará en el primer nivel. La columna C1 la obtendremos restando a la anterior la columna de la matriz M correspondiente a la actividad D, es decir la cuarta columna (ignorando ya el coeficiente que corresponde a D ).
C_1=\left( \begin{array}{c} 2 \\ 1 \\ 1 \\ 0 \end{array} \right)- \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ - \end{array} \right)=\left( \begin{array}{c} 1 \\ 0 \\ 0 \\ - \end{array} \right)
En este segundo nivel se han anulado los coeficientes correspondientes a las tareas B y C. La siguiente iteración, la columna C2, la obtendremos restando a C1 la suma de las columnas correspondientes a C y D
C_2=\left( \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array} \right)- \left( \begin{array}{c} 1 \\ - \\ - \\ - \end{array} \right)=\left( \begin{array}{c} 0 \\ - \\ - \\ - \end{array} \right)
Es decir en el tercer nivel estará la actividad A. Con esta información el proyecto comenzaría con la actividad A, una vez que esta concluyera se realizarían la B y la C (pueden hacerse simultáneamente), y cuando concluyan la D.
Si hacemos el algoritmo por filas tendríamos: F0 = (0 1 0 3) es decir en el primer nivel están las actividades A y C; F1 = ( - 0 - 1) es decir, en el segundo nivel estaría la actividad B y finalmente, F2 = ( - - - 0) es decir, en el tercer nivel está la actividad D. Esto indica que se pueden comenzar realizando las actividades A y C simultáneamente, cuando concluyan la B y posteriormente la D. El resultado es distinto al anterior, porque como comentábamos antes, el algoritmo por filas informa de la etapa más temprana en que puede realizarse una actividad y el algoritmo por columnas de la etapa más tardía.
Ejemplo 2
El ejemplo anterior es tan sencillo que lo hubiéramos resuelto inmediatamente sin necesidad de un grafo, pero cuando las actividades y las relaciones entre ellas son un número relativamente grande, es necesario un procedimiento algorítmico como el que hemos descrito. Veamos un caso más complejo.
Supongamos que hay 13 operaciones tecnológicas, A, B, . . . , M cuyas relaciones se dan a continuación (el símbolo < debe leerse "precede obligatoriamente"):
A < G, A < H, A < J, A < L, B < A, C < A, C < B, C < F, D < C
D < F, E < B, E < C, E < D, E < F, F < H, F < J, G < I, H < L, H < M
J < K, J < L, J < M, K < I, K < M, L < I, L < M, M < I
El grafo que representa este proyecto lo tenemos en la figura 5. Utilicemos el algoritmo de Kaufmann por filas y columnas:
Cuadro 1: Función ordinal sobre un grafo sin circuitos. Algoritmo de Kaufmann
Figura 5: Representación gráfica del ejemplo
Aplicación II: Caminos hamiltonianos. El método de la multiplicación latina
Dado un grafo un camino es una sucesión de arcos del tipo:
(vi1 , vi2 ), (vi2 , vi3 ), . . . , (vik−2 , vik−1 ), (vik−1 .vik )
Es decir una sucesión de arcos donde la extremidad final de cada uno es precisa- mente la extremidad inicial del siguiente. Un camino es hamiltoniano si recorre todos los vértices del grafo sin pasar nunca dos veces por el mismo. La existencia de caminos hamiltonianos y su determinación son problemas clásicos de la teoría de grafos (el conocido "problema del viajante", que ha de encontrar una ruta óptima para recorrer todos los nodos de una red sin pasar dos veces por el mismo, consiste en hallar un camino hamiltoniano de longitud mínima).
En esta sección veremos un conocido algoritmo para calcular todos los caminos hamiltonianos de un grafo conocido como el método de multiplicación latina. Para ello nombraremos cada vértice del grafo x1, . . . , xn con una letra, y lo representaremos por medio de una matriz cuadrada de orden n, A1, llamada "matriz latina", cuyo término aij será 0 si no existe el arco (xi, xj ) y en el caso de que sí exista escribiremos la letra correspondiente al vértice xi seguida de la correspondiente a xj . Si en la secuencia se repite una letra (es decir, si hubiera un arco que va de un vértice a sí mismo, lo que se denimina un bucle) pondremos también un 0. Así, en la matriz A1 podemos leer los "nombres"de todos los arcos del grafo (entendiendo por nombre la secuencia extremidad inicial - extremidad final, excepto los de los bucles (que nunca podrían formar parte de un camino hamiltoniano, porque pasan dos veces por el mismo vértice). Llamaremos A1* a la matriz obtenida a partir de A1 quitando, simplemente, las letras correspondientes a las extremidades iniciales de cada arco. Los caminos de longitud i en los que no se repite ningún arco se obtienen a partir de la matriz Ai , que se define por recurrencia como sigue: Ai = Ai−1 . A1* donde el signo ´ denota una multiplicación de ambas matrices que sigue las siguientes reglas:
- El término (i, j) del "producto latino"se obtiene "multiplicando"la fila i- ésima de la primera matriz por la j-ésima columna de la segunda, como en el producto matricial habitual.
- Pondremos 0 en la posición (i, j) del producto si ∀k = 1, . . . , n en cada uno de los productos del elemento (i, k) por el elemento (k, j) al menos uno de ellos es 0.
- El producto de secuencias de letras se hace por simple yuxtaposición, teniendo en cuenta que si en la secuencia resultante se repite una letra, entonces esa secuencia es nula (i.e. AB · C = ABC, AB · A = 0)
- Si al realizar el producto de una fila por una columna se obtienen varias secuencias de letras no nulas, todas ellas pasarán al término correspondiente del producto.
Veámoslo con un ejemplo:
Figura 6
El grado de la figura 6 tiene asociadas las siguientes matrices latinas A1 y A1* :
A_1= \left( \begin{array}{cccccc} 0 & 0 & AC & 0 & 0 & 0 \\ BA & 0 & BC & 0 & BE & 0 \\ 0 & CB & 0 & 0 & 0 & CF \\ 0 & 0 & DC & 0 & 0 & DF \\ 0 & 0 & 0 & ED & 0 & EF \\ FA & 0 & 0 & 0 & FE & 0 \end{array} \right)
A^*_1= \left( \begin{array}{cccccc} 0 & 0 & C & 0 & 0 & 0 \\ A & 0 & C & 0 & E & 0 \\ 0 & B & 0 & 0 & 0 & F \\ 0 & 0 & C & 0 & 0 & F \\ 0 & 0 & 0 & D & 0 & F \\ A & 0 & 0 & 0 & E & 0 \end{array} \right)
Hallemos los caminos elementales de longitud 2:
A_2=A_1 \cdot A^*_1 = \left( \begin{array}{cccccc} 0 & ACB & 0 & 0 & 0 & ACF \\ 0 & 0 & BAC & BED & 0 & BCF/ BEF \\ CBA/CFA & 0 & 0 & 0 & CBE/CFE & 0 \\ DFA & DCB & 0 & 0 & DFE & DCF \\ EFA & 0 & EDC & 0 & 0 & EDF \\ 0 & 0 & FAC & FED & 0 & 0 \end{array} \right)
Los de longitud 3:
A_3=A_2 \cdot A^*_1 = \left( \begin{array}{cccccc} 0 & 0 & 0 & 0 & ACBE/ ACFE & 0 \\ BCFA/BEFA & 0 & BEDC & 0 & BCFE & BACF/ BEDF \\ 0 & 0 & 0 & CBED/CFED & 0 & CBEF \\ DCBA/DCFA & 0 & DFAC & 0 & DCFE/DCBE & 0 \\ EDFA & EDCB & EFAC & 0 & 0 & EDCF \\ 0 & FACB & FEDC & 0 & 0 & 0 \end{array} \right)
Los de longitud 4:
A_4=A_3 \cdot A^*_1 = \left( \begin{array}{cccccc} 0 & 0 & 0 & ACBED/ACFED & 0 & ABCEF \\ BEDFA & 0 & BEFAC & BCFED & BACFE & BEDCF \\ CBEFA & 0 & 0 & 0 & 0 & CBEDF \\ 0 & DFACB & 0 & 0 & 0 & DCBEF \\ EDCBA/EDCFA & EFACB & EDFAC & 0 & 0 &0 \\ 0 & FEDCB & 0 & 0 & FACBE & 0 \end{array} \right)
Y finalmente los de longitud 5, es decir, los caminos hamiltonianos:
A_5=A_4 \cdot A^*_1 = \left( \begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & ACBEDF \\ BEDCFA & 0 & BEDFAC & BACFED & 0 & 0\\ CBEDFA & 0 & 0 & 0 & 0 & 0 \\ DCBEFA & 0 & 0 & 0 & DFACBE & 0 \\ 0 & EDFACB & 0 & 0 & 0 &0 \\ FEDCBA & 0 & 0 & FACBED & 0 & 0 \end{array} \right)
Obra publicada con Licencia Creative Commons Reconocimiento Compartir igual 4.0