Teoría de gráficas: una aplicación de matrices | Matriz de Incidencia

En los últimos años se ha dedicado mucha atención a un área relativamente nueva de la investigación matemática denominada teoría de gráficas. Las gráficas, que se definirán en breve, son útiles en el estudio de la forma en la cual se interrelacionan las componentes de las redes que surgen en el comercio, las ciencias sociales, la medicina y otras áreas más. Por ejemplo, las gráficas resultan de utilidad en el estudio de las relaciones familiares en una tribu, la propagación de una enfermedad contagiosa o una red de vuelos comerciales que comunican a un número dado de ciudades importantes. La teoría de gráficas es un tema de gran amplitud. En esta sección se presentarán únicamente algunas definiciones y se mostrará la cercanía de la relación entre la teoría de gráficas y la teoría de matrices.

A continuación se ilustrará de qué manera surge una gráfica en la práctica

Representación de un sistema de comunicación mediante una gráfica

Suponga que se está analizando un sistema de comunicaciones unido por líneas telefónicas. En este sistema hay cinco estaciones. En la siguiente tabla se indican las líneas disponibles en dirección “a”, y provenientes “de” las estaciones:

Por ejemplo, la marca del cuadro anterior indica que hay una línea de la estación 1 a la estación 2. La información en la tabla se puede representar por una gráfica dirigida como la que se ilustra en la figura: 

Figura 1. La gráfica muestra las líneas de una estación en dirección a las otras.

Gráfica dirigida Vértices Aristas

En general, una gráfica dirigida es una colección de npuntos denominados vértices, denotados por  V₁ , V₂ , . . . V_n , junto con un número finito de aristasque unen distintos pares de  vértices. Cualquier gráfica dirigida se puede representar mediante una matriz de n 3 n en donde el número de la posición ijes el número de aristas que unen el vértice icon el vértice j.

Representación matricial de una gráfica dirigida

La representación matricial de la gráfica en la figura 1 es:

Matriz de Incidencia

Una Matriz que representa una gráfica dirigida que satisfacen las siguientes dos condiciones:

ii) Ningún vértice está conectado consigo mismo.
ii) A lo más una arista lleva de un vértice a otro

Sin embargo, en términos generales es posible tener ya sea un 1 en la diagonal principal de una representación matricial (indicando una arista de un vértice hacia sí mismo) o un entero mayor que 1 en la matriz (indicando más de una trayectoria de un vértice a otro). Para evitar situaciones más complicadas (pero manejables), se ha supuesto, y se seguirá suponiendo, que i) y ii) se satisfacen.

Ejemplo 1: Una gráfica dirigida que describe el dominio de un grupo

Las gráficas dirigidas se utilizan con frecuencia en sociología para estudiar las interacciones grupales. En muchas situaciones de esta naturaleza, algunos individuos dominan a otros. El dominio puede ser de índole física, intelectual o emocional. Para ser más específicos, se supone que en una situación que incluye a seis personas, un sociólogo ha podido determinar quién domina a quién(esto se pudo lograr mediante pruebas psicológicas, cuestionarios o simplemente por observación). La gráfica dirigida en la figura 2 indica los hallazgos del sociólogo. 

Figura 2. La gráfica muestra quién domina a quién en el grupo

La representación matricial de esta gráfica es

No tendría mucho sentido introducir la representación matricial de una gráfica si lo único viable fuera escribirlas. Existen varios hechos no tan visibles que se pueden preguntar sobre las gráficas. Para ilustrar lo anterior considere la gráfica en la figura 3

Figura 3. Existen trayectorias de V1 a V5 aun cuando no hay una arista de V1 a V5. Una de estas trayectorias es
V1  → V2 → V5

Observe que aunque no hay una arista de V1 a V5 es posible mandar un mensaje entre estos dos vértices. De hecho, hay cuando menos dos maneras de hacerlo:

V1 → V2 → V5 (G1)

V1 → V4 → V2 → V5 (G2)

Trayectoria Cadena 

La ruta de un vértice hacia otro se denomina trayectoria o cadena. La trayectoria de V1 a V5 en (G1) se llama 2-cadena porque atraviesa por dos aristas. La trayectoria (G2) se llama 3-cadena. En general una trayectoria que atraviesa por n-aristas (y por lo tanto pasa por n+1 vértices) se llama n-cadena. Ahora, regresando a la gráfica, se puede observar que es posible ir de V1 a V5 a lo largo de la 5-cadena

V₁ → V₄ → V₃ → V₄→ V₂ → V₅ (G3)

Sin embargo, no resultaría muy interesante hacerlo, ya que con una parte de la trayectoria no se obtiene nada. Una trayectoria en la que un vértice se encuentra más de una vez se denomina redundante.La 5-cadena (G3) es redundante porque el vértice 4 se encuentra dos veces.
Es de gran interés poder determinar la trayectoria más corta (si es que existe) que une a dos vértices en una gráfica dirigida. Existe un teorema que muestra cómo esto se puede lograr, pero primero se hará una observación importante. Como se ha visto, la representación matricial de la gráfica en la figura 1 está dada por:

 Se calcula

 

Observe con más cuidado las componentes de A². Por ejemplo, el 1 en la posición (2, 4) es el producto escalar del segundo renglón y la cuarta columna de A:

El último 1 del segundo renglón representa la arista

V₂ →V₅

El último 1 en la cuarta columna representa la arista

V₅→ V₄

Al multiplicar, estos unos representan la 2-cadena

V₂→V₅ → V₄

Si se generalizan estos hechos se pueden probar los siguientes resultados:

Teorema 1:

Si A es la matriz de incidencia de una gráfica dirigida, la componente ij de A² da el número de 2-cadenas de un vértice ia un vértice j.

Teorema 2:

Sea A una matriz de incidencia de una gráfica dirigida. Sea a_ij⁽ⁿ⁾

la componente ij de Aⁿ.

i) Si aij⁽ⁿ⁾ = k, entonces existen exactamente k n-cadenas del vértice i al vértice j.

ii) Más aún, si aij^(m) = 0 para toda m< n y aij⁽ⁿ⁾ ≠0, entonces la cadena más corta del vértice i al vértice j es una n-cadena.

 Trabajando con Scilab

A=[
0 1 0 0 0
1 0 0 0 0
0 0 0 1 0
0 1 1 0 0
1 0 0 1 0
];
disp("A");
disp(A);
disp("A^2:");
disp(A^2);

Share on Google Plus

Acerca del Autor Matemática Positiva

Sitio Web Dedicado al Universo Matemático