Matriz de adyacencia
| ||||||
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.
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 |
| 8 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Véase también
Fuentes.
- K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988.
This article is issued from
Ecured.
The text is licensed under Creative
Commons - Attribution - Sharealike.
Additional terms may apply for the media files.