< Atrás | Siguiente | Contenido >
Matriz de Adyacencia: Vértice Vértice
La familia de grafos argumenta que una de las mejores formas de representarlos en una matriz es contando el número de aristas entre dos vértices adyacentes.
Se dice que dos vértices son adyacentes o vecinos si soportan al menos una arista común.
Comencemos con el ejemplo
El gráfico de abajo tiene tres vértices. Por lo tanto, hacemos una matriz de adyacencia de tamaño 3 por 3. Luego ponemos el nombre de los vértices en el lado de la matriz. Mira la imagen y empezamos con una matriz vacía. Solo están los nombres de los vértices
matriz, nos fijamos en el nombre del vértice en fila y columna. Si esos vértices están conectados por una arista o más, contamos el número de aristas y ponemos este número como elemento de matriz.
Vértice 
y vértice 
tiene una arista común, decimos que Vértice 
y vértice 
es adyacente (vecina). Ingresamos el número de aristas en la celda de matriz que corresponden a vértice 
y vértice 
.
Vértice 
y 
es adyacente por una arista. Por lo tanto, ingresamos el número de aristas en la celda de la matriz que corresponden al Vértice 
y 
.
Del mismo modo, vertex 
y 
está conectada por una arista. Por lo tanto, ingresamos el número de aristas en la celda de matriz que corresponden al vértice 
y 
No hay otra arista en el grafo, por lo que colocamos el resto de celdas sin rellenar en la matriz como cero
un gráfico de esta manera se llama matriz de adyacencia .
El tamaño de la matriz de adyacencia es igual al número de vértices en el grafo. Es una matriz cuadrada (es decir, el número de filas es igual al número de columnas).
La matriz de adyacencia de un gráfico es simétrica porque no tiene dirección. Se pueden llamar dos vértices que comparten la misma arista del primero al segundo, o del segundo al primero. Por ejemplo, Vertex 
y vertex 
tiene una arista común, luego element (a, b) = 1 y element (b, a) = 1.
Probemos otro ejemplo:
¿Puede hacer la matriz de adyacencia de este gráfico? Pruébelo primero antes de mirar la respuesta a continuación.
El gráfico tiene 3 vértices, por lo que hacemos una matriz de tamaño 3 por 3. Ponemos el nombre de los vértices en el lado de la matriz.
Ahora mira el vértice 
y vértice 
. ¿Cuántas aristas soportan los dos vértices? Una. Luego ponemos este valor en la matriz
Mira el vértice 
y vértice 
. ¿Cuántas aristas soportan estos vértices? Ninguno. Luego, ponemos el valor cero en la celda correspondiente en la matriz
A continuación, mira el vértice 
y vértice 
. ¿Cuántos bordes soportan estos vértices? Dos. Luego ingresamos la matriz en
Dado que no hay otra arista en el grafo, podemos llenar la celda vacía con ceros. Por lo tanto, tenemos la respuesta
Algunos de ustedes pueden preguntar acerca de la parte diagonal de la matriz, ¿estas células son siempre cero? No, si encuentra que el gráfico tiene algún bucle en algunos vértices, puede llenar el elemento diagonal de la matriz de adyacencia con el número de bucle.
Si un gráfico tiene algún vértice que no está conectado a ningún otro vértice, la matriz de adyacencia correspondiente a ese vértice único es cero.
Por favor, practique un poco para representar el gráfico de abajo en la matriz de adyacencia.
(Consulte la respuesta en la página anterior)
Dada la matriz de adyacencia, ¿puede retirar el gráfico?
Compruebe el ejemplo de aplicación de la teoría de grafos en el tutorial de Q-Learning
< Atrás | Siguiente/Contenido>