Calculadora de Matriz de Adyacencia

Calculadora de Matriz de Adyacencia

La Calculadora de Matriz de Adyacencia es una utilidad de teoría de grafos que convierte entre las tres representaciones canónicas de grafos: matriz de adyacencia, lista de aristas y lista de adyacencia, y enriquece el resultado con un análisis estructural: secuencia de grados, densidad del grafo, componentes conexos y potencias de la matriz. Detecta automáticamente si tu entrada describe un grafo dirigido o no dirigido y genera una visualización interactiva en SVG con cada resultado.

¿Qué es una matriz de adyacencia?

Dado un grafo G = (V, E) con n vértices, su matriz de adyacencia es la matriz cuadrada n × n A cuya entrada A[i][j] es 1 si hay una arista desde el vértice i al vértice j, y 0 en caso contrario.

Para un grafo no dirigido, la matriz de adyacencia es siempre simétrica: cada arista {u, v} contribuye tanto a A[u][v] = 1 como a A[v][u] = 1. Para un grafo dirigido (dígrafo), la matriz puede ser asimétrica, reflejando la dirección de cada arco.

Tres representaciones: elige la que mejor se adapte a tu problema

Métricas clave calculadas

Secuencia de grados

Para grafos no dirigidos, el grado de un vértice es el número de aristas que inciden en él (contando los bucles dos veces). Para grafos dirigidos, cada vértice tiene un grado de entrada (arcos entrantes) y un grado de salida (arcos salientes). La lista ordenada de grados es un invariante de grafo clásico utilizado en pruebas de isomorfismo y en el teorema de realizabilidad de Erdős–Gallai.

Densidad del grafo

La densidad mide qué tan "lleno" está un grafo en relación con el número máximo de aristas posibles en n vértices.

Una densidad de 0 significa que no hay aristas, 1 significa que el grafo es completo, y los valores por debajo de 0.1 suelen indicar un grafo disperso donde una lista de adyacencia es más eficiente en espacio que una matriz.

Componentes conexos

Un componente conexo es un subconjunto maximal de vértices tal que cada par está unido por un camino. Para grafos dirigidos, esta calculadora informa los componentes débilmente conexos (ignorando la dirección de las flechas), los mismos subconjuntos que obtendrías al tratar cada arco como una arista no dirigida.

Potencias de la matriz (A², A³ ... )

Un teorema fundamental de la teoría de grafos algebraicos establece que la entrada (i, j) de A^k es igual al número de caminos de longitud exactamente k desde el vértice i al vértice j. En consecuencia:

• A²[i][i] es igual al grado del vértice i (no dirigido), ya que un camino de longitud 2 de i a sí mismo es "ir a un vecino y volver".
• La traza de A³ dividida por 6 cuenta los triángulos en un grafo no dirigido.
• Si Aⁿ⁻¹ tiene alguna entrada igual a cero, te indica si el grafo es conexo.

Formatos de entrada aceptados

1. Lista de aristas

Una arista por línea o separada por comas. Cualquiera de estos separadores funciona: A-B, A B, A,B, A->B, A--B. Usa -> si quieres forzar una interpretación dirigida.

2. Lista de adyacencia

Una línea por vértice, en la forma vértice: vecino1, vecino2, .... El orden no importa; los vértices faltantes se añaden automáticamente desde las listas de vecinos.

3. Matriz de adyacencia

Una fila por línea con valores 0/1 separados por espacios o comas. La matriz debe ser cuadrada. Opcionalmente, proporciona etiquetas personalizadas en el campo Etiquetas de la matriz (de lo contrario se usan A, B, C…).

Cómo usar esta calculadora

1. Elige un formato de entrada usando el selector de pestañas: lista de aristas, lista de adyacencia o matriz de adyacencia.
2. Pega o escribe tu grafo en el área de texto. Para la entrada de matriz, añade etiquetas opcionales en el campo Etiquetas de la matriz.
3. Selecciona el tipo de grafo: déjalo en Detección automática y la calculadora inferirá la direccionalidad a partir de las flechas (->) o la simetría de la matriz. Forzar a Dirigido o No dirigido si deseas anularlo.
4. Haz clic en Convertir y Analizar Grafo. La página de resultados muestra la matriz de adyacencia, una representación SVG interactiva, las otras dos representaciones de texto, estadísticas de grados, componentes conexos y matrices de recuento de caminos A² y A³ cuando el grafo es lo suficientemente pequeño.
5. Pasa el ratón por una fila de la matriz o un nodo del grafo para iluminar la fila/columna correspondiente y las aristas incidentes; una prueba visual instantánea de que cada formato codifica la misma información.

Ejemplo práctico

Considera un grafo no dirigido en los vértices {A, B, C, D} con aristas AB, BC, CA, CD. La matriz de adyacencia es:

Datos clave que la calculadora deriva:

• ¿Simétrico? Sí, confirma que no es dirigido.
• Secuencia de grados: (3, 2, 2, 1); el vértice C es el núcleo.
• Densidad: 2·4 / (4·3) = 0.667; un grafo moderadamente denso.
• ¿Conexo? Sí, un único componente.
• Triángulos: exactamente uno (A–B–C), como confirma tr(A³) = 6.

Aplicaciones comunes

• Análisis de redes sociales: grafos de amistad / seguidores, centralidad.
• Grafos web y de citas: PageRank y HITS trabajan directamente sobre A y A^T.
• Enrutamiento y redes: ruta más corta, corte mínimo, flujo máximo.
• Química: grafos moleculares con átomos como vértices y enlaces como aristas.
• Programación y resolución de dependencias: grafos acíclicos dirigidos (DAGs) en sistemas de construcción.
• Cadenas de Markov: las matrices estocásticas de filas derivadas de grafos codifican probabilidades de transición.

Preguntas frecuentes

¿Qué es una matriz de adyacencia?

Una matriz de adyacencia es una matriz cuadrada n × n utilizada para representar un grafo finito. Cada celda A[i][j] es 1 si hay una arista desde el vértice i al vértice j, y 0 en caso contrario. Para grafos no dirigidos, la matriz es simétrica, por lo que A[i][j] = A[j][i]. La matriz facilita comprobar si dos vértices están conectados en tiempo constante, y las potencias de la matriz codifican el número de caminos entre los vértices.

¿Cómo saber si un grafo es dirigido a partir de su matriz de adyacencia?

Si la matriz de adyacencia es simétrica, es decir, A[i][j] es igual a A[j][i] para cada par de índices, el grafo es no dirigido. Si hay al menos un par donde A[i][j] difiere de A[j][i], el grafo es dirigido. Esta calculadora realiza esa comprobación de simetría automáticamente cuando eliges la opción de Detección automática.

¿Qué representa la k-ésima potencia de una matriz de adyacencia?

La entrada (i, j) de A^k cuenta el número de caminos de longitud exacta k desde el vértice i al vértice j. Por ejemplo, A²[i][j] es el número de caminos de 2 pasos, lo que equivale al número de vecinos comunes entre i y j en grafos no dirigidos. Esta propiedad se utiliza en algoritmos para el conteo de triángulos, alcanzabilidad y cálculos de estilo PageRank.

¿Qué es la densidad de un grafo?

La densidad del grafo es la relación entre el número de aristas presentes y el número máximo posible de aristas. Para un grafo simple no dirigido con n vértices, densidad = 2m / (n(n-1)). Para un grafo dirigido, densidad = m / (n(n-1)). Una densidad cercana a 0 significa un grafo disperso; una densidad de 1 significa un grafo completo.

¿En qué se diferencia una matriz de adyacencia de una lista de adyacencia?

Una matriz de adyacencia almacena la conectividad para cada par de vértices utilizando n² bits, lo que hace que la búsqueda de vecinos sea O(1) pero el uso de memoria sea O(n²). Una lista de adyacencia almacena solo los vecinos reales de cada vértice, lo que da una memoria de O(n + m), que es mucho menor para grafos dispersos, pero la búsqueda de vecinos requiere un escaneo lineal. Las matrices son mejores para grafos densos y operaciones de álgebra matricial; las listas son mejores para grafos dispersos y algoritmos de recorrido como BFS/DFS.

¿Puede esta herramienta manejar grafos ponderados?

La calculadora actual se centra en matrices de adyacencia no ponderadas con entradas 0/1. Si pegas una matriz con pesos numéricos distintos de cero, cada celda distinta de cero se trata como un 1 para el análisis estructural. Para cálculos de grafos ponderados, como la ruta más corta, considera una herramienta dedicada a grafos ponderados.

Lecturas adicionales

• Matriz de adyacencia — Wikipedia
• Secuencia de grados — Wikipedia (Inglés)
• Densidad de grafos — Wikipedia (Inglés)
• Componentes conexos — Wikipedia