Aplicaciones prácticas
Un problema de comunicaciones
Una señal de radio transmitida por una estación puede ser retransmitida por estaciones vecinas las cuales formando una cadena pueden llevarla hasta los confines más remotos.
Cuando el número de estaciones retransmisoras aumenta, puede ser dificil determinar si la señal que sale de una estación puede llegar a otra directamente o al menos utilizando algunos relevos.
Suponiendo que las estaciones 1,2,3,4,5, y 6 establecen canales de comunicación como los que muestra la siguiente figura:
Debemos determinar si una señal transmitida por una estación puede llegar a otra.
En la figura anterior puede observarse que la estación 1 está aislada de las otras estaciones y que la estación 3 no puede enviar señal a la estación 2, pese a que puede recibir señal de aquella.
Algunas estaciones tienen comunicaciones de doble vía.
Es un hecho que la estación 2 puede enviar señales a la estación 6 utilizando las rutas
2--->3--->4---->6, 2--->3--->5--->6, 2--->5--->6, 2--->5--->3---->4---->6.
El gráfico de la figura anterior podría representar también posibilidades de soborno o tráfico de influencias, que son desgraciadamente comunes en nuestra sociedad, entre las personas 1, 2, 3, 4, 5 y 6.
En el gráfico anterior observaríamos que el señor 1 no soborna y es insobornable, y que el señor 6, entre otros, puede ser sobornado por todos, excepto por el incorruptible señor 1 (nuestro héroe). A veces a alto costo por el número de intermediarios que se pueden requerir.
Si el gráfico anterior representa cómo una perturbación sufrida por uno de los focos, se transmite a los restantes, podemos ver que la más alta posibilidad de perturbación se halla en los focos 4 y 6 pues se perturban al perturbar cualquier otro foco distinto de 1.
Gráficos como el de la figura pueden esquematizar relaciones genéticas entre individuos o generaciones, retrasmisiones de repetidoras o vias de comunicación.
Retornemos al caso de las estaciones de radio!.
Si el número de estaciones y de relaciones aumenta, gráficos como el de la figura anterior pueden parecer al observador tan indescifrables como el gráfico siguiente:
La matriz C que llamaremos la matriz de las comunicaciones directas, condensa toda la información del gráfico.
La matriz C = (cij )6x6 , ha sido definida de tal manera que cij = 1, para i = j, si la señal de la i-ésima estación es recibida directamente por la j-ésima estación.
Por definición cii = 0 para todo i (no aceptamos retrasmisión de una estación a sí misma).
Podemos plantearnos la pregunta:
Cuáles estaciones se pueden comunicar entre sí enviando sus señales por intermedio de otras estaciones (relevos) ?.
Motivaremos la respuesta a esta pregunta observando un elemento en la matriz C2.
Estudiemos por ejemplo el elemento situado en la 2da. fila, 4ta. columna de C2. Tal elemento es:
.
c21 . c14 + c22 . c24 + c23 . c34 + c24 .c44 + c25 . c54 + c26 . c64
Cada elemento c2k . ck4 de la suma anterior es 0 o 1. Además: c2k . ck4 es 1 sólo en el caso de que c2k = 1 y ck4 = 1. Es decir, sólo en caso de que la señal de la estación 2 pueda ser retransmitida a la estación 4, pasando por la estación intermedia k.
En consecuencia la suma anterior, cuenta de cuántas maneras se puede enviar la señal de la estación 2 a la estación 4, utilizando exactamente una estación como intermediaria ( un relevo).
Asumimos de nuevo que los elementos de la diagonal de C2, se reemplazan por ceros.
Por un razonamiento similar se concluye que cada elemento de la fila i, columna j, de C3, dá exactamente el número de maneras como la señal de la estación i puede llegar a la estación j, utilizando exactamente dos relevos.
Verifiquemos el caso de C2.
En tal matriz, b36 = 2, ya que las cadenas que se pueden utilizar para enviar la señal de la estación 3 a la estación 6, a partir del gráfico inicial de la página 17, utilizando exáctamente un relevo son:
3--->5--->6 y 3---->4---->6,
mientras que b25 = 1, ya que la única cadena que lleva la señal de la estación 2 a la estación 5, utilizando exactamente un relevo es:
2---->3---->5.
El elemento C23,3 = 1, está informándonos de la cadena
Dependiendo del problema, esta cadena puede tenerse o no, en cuenta. En nuestro caso hemos decidido eliminarla ya que no queríamos que nos estorbara ese tipo de retrasmisión tipo eco. Sin embargo, es posible que estos ecos deban ser tomados en cuenta como lo haremos a continuación estudiando los casos C, C2 y C3 cuando aceptamos 1’s en la diagonal.
Similarmente, el elemento en la posición i,j de C3 nos dice de cuántas maneras se puede enviar la señal de la estación i a la estación j utilizando exactamente 2 relevos.
En general, el elemento en la posición i,j, fila i, columna j de Ak , para cualquier k, cuenta de cuántas maneras, la señal de la estación i puede llegar a la estación j, utilizando exactamente k - 1 relevos.
