Grafos y matrices

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.

Grafos y matrices Grafos y matrices

Crea materiales de aprendizaje sobre Grafos y matrices con nuestra app gratuita de aprendizaje!

  • Acceso instantáneo a millones de materiales de aprendizaje
  • Tarjetas de estudio, notas, exámenes de simulacro y más
  • Todo lo que necesitas para sobresalir en tus exámenes
Regístrate gratis
Índice de temas

    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.

    Grafos y matrices, representación de un grafo, StudySmarterFig. 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:

    1. 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).

    2. Si hay una conexión, se pone un \(1\).

    3. 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.

    Grafos y matrices, representación de un grafo dirigido, StudySmarterFig. 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.

    Grafos y matrices, representación de un grafo con aristas, StudySmarter

    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:
      1. 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).

      2. Si hay una conexión, se pone un \(1\).

      3. 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.

    Preguntas frecuentes sobre Grafos y matrices

    ¿Qué es un grafo y cuál sería un ejemplo?

    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.


    Un ejemplo de un grafo es el plano del metro de una cuidad. En este, las estaciones son los vértices del grafo y las vías entre estaciones son las aristas.

    ¿Dónde se aplican los 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.

    ¿Cómo hacer la matriz de un grafo?

    Si quieres crear la matriz de adyacencia de un grafo puedes seguir los siguientes pasos:

    1. Rellenamos, elemento a elemento, empezando por el de la primera fila con la primera columna. Esto significa que entre el vértice A y el vértice A hay alguna conexión (arista).

    2. Si hay una conexión, se pone un 1.

    3. Si no hay ninguna conexión, se pone un 0.

    ¿Cómo se hace una matriz de adyacencia?

    Si quieres crear la matriz de adyacencia de un grafo, puedes seguir los siguientes pasos:

    1. Rellenamos, elemento a elemento, empezando por el de la primera fila con la primera columna. Esto mide si entre el vértice A y el vértice A hay alguna conexión (arista).

    2. Si hay una conexión, se pone un 1.

    3. Si no hay ninguna conexión, se pone un 0.

    Pon a prueba tus conocimientos con tarjetas de opción múltiple

    ¿Qué es un grafo?

    La matriz de adyacencia relaciona:

    La matriz de incidencia relaciona:

    Siguiente
    1
    Acerca de StudySmarter

    StudySmarter es una compañía de tecnología educativa reconocida a nivel mundial, que ofrece una plataforma de aprendizaje integral diseñada para estudiantes de todas las edades y niveles educativos. Nuestra plataforma proporciona apoyo en el aprendizaje para una amplia gama de asignaturas, incluidas las STEM, Ciencias Sociales e Idiomas, y también ayuda a los estudiantes a dominar con éxito diversos exámenes y pruebas en todo el mundo, como GCSE, A Level, SAT, ACT, Abitur y más. Ofrecemos una extensa biblioteca de materiales de aprendizaje, incluidas tarjetas didácticas interactivas, soluciones completas de libros de texto y explicaciones detalladas. La tecnología avanzada y las herramientas que proporcionamos ayudan a los estudiantes a crear sus propios materiales de aprendizaje. El contenido de StudySmarter no solo es verificado por expertos, sino que también se actualiza regularmente para garantizar su precisión y relevancia.

    Aprende más
    Equipo editorial StudySmarter

    Equipo de profesores deGrafos y matrices

    • Tiempo de lectura de 10 minutos
    • Revisado por el equipo editorial de StudySmarter
    Guardar explicación

    Guardar explicación

    Sign-up for free

    Regístrate para poder subrayar y tomar apuntes. Es 100% gratis.

    Únete a más de 22 millones de estudiantes que aprenden con nuestra app StudySmarter.

    La primera app de aprendizaje que realmente tiene todo lo que necesitas para superar tus exámenes en un solo lugar.

    • Tarjetas y cuestionarios
    • Asistente de Estudio con IA
    • Planificador de estudio
    • Exámenes simulados
    • Toma de notas inteligente
    Únete a más de 22 millones de estudiantes que aprenden con nuestra app StudySmarter.