sábado, 13 de agosto de 2016

Matriz de adyacencia para un grafo



"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque para nuestro caso será una de las formas de representar un grafo.

¿Por que matriz cuadrada? (si fuera profesor lo preguntaría para pescar a más de un distraído), la razón es que tanto las filas como las columnas representan cada uno de los nodos del grafo, si el grafo es de n nodos, la matriz correspondiente sería de n * n, es decir matriz cuadrada, fácil.

Continuemos analizando el paso de grafo a una matriz.


Como ya sabemos al tener 6 nodos nuestro grafo, nuestra matriz tendrá unas dimensiones de 6 * 6, es decir 6 filas y seis columnas.

Si nos fijamos en lo que consideraremos nuestro primer nodo, el nodo uno solo esta conectado con el nodo 2 y 5; en la fila 1 que representa el nodo 1 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 2 y 5.

Si nos fijamos en lo que consideraremos nuestro segundo nodo, el nodo dos esta conectado con el nodo 1, 3 y 5; en la fila 2 que representa el nodo 2 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 1, 3 y 5.

Análogamente hacemos de igual forma con los demás nodos hasta terminar el grafo.

Les dejo algunos ejemplo y un ejecutable en Java de mi autoría para que se diviertan.

Clic aquí para descargar ejecutable.



1 comentario:

Entrada destacada

Matriz de adyacencia para un grafo

"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque pa...