Una red social es un canal por el cual muchas personas están interconectadas, hablan, comparten contenido, interactúan, ven y hacen publicaciones, etc. Sin embargo, no todas las personas que forman parte de la red social están conectadas entre sí: algunos usuarios solo reciben contenido de unos pocos cientos de usuarios, mientras que otras personas comparten contenido con hasta millones de otros usuarios. Estas conexiones entre personas las podemos representar mediante un esquema en el que una persona es un punto y hay líneas que unen dos puntos, representando la conexión entre esas dos personas.
Este es solo un ejemplo; pero, a este tipo de esquema es lo que denominamos grafo.
Grafos
Un grafo es una representación gráfica de un conjunto de objetos llamados vértices o nodos, unidos por enlaces que llamamos aristas, con el fin de expresar una relación binaria entre los elementos del conjunto.
Con esta definición y con el ejemplo anterior, podemos decir que la Fig. 1 es la representación de un grafo en el que cada punto representa un vértice y cada una de las aristas representa la conexión entre dos vértices.
Fig. 1. Representación de un grafo.
Matriz de adyacencia
El grafo es, entonces, una representación gráfica de la información. Pero, con una imagen no podemos hacer cálculos para obtener información precisa, ni calcular otros datos. Para poder hacer esto, se crea la llamada matriz de adyacencia.
La matriz de adyacencia es la matriz en la que los vértices se ordenan en las filas y columnas y cada elemento \(a_{ij}\) representa el número de aristas que unen el vértice de la fila \(i\) con el vértice de la columna \(j\).
Esta matriz es una representación numérica del grafo con la cual podemos hacer operaciones y obtener más datos.
Si queremos obtener la matriz de adyacencia del grafo anterior, ordenamos los vértices en las filas y las columnas de una matriz que será de dimensión \(n\times n\), siendo \(n\) el número de vértices en el grafo.
\[\begin{array}\, \space\space\space\space\space\space\space\space\space\space&A&B&C&D&E&F\end{array}\]
\[M=\begin{array}\,A\\B\\C\\D\\E\\F\end{array}\begin{pmatrix}\,&\space\space\space&\space\space&\space\space&\space\space&\space\space\space\space\space\space\space\\&&&&&\\&&&&&\\&&&&&\\&&&&&\\&&&&&\end{pmatrix}\]
A continuación, rellenamos la matriz siguiendo los siguientes pasos:
La completamos, elemento a elemento, empezando por el de la primera fila con la primera columna; es decir, el elemento \(a_{11}\). Esto es, si entre el vértice \(A\) y el vértice \(A\) hay alguna conexión (arista).
Si hay una conexión, se pone un \(1\).
Si no hay ninguna conexión, se pone un \(0\). En este caso, no hay ninguna conexión que lleve del vértice A de vuelta al mismo vértice, por lo que en el elemento \(a_{11}\) de la matriz pondríamos un \(0\).
Por ejemplo, en el siguiente elemento \(a_{12}\) hay que ver si hay alguna arista que conecte el vértice \(A\) con el vértice \(B\). En este caso sí hay una arista, por lo que este elemento será un \(1\).
De este modo, rellenamos la matriz completa obteniendo:
\[\begin{array}\, \space\space\space\space\space\space\space\space\space&A&B&C&D&E&F\end{array}\]
\[M=\begin{array}\,A\\B\\C\\D\\E\\F\end{array}\begin{pmatrix}\,0\space&1\space&1\space&1\space&0\space&0\space\\1&0&1&1&1&0\\1&1&0&1&0&1\\1&1&1&0&1&0\\0&1&0&1&0&1\\0&0&1&0&1&0\end{pmatrix}\]
Esta sería la matriz de adyacencia del grafo de la Fig. 1.
Matriz de adyacencia de un grafo dirigido
También podemos tener un grafo en el que las artistas estén dirigidas; es decir, que tengan una flecha que indica el sentido de la conexión, tal como se observa en la Fig. 2. A este tipo de grafo se le denomina gafo dirigido.
Fig. 2. Grafo dirigido.
La manera de obtener la matriz de adyacencia de este grafo es similar a la del primer caso. La única diferencia es que ahora la arista solo cuenta cuando va de un vértice a otro en el sentido de la flecha, no en ambos sentidos. Por tanto, de \(A\) a \(D\) habría una conexión o arista y el elemento de matriz sería un \(1\). Sin embargo, de \(D\) a \(A\) no hay ninguna conexión o arista y el elemento de matriz sería \(0\). De este modo, podemos rellenar la matriz de adyacencia completa de este grafo dirigido:
\[\begin{array}\,\space\space\space\space\space\space\space\space\space&A&B&C&D&E&F\end{array}\]
\[M=\begin{array}\,A\\B\\C\\D\\E\\F\end{array}\begin{pmatrix}\,0\space&1\space&1\space&1\space&0\space&0\space\\1&0&0&1&0&0\\0&0&0&0&0&1\\0&0&1&0&1&1\\0&1&0&1&0&0\\0&0&0&0&0&0\end{pmatrix}\]
Esta sería la matriz de adyacencia del grafo de la Fig. 2. Si denominamos a esta matriz como \(M\), esta da cuenta de los caminos que hay para llegar a un vértice desde otro.
Pero, ahora vamos a calcular \(M^2\):
\[M^2=\begin{pmatrix}\,1&0&1&1&1&2\\0&1&2&1&1&1\\0&0&0&0&0&0\\0&1&0&1&0&1\\1&0&1&1&1&1\\0&0&0&0&0&0\end{pmatrix}\]
Si te fijas bien, la interpretación de esta matriz es el número de caminos que llegan del vértice \(i\) al vértice \(j\), haciendo una escala.
Por ejemplo, hay un solo camino para ir de \(A\) a \(A\) haciendo una escala, y este es ir de \(A\) a \(B\) y luego de \(B\) a \(A\).
Si un elemento es un \(2\), quiere decir que existen dos caminos posibles para ir de un vértice a otro, haciendo una escala.
Por último, si sumásemos la matriz \(M\) a \(M^2\), tendríamos el número total de caminos para ir de un vértice a otro, haciendo una escala o yendo directamente.
Como ves, esto tiene muchas aplicaciones en diversos campos científicos.
Matriz de incidencia de un grafo
La matriz de incidencia de un grafo es similar a la matriz de adyacencia, en el sentido en que también muestra las relaciones entre vértices; pero, en este caso, se tienen en cuenta las aristas. Como ejemplo, vamos a usar el grafo de la Fig. 1. Para ello, primero nombramos las aristas como en la Fig. 3.
Fig. 3. Representación de un grafo con vértices y aristas etiquetados.
Para formar esta matriz, en las filas estarán los vértices y en las columnas las aristas. El elemento de matriz será un \(1\), cuando el vértice que corresponde a la fila está conectado a la arista que corresponde a la columna.
Ahora, formamos la matriz de filas y columnas, tal como hemos explicado:
\[I=\begin{pmatrix}\,1&1&1&0&0&0&0&0&0&0\\0&1&0&1&0&1&1&0&0&0\\1&0&0&0&1&0&0&1&0&0\\0&0&1&0&1&1&0&0&0&1\\0&0&0&0&0&0&1&0&1&1\\0&0&0&0&0&0&0&1&1&0\end{pmatrix}\]
Esta sería la matriz de incidencia del grafo representado en la Fig. 3.
Tipos de grafos
Los grafos se pueden dividir en dos grandes grupos:
Grafos no dirigidos.
Grafos dirigidos.
Estos dos tipos de grafos ya los hemos visto en los ejemplos anteriores. Así que ya entiendes en qué se parecen y en qué se diferencian cada uno. Además, en función de las características del grafo, también hay otras clasificaciones:
Grafo simple: es un grafo en el que siempre se da que una única arista une dos vértices.
Multigrafo: al contrario que un grafo simple, en los multigrafos varias aristas pueden unir los mismos dos vértices.
Grafo conexo.
Grafo completo.
Grafo bipartito.
Etc.
Como puedes ver, hay muchos tipos de grafos según sus características.
Aplicaciones de grafos
Los grafos son objetos que se pueden aplicar a muchas ramas científicas, como la sociometría, la antropología, la comunicación, la geografía, las redes sociales, entre muchas otras.
Por ejemplo, los grafos son un recurso que se utiliza para crear las líneas de transporte público, como autobuses y trenes. En los planos, cada estación se trata como un vértice y cada vía entre estaciones es una arista. Además, cada arista puede recibir una ponderación o peso; es decir, un número que denota una cantidad, como puede ser la distancia.
Esto lo utilizan las aplicaciones de mapas para crear rutas entre dos estaciones, contando con el número de estaciones (vértices) y la distancia entre las mismas (aristas ponderadas). Así crean la mejor ruta, adaptada a las necesidades del usuario (menor tiempo, menor número de estaciones, menor número de transbordos, etc.).
Grafos y matrices - Puntos clave
- Un grafo es una representación gráfica de un conjunto de objetos llamados vértices, unidos por enlaces que llamamos aristas, con el fin de expresar una relación binaria entre los elementos del conjunto.
- La matriz de adyacencia es la matriz en la que los vértices se ordenan en las filas y columnas y cada elemento \(a_{ij}\) representa el número de aristas que unen el vértice de la fila \(i\) con el vértice de la columna \(j\).
- Para crear la matriz de adyacencia podemos seguir los siguientes pasos:
Rellenamos, elemento a elemento, empezando por el de la primera fila con la primera columna. Esto significa si entre el vértice \(A\) y el vértice \(A\) hay alguna conexión (arista).
Si hay una conexión, se pone un \(1\).
Si no hay ninguna conexión, se pone un \(0\).
La matriz de incidencia relaciona los vértices con las aristas.
Hay muchos tipos de grafos, en función de sus características. Por ejemplo: grafos no dirigidos, grafos dirigidos, grafos simples, multigrafos, grafos conexos, etc.
Los grafos son objetos que se pueden aplicar a muchas ramas científicas, como la sociometría, la antropología, la comunicación, la geografía, las redes sociales, entre muchas otras.
Résumenes 
Exámenes 
Magazine 
Formacion Profesional 
