Iniciar sesión Empieza a estudiar
La app de estudio todo en uno
4.8 • +11 mil reviews
Más de 3 millones de descargas
Free
|
|

Grafos y matrices

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.

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

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.

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.

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.

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.

Cuestionario final de Grafos y matrices

Pregunta

¿Qué es un grafo?

Mostrar respuesta

Answer

Un grafo es una representación de objetos, llamados vértices, unidos por aristas para expresar una relación binaria.

Show question

Pregunta

La matriz de adyacencia relaciona:

Mostrar respuesta

Answer

Vértices con vértices.

Show question

Pregunta

La matriz de incidencia relaciona:

Mostrar respuesta

Answer

Vértices con aristas.

Show question

Pregunta

¿Cuántas filas tiene una matriz de incidencia?

Mostrar respuesta

Answer

Tantas como número de vértices.

Show question

Pregunta

¿Cuántas filas tiene una matriz de adyacencia?

Mostrar respuesta

Answer

Tantas como número de vértices.

Show question

Pregunta

¿Cuántas columnas tiene una matriz de incidencia?

Mostrar respuesta

Answer

Tantas como número de aristas.

Show question

Pregunta

¿Cuántas columnas tiene una matriz de adyacencia?

Mostrar respuesta

Answer

Tantas como vértices.

Show question

Pregunta

Un grafo dirigido tiene la misma matriz de adyacencia que el mismo grafo pero no dirigido. ¿Verdadero o falso?

Mostrar respuesta

Answer

Falso.

Show question

Pregunta

Un grafo dirigido tiene la misma matriz de incidencia que el mismo grado pero no dirigido. ¿Verdadero o falso?

Mostrar respuesta

Answer

Verdadero.

Show question

Pregunta

¿Cuál de las siguientes opciones no es un tipo de grafo?

Mostrar respuesta

Answer

Grafos compuestos.

Show question

Pregunta

¿Cuáles de las siguientes situaciones se puede representar mediante un grafo?

Mostrar respuesta

Answer

Las conexiones entre usuarios en una red social.

Show question

Pregunta

¿La longitud de una arista representa una magnitud entre los dos vértices que une?

Mostrar respuesta

Answer

Sí, siempre hay que representarlas en función de la magnitud que relaciona los dos vértices.

Show question

60%

de los usuarios no aprueban el cuestionario de Grafos y matrices... ¿Lo conseguirás tú?

Empezar cuestionario

Scopri i migliori contenuti per le tue materie

No hay necesidad de copiar si tienes todo lo necesario para triunfar. Todo en una sola app.

Plan de estudios

Siempre preparado y a tiempo con planes de estudio individualizados.

Cuestionarios

Pon a prueba tus conocimientos con cuestionarios entretenidos.

Flashcards

Crea y encuentra fichas de repaso en tiempo récord.

Apuntes

Crea apuntes organizados más rápido que nunca.

Sets de estudio

Todos tus materiales de estudio en un solo lugar.

Documentos

Sube todos los documentos que quieras y guárdalos online.

Análisis de estudio

Identifica cuáles son tus puntos fuertes y débiles a la hora de estudiar.

Objetivos semanales

Fíjate objetivos de estudio y gana puntos al alcanzarlos.

Recordatorios

Deja de procrastinar con nuestros recordatorios de estudio.

Premios

Gana puntos, desbloquea insignias y sube de nivel mientras estudias.

Magic Marker

Cree tarjetas didácticas o flashcards de forma automática.

Formato inteligente

Crea apuntes y resúmenes organizados con nuestras plantillas.

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