Diferencia entre revisiones de «Matriz de adyacencia»
(Etiqueta: no tiene enlaces internos) |
m (Texto reemplazado: «<div align="justify">» por «») |
||
(No se muestran 5 ediciones intermedias de 5 usuarios) | |||
Línea 1: | Línea 1: | ||
− | + | {{Definición|Nombre=Matriz de adyacencia|imagen=7027a0eda733d90e8088881aa9e7a781.png|concepto=Matriz cuadrada de orden ''NxN'' asociada a un grafo de orden N en cuyas celdas se indican la cantidad de aristas a los nodos asignado a la fila y columnas en cuestión.}} | |
− | {{Definición|Nombre=Matriz de adyacencia|imagen=|concepto=Matriz cuadrada de orden ''NxN'' asociada a un grafo de orden N en cuyas celdas se indican la cantidad de aristas a los nodos asignado a la fila y columnas en cuestión.}} | + | |
− | + | '''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 [[nodo]]s asignado a la fila y columnas en cuestión. | |
− | '''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 | ||
== Definición. == | == Definición. == | ||
Línea 12: | Línea 11: | ||
== Ejemplo. == | == 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))>''. | * ''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))>''. | ||
Línea 33: | Línea 28: | ||
! 8 | ! 8 | ||
|- | |- | ||
− | |0||0||0||0||1||1||1||0||0||0 | + | |'''0'''||0||0||0||1||1||1||0||0||0 |
|- | |- | ||
− | |1||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 | + | |'''2'''||0||0||0||1||1||1||0||0||0 |
|- | |- | ||
− | |3||1||1||1||0||0||0||1||1||1 | + | |'''3'''||1||1||1||0||0||0||1||1||1 |
|- | |- | ||
− | |4||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 | + | |'''5'''||1||1||1||0||0||0||1||1||1 |
|- | |- | ||
− | |6||0||0||0||1||1||1||0||0||0 | + | |'''6'''||0||0||0||1||1||1||0||0||0 |
|- | |- | ||
− | |7||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 | + | |'''8'''||0||0||0||1||1||1||0||0||0 |
|} | |} | ||
+ | |||
+ | == Véase también == | ||
+ | |||
+ | * [[Grafo]] | ||
+ | * [[Matriz]] | ||
+ | * [[Matriz cuadrada]] | ||
+ | |||
== Fuentes. == | == Fuentes. == | ||
− | + | * K. Ribnikov. Análisis Combinatorio. Editorial Mir Moscú. 1988. | |
− | + | [[Category:Álgebra]] | |
− | |||
− | [[Category: |
última versión al 19:29 28 ago 2019
|
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.