Teoría de grafos: Matriz de adyacencia

el
Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.Se trata de una matriz cuadrada de n  filas x n columnas (siendo n el número de vértices del grafo). 
Para construir la matriz de adyacencia, cada elemento aij vale {{1}} cuando haya una arista que una los vértices i y j. En caso contrario el elemento vale 0.

 La matriz de adyacencia, por tanto, estará formada por ceros y unos.
Ejemplo 1
Vamos a construir la matriz de adyacencia del siguiente grafo:

Como tiene 5 vértices, será una matriz de 5 filas x 5 columnas
\left( \begin{array}{ccccc} X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \end{array} \right)
Completamos la primera fila (la del 1). El 1 sólo está conectado al 2 y al 4, por tanto ponemos un 1 en las columnas 2 y 4 y un 0 en las demás:
\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \end{array} \right)

Procedemos de igual forma con el resto de filas y ya tenemos la matriz de adyacencia:
\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 1 \\0 & 1 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 0 \\0 & 1 & 0 & 0 & 0 \end{array} \right)
En la siguiente imagen podemos ver las conexiones entre el 1 y el 4

Comentarios

Publicar un comentario