calculo.cc

Matrices y grafos

Grafos

Un grafo está definido por un conjunto de puntos, llamados vértices o nodos y un conjunto de pares de vértices, denominados aristas o arcos.


Podemos considerar un grafo con vértices { a, b, c, d, e } y aristas { ab, ad, ae, bc, cd, de }

Como podemos ver en el ejemplo, los vértices se representan como puntos y cada arista entre dos vértices como una línea que une dichos vértices.

Un grafo no dirigido es aquel que tiene sus aristas o arcos sin orientar.

Un grafo dirigido o digrafo es aquel que tiene sus aristas o arcos orientados, es decir, sus aristas vienen dadas por pares ordenados.


Podemos considerar un grafo dirigido con vértices { a, b, c, d, e } y aristas { ab, ae, bc, bd, cd, da }



En este caso también los vértices se representan como puntos. Las aristas se representan como flechas que parten de un vértice (el primero de cada par) y llegan a otro (el segundo de cada par).

Matriz de adyacencia o asociada

Todo grafo, dirigido o no, puede representarse mediante una matriz cuadrada que tiene como orden el número de vértices del grafo. Dicha matriz recibe el nombre de matriz asociada o matriz de adyacencia

Ejemplos de matrices de adyacencia

1) Construcción de la matriz de adyacencia de un grafo no dirigido:

Para construir las matrices de adyacencia, ordenamos los vértices, por ejemplo



Si tenemos una arista que une los vértices a y b, en la matriz de adyacencia tenemos que poner un 1 tanto en la posición   ab   como en la posición   ba.

La matriz de adyacencia de los grafos no dirigidos siempre es simétrica.



2) Construcción de la matriz de adyacencia de un grafo dirigido:

Para construir las matrices de adyacencia, ordenamos los vértices, por ejemplo:

Si tenemos una flecha que parte del vértice a y llega al vértice e , ponemos un 1 en la posición   ae   de la matriz de adyacencia. En caso de no tener esa flecha ponemos un 0.

La matriz de adyacencia de un grafo no dirigido no tiene por qué ser simétrica.



3) Escribe las matrices de adyacencia o asociadas a cada uno de los siguientes grafos:

  1.      
  2.      
  3.      

Camino y longitud de un camino

Llamaremos camino entre los vértices a y b a cualquier sucesión de aristas que conecte a y b. La longitud del camino será el número de aristas que lo componen.

Ejemplos de caminos y longitud de caminos

El mapa de las caminos de una isla entre las casas de los vecinos viene dado por el siguiente grafo (las aristas representan caminos y los vértices casas):

Hallar cuántos caminos de longitud 2 y 3 conectan cada par de casas de dicho mapa.

Empezamos construyendo la matriz de adyacencia:

Todos los caminos de longitud 2 entre dos vértices vendrán dados por la matriz C2 y los de longitud 3 por la matriz C3.

¿Cuántos y cuáles son los caminos de longitud 2 que unen las casas b y d?

A la vista de la matriz C2 sabemos que hay exactamente 2 rutas de longitud 2 que son:    

d → c → b       

d → a → b

¿Cuántos y cuáles son los caminos de longitud 3 que unen las casas a y d?

A la vista de la matriz C3 sabemos que hay exactamente 6 caminos de longitud 3 que unen las casas a y d que son los siguientes:

a → b → c → d            a → b → a → d        

a → e → a → d            a → d → e → d      

a → d → a → d            a → d → c → d             

Aplicación de grafos a la psicología

El psicólogo de una empresa está estudiando la relación de dominio o ascendiente de un grupo de trabajo de 5 personas: Aurelia, Berta, Carlos, Daniela, Esteban. Mediante entrevistas personales, consigue establecer quién domina a quien por parejas. Empleando los datos que obtiene, elabora el siguiente grafo dirigido de 5 vértices donde, por ejemplo, A → B significa que Aurelia domina a Berta.

Para ver quien es el lider del grupo se suman las filas de la matriz de adyacencia. Con esto se obtiene a cuantos compañeros domina cada persona. En este caso obtenemos que

Tanto Aurelia como Daniela dominan a 3 personas. Este empate hace que no sea posible decidir quién es el lider del grupo.

La matriz M2, tal como hemos visto en el ejemplo anterior, representa a caminos de longitud 2. En términos del problema que estamos tratando, esto representa los dominios "de segundo orden", es decir, la cantidad de personas que son dominadas por personas que domina cierta persona. Por ejemplo, si Daniela domina a Carlos y Carlos domina a Berta, tiene sentido pensar que Daniela puede ejercer algún tipo de dominio sobre Berta. Sumando como antes, obtenemos cuantos dominios de segundo orden ejerce cada persona.

Finalmente, la matriz M + M2 representa la cantidad de dominios de primer o segundo orden que ejerce cada persona sobre el resto de personas del grupo. Sumando el número de filas de esta matriz, podemos declarar a Daniela como líder del grupo.

izquierda
         arriba
derecha