Matriz de adyacencia de un grafo
Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.
Se trata de una matriz cuadrada de filas columnas (siendo el número de vértices del grafo).
Para construir la matriz de adyacencia, cada elemento vale 1 cuando haya una arista que una los vértices y . En caso contrario el elemento vale 0.
La matriz de adyacencia, por tanto, estará formada por ceros y unos.
Ejemplo 1
Vamos a construir la matriz de adyacencia del siguiente grafo:
– Como tiene 5 vértices, será una matriz de 5 filas x 5 columnas
Completamos la primera fila (la del ). El sólo está conectado al y al , por tanto ponemos un en las columnas y y un 0 en las demás:
Procedemos de igual forma con el resto de filas y ya tenemos la matriz de adyacencia:
En la siguiente imagen podemos ver las conexiones entre el 1 y el 4
19 - Grafos
- Secciones
-
MATEMÁTICAS
- 01 - Números Naturales
- 02 - Números Enteros
- 03 - Fracciones
- 04 - Proporcionalidad y Porcentajes
- 05 - Sistemas de medida
- 06 - Polinomios
- 07 - Ecuaciones
- 08 - Sistemas de ecuaciones
- 10 - Sucesiones
- 11 - Geometría en el plano
- 12 - Estadística
- 13 - Probabilidad
- 14 - V.A. Unidimensionales
- 15 - Funciones, Límites y Continuidad
- 16 - Derivadas
- 17 - Integrales
- 18 - Matrices y Determinantes
- 19 - Grafos
- 20 - Geometría en el espacio
- 21 - Trigonometría
- 22 - Logaritmos
- 23 - Matemática Financiera
- 25 - Inferencia Estadística
- LaTeX