Matriz de adyacencia
Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.
Se trata de una matriz cuadrada de n filas \times n columnas (siendo n el número de vértices del grafo).
Para construir la matriz de adyacencia, cada elemento a_{ij} vale {{1}} cuando haya una arista que una los vértices i y j. En caso contrario el elemento a_{ij} vale 0.
La matriz de adyacencia, por tanto, estará formada por ceros y unos.
Ejemplo : Este video no tiene lucro para esta pagina
Matriz de adyacencia. Matriz cuadrada de orden NxN asociada a un grafo de orden N, donde sus filas y columnas se identifican con los vértices del grafo y en las celdas se indican la cantidad de aristas (o arcos salientes si es un dígrafo) a los nodos asignado a la fila y columnas en cuestión.
Contenido
[ocultar]
1 Definición.
2 Ejemplo.
3 Véase también
4 Fuentes.
Definición.
Sea el grafo G=<V,A> de orden N al mismo se asocia una matriz cuadrada M de NxN tal que:
A cada fila se asocia un nodo de V.
A cada columna se asocia un nodo de V.
La celda Mi,j contiene la cantidad de aristas de A de la forma {i,j} ó (i, j).
Ejemplo.
Dada la relación:
G=<{0, 1, 2, 3, 4, 5, 6, 7, 8}, ((0, 3), (0, 4), (0, 5), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 6), (3, 7), (8, 3), (4, 6), (4, 7), (8, 4), (5, 6), (5, 7), (8, 5))>.
la matriz de adyacencia asociada al grafo sería:
N 0 1 2 3 4 5 6 7 8
0 0 0 0 1 1 1 0 0 0
1 0 0 0 1 1 1 0 0 0
2 0 0 0 1 1 1 0 0 0
3 1 1 1 0 0 0 1 1 1
4 1 1 1 0 0 0 1 1 1
5 1 1 1 0 0 0 1 1 1
6 0 0 0 1 1 1 0 0 0
7 0 0 0 1 1 1 0 0 0
para mayor información sigume en:
CIBERGRAFIA
No hay comentarios:
Publicar un comentario