Grafos

  • Computer Science

    Definición

    Un grafo es una estructura de datos que representa relaciones entre objetos. Está compuesto por:

  • Vértices (nodos): representan los objetos o entidades.
  • Aristas (edges): representan las relaciones entre los vértices.
  • Pueden ser dirigidos (aristas con dirección) o no dirigidos.
  • Pueden ser ponderados (con un valor asociado a la arista) o no ponderados.

Tipos de grafos

  • Grafos simples: sin bucles ni aristas múltiples.
  • Grafos completos: cada par de nodos está conectado.
  • Grafos bipartitos: nodos divididos en dos conjuntos, aristas solo entre conjuntos.
  • Grafos cíclicos y acíclicos: dependiendo de la existencia de ciclos.
  • Grafos conexos y desconexos: si todos los nodos están conectados.

Representación de grafos

  • Listas de adyacencia
    • Cada nodo mantiene una lista de sus vecinos.
    • Eficiente en grafos dispersos.
    • Ejemplo en Python:

Código: Lista de adyacencia

graph = {
	'A': ['B', 'C'],
	'B': ['A', 'D', 'E'],
	'C': ['A', 'F'],
	'D': ['B'],
	'E': ['B', 'F'],
	'F': ['C', 'E']
}

`

  • Matriz de adyacencia

    • Matriz cuadrada de tamaño n x n.
    • Posición (i, j) indica si existe arista entre nodo i y nodo j.
    • Eficiente en grafos densos.

Código: Matriz de adyacencia

graph = [
	[0, 1, 1, 0, 0, 0],
	[1, 0, 0, 1, 1, 0],
	[1, 0, 0, 0, 0, 1],
	[0, 1, 0, 0, 0, 0],
	[0, 1, 0, 0, 0, 1],
	[0, 0, 1, 0, 1, 0]
]

Costes y complejidad

  • Basado en número de vértices (n) y aristas (m).
  • Listas de adyacencia: O(n + m) para recorrer todos los nodos y aristas.
  • Matriz de adyacencia: O(n²) para recorrido completo.
  • Elección depende de densidad del grafo.

Algoritmos fundamentales en grafos

  • Búsqueda
    • BFS (Breadth-First Search): recorre niveles, útil para caminos mínimos en grafos no ponderados.
    • DFS (Depth-First Search): recorre en profundidad, útil para detección de ciclos.
  • Caminos y distancias
    • Dijkstra: caminos mínimos en grafos ponderados sin aristas negativas.
    • Bellman-Ford: caminos mínimos con aristas negativas.
    • Floyd-Warshall: caminos mínimos entre todos los pares de nodos.
  • Árbol de expansión mínima
    • Prim y Kruskal: encontrar subgrafo conexo con mínima suma de pesos.
  • Detección de ciclos y conectividad
    • DFS o Union-Find para grafos no dirigidos.
  • Algoritmos especializados
    • Topological Sorting: grafos acíclicos dirigidos.
    • Matching en grafos bipartitos.

Estructuras relacionadas

  • Arreglos y listas enlazadas: base para representar nodos y listas de adyacencia.
  • Tablas hash: para búsqueda rápida de nodos.
  • Pilas y colas: usadas en DFS y BFS.
  • Árboles: casos particulares de grafos acíclicos conectados.

Problemas y desafíos comunes

  • Transformar arrays en representaciones de grafos.
  • Representación de bits y manipulación.
  • Contar bits activos (1s) y encontrar combinaciones específicas.
  • Encontrar el siguiente número mayor con el mismo número de bits activos.
  • Compresión y optimización de datos en estructuras de grafos.

Recursos adicionales

Grafos - Conceptos y Temas Avanzados

Representación avanzada y memoria

  • Grafos dinámicos
    • Estructura que permite agregar/eliminar nodos y aristas en tiempo eficiente.
    • Uso de diccionarios y listas enlazadas para manejar grandes grafos.
  • Grafos dispersos con listas comprimidas
    • Uso de arrays de adyacencia compactos para reducir memoria.
    • Representación CSR (Compressed Sparse Row) en grafos grandes.
  • Grafos implícitos
    • Nodos no almacenados explícitamente.
    • Cada nodo generado a partir de reglas o función.
    • Ejemplo: estados en BFS para puzzles o problemas combinatorios.

Propiedades y métricas avanzadas

  • Centralidad de nodos
    • Indica la importancia de un nodo dentro del grafo.
    • Tipos:
      • Grado: número de conexiones.
      • Betweenness: cuántos caminos más cortos pasan por el nodo.
      • Closeness: proximidad a todos los demás nodos.
      • Eigenvector: influencia global del nodo.
  • Clustering y cohesión
    • Coeficiente de clustering: mide tendencia de vecinos a estar conectados.
    • Comunidades: grupos de nodos densamente conectados.
  • Diámetro y radio del grafo
    • Diámetro: longitud del camino más largo mínimo.
    • Radio: distancia mínima desde nodo central.

Algoritmos de grafos avanzados

  • Algoritmos de caminos mínimos con restricciones
    • Con límites de pasos, costos o tiempo.
  • Algoritmos probabilísticos
    • Grafos aleatorios: generación y análisis de propiedades.
    • PageRank: importancia de nodos según enlaces entrantes.
  • Grafos dirigidos acíclicos (DAG)
    • Detección de ciclos en DAG.
    • Aplicación en scheduling y pipelines.
  • Matching y emparejamiento
    • Matching máximo en grafos bipartitos (Hungarian Algorithm).
    • Aplicaciones: asignación de tareas, emparejamiento de recursos.

Grafos en teoría de la complejidad

  • Problemas NP-completos en grafos
    • Clique máximo.
    • Vertex cover mínimo.
    • Hamiltonian path.
    • TSP (Traveling Salesman Problem).
  • Heurísticas y aproximaciones
    • Algoritmos greedy.
    • Algoritmos basados en backtracking.
    • Algoritmos aproximados y metaheurísticas.

Aplicaciones modernas de grafos

  • Redes sociales
    • Detección de comunidades, influencers, propagación de información.
  • Sistemas de recomendación
    • Representar usuarios y productos como grafos bipartitos.
  • Bioinformática
    • Redes de proteínas, genomas, rutas metabólicas.
  • Optimización de transporte y logística
    • Caminos mínimos, flujos máximos, rutas de distribución.
  • Inteligencia artificial
    • Grafos de conocimiento, planificación, estados en juegos.
  • Representación de datos
    • Compresión de datos binarios mediante grafos implícitos.
    • Transformación de arrays y bit manipulation.

Representaciones de bits en grafos

  • Contar 1s en números binarios
    • Relacionado con combinatoria de nodos/estados.
  • Transformar arrays a grafos
    • Cada elemento como nodo, relaciones según reglas de bits.
  • Problemas de “siguiente número mayor”
    • Encontrar configuración de bits con el mismo número de unos.
    • Aplicable a estados consecutivos en grafos implícitos.

Grafos dinámicos e implícitos

  • Grafos dinámicos
    • Permiten agregar y eliminar nodos o aristas durante la ejecución.
    • Útiles en simulaciones, redes en tiempo real, juegos.
  • Grafos implícitos
    • Nodos no almacenados explícitamente.
    • Cada nodo se genera mediante reglas o funciones.
    • Ejemplo: estados de un tablero de ajedrez, puzzle o combinaciones.

Propiedades métricas avanzadas

  • Centralidad
    • Betweenness: cantidad de caminos cortos que pasan por un nodo.
    • Closeness: proximidad promedio a todos los nodos.
    • Eigenvector: influencia global de un nodo dentro del grafo.
  • Coeficiente de clustering
    • Mide tendencia de los vecinos de un nodo a estar conectados.
  • Comunidades
    • Subgrafos densamente conectados con pocas conexiones externas.
  • Diámetro y radio
    • Diámetro: longitud del camino más largo mínimo entre nodos.
    • Radio: distancia mínima desde un nodo central a todos los demás.

Algoritmos especializados

  • Caminos mínimos con restricciones
    • Encontrar rutas respetando límites de pasos, costos o tiempo.
  • PageRank y algoritmos probabilísticos
    • Evaluar importancia relativa de nodos en redes complejas.
  • Matching y emparejamiento
    • Matching máximo en grafos bipartitos (Hungarian Algorithm).
  • Algoritmos de coloración
    • Asignación de colores a nodos sin que vecinos compartan color.
    • Útil en scheduling y resolución de conflictos.

Teoría de la complejidad en grafos

  • Problemas NP-completos
    • Clique máximo.
    • Vertex cover mínimo.
    • Hamiltonian path.
    • Traveling Salesman Problem (TSP).
  • Heurísticas y aproximaciones
    • Algoritmos greedy.
    • Backtracking.
    • Metaheurísticas (genéticos, recocido simulado, búsqueda local).

Aplicaciones modernas

  • Redes sociales
    • Detección de comunidades, influencers, propagación de información.
  • Bioinformática
    • Redes de proteínas, rutas metabólicas, genomas.
  • Sistemas de recomendación
    • Grafos bipartitos de usuarios y productos.
  • Optimización de transporte y logística
    • Rutas, flujos de transporte, asignación de recursos.
  • Inteligencia artificial y juegos
    • Grafos de conocimiento, planificación, búsqueda de estados.
  • Representación y compresión de datos
    • Mapear datos binarios y arrays a nodos y relaciones de grafos.

Representación avanzada de estados y bits

  • Estados implícitos y transiciones
    • Cada nodo representa un estado de un sistema.
    • Aristas representan transiciones posibles.
  • Manipulación de bits
    • Contar bits activos (1s) para generar combinaciones.
    • Encontrar el siguiente número con la misma cantidad de bits activos.
    • Aplicable a problemas combinatorios y optimización de estados.

Métricas de rendimiento y optimización

  • Memoria
    • Representaciones comprimidas (CSR, listas enlazadas compactas).
    • Eficiente para grafos extremadamente grandes.
  • Tiempo
    • Uso de estructuras hash y diccionarios para acceso rápido a vecinos.
    • Algoritmos aproximados para problemas NP-completos.