En este artículo, discutiremos la matriz de adyacencia junto con su representación.
jdbc jdbc
Definición de matriz de adyacencia
En teoría de grafos, una matriz de adyacencia es una forma densa de describir la estructura de un grafo finito. Es la matriz 2D que se utiliza para mapear la asociación entre los nodos del gráfico.
Si una gráfica tiene norte número de vértices, entonces la matriz de adyacencia de ese gráfico es n x n , y cada entrada de la matriz representa el número de aristas de un vértice a otro.
Una matriz de adyacencia también se llama matriz de conexión . A veces también se le llama matriz de vértice .
Representación de matriz de adyacencia
Si un gráfico no dirigido G consta de n vértices, entonces la matriz de adyacencia de un gráfico es n x n matriz A = [aij] y está definida por -
ayo= 1 {si existe un camino desde Via Vj}
ayo= 0 {de lo contrario}
Veamos algunos de los puntos importantes con respecto a la matriz de adyacencia.
- Si existe una arista entre el vértice Viy Vj, donde i es una fila y j es una columna, entonces el valor de ayo= 1.
- Si no hay arista entre el vértice Viy Vj, entonces el valor de ayo= 0.
- Si no hay bucles propios en el gráfico simple, entonces la matriz de vértices (o matriz de adyacencia) debe tener ceros en la diagonal.
- Una matriz de adyacencia es simétrica para un gráfico no dirigido. Especifica que el valor en ithfila y jthla columna es igual al valor en jthfila ith
- Si la matriz de adyacencia se multiplica por sí misma y si hay un valor distinto de cero en la ithfila y jthcolumna, luego está la ruta desde Via Vjcon una longitud equivalente a 2. El valor distinto de cero en la matriz de adyacencia representa que el número de caminos distintos está presente.
Nota: En una matriz de adyacencia, 0 representa que no existe una asociación entre dos nodos, mientras que 1 representa que existe una asociación entre dos nodos.
¿Cómo crear una matriz de adyacencia?
Supongamos que hay un gráfico gramo con norte número de vértices, entonces la matriz de vértices (o matriz de adyacencia) viene dada por -
Una = una11a12. . . . . a1na21a22. . . . . a2n. . . . . . . . . an1an2. . . . . ann
donde el unyoes igual al número de aristas desde el vértice i al j. Como se mencionó anteriormente, la matriz de Adyacencia es simétrica para un gráfico no dirigido, por lo que para un gráfico no dirigido, ayo= unji.
Cuando los gráficos son simples y no hay pesos en los bordes o bordes múltiples, entonces las entradas de la matriz de adyacencia serán 0 y 1. Si no hay bucles automáticos, entonces las entradas diagonales de la matriz de adyacencia serán 0.
java mientras condición
Ahora, veamos la matriz de adyacencia para un gráfico no dirigido y para gráficos dirigidos.
Matriz de adyacencia para un gráfico no dirigido
En un gráfico no dirigido, los bordes no están asociados con las direcciones que los contienen. En un gráfico no dirigido, si existe una arista entre el vértice A y el vértice B, entonces los vértices se pueden transferir de A a B, así como de B a A.
Consideremos el siguiente gráfico no dirigido e intentemos construir su matriz de adyacencia.
En el gráfico, podemos ver que no hay un bucle automático, por lo que las entradas diagonales de la matriz adyacente serán 0. La matriz de adyacencia del gráfico anterior será:
Matriz de adyacencia para un gráfico dirigido
En un gráfico dirigido, las aristas forman un par ordenado. Los bordes representan una ruta específica desde algún vértice A a otro vértice B. El nodo A se llama nodo inicial, mientras que el nodo B se llama nodo terminal.
Consideremos el siguiente gráfico dirigido e intentemos construir su matriz de adyacencia.
arquitectura de la colmena
En el gráfico anterior, podemos ver que no hay un bucle automático, por lo que las entradas diagonales de la matriz adyacente serán 0. La matriz de adyacencia del gráfico anterior será:
Propiedades de la matriz de adyacencia
Algunas de las propiedades de la matriz de adyacencia se enumeran a continuación:
- Una matriz de adyacencia es una matriz que contiene filas y columnas que se utilizan para representar un gráfico etiquetado simple con los números 0 y 1 en la posición de (VI, ENj), según la condición de si los dos Vi y Vjson adyacentes.
- Para un gráfico dirigido, si existe una arista entre el vértice i o Vial vértice j o Vj, entonces el valor de A[Vi][ENj] = 1, de lo contrario el valor será 0.
- Para un gráfico no dirigido, si existe una arista entre el vértice i o Vial vértice j o Vj, entonces el valor de A[Vi][ENj] = 1 y A[Vj][ENi] = 1, de lo contrario el valor será 0.
Veamos algunas cuestiones de la matriz de adyacencia. Las siguientes preguntas se refieren a los gráficos dirigidos y no dirigidos ponderados.
NOTA: Se dice que un gráfico es ponderado si a cada borde se le asigna un número positivo, que se denomina peso del borde.
Pregunta 1 - ¿Cuál será la matriz de adyacencia para el siguiente gráfico ponderado no dirigido?
Solución - En la pregunta dada, no hay bucle automático, por lo que está claro que las entradas diagonales de la matriz adyacente para el gráfico anterior serán 0. El gráfico anterior es un gráfico no dirigido ponderado. Los pesos en los bordes del gráfico se representarán como las entradas de la matriz de adyacencia.
espacio de línea numeroso
La matriz de adyacencia del gráfico anterior será:
Pregunta 2 - ¿Cuál será la matriz de adyacencia para el siguiente gráfico ponderado dirigido?
Solución - En la pregunta dada, no hay bucle automático, por lo que está claro que las entradas diagonales de la matriz adyacente para el gráfico anterior serán 0. El gráfico anterior es un gráfico dirigido ponderado. Los pesos en los bordes del gráfico se representarán como las entradas de la matriz de adyacencia.
La matriz de adyacencia del gráfico anterior será:
Espero que este artículo le resulte beneficioso para comprender la matriz de adyacencia. Aquí, hemos discutido la matriz de adyacencia junto con su creación y propiedades. También hemos discutido la formación de matrices de adyacencia en gráficos dirigidos o no dirigidos, estén ponderados o no.