Jack Straws:
Análisis de
Conectividad
mediante Teoría de
Grafos: 1127
Fernando Mauricio Rosero
Piamba
Contenido
• Definición del problema
• Implementación
• Grafo recorrido
• Análisis de complejidad
• Aplicaciones
Definición del problema
En el juego de Jack Straws, se tiran varias pajitas
de plástico o madera sobre la mesa y los jugadores
intentan retirarlas una a una sin tocar las demás.
Aquí, solo nos interesa saber si varios pares de
pajitas están conectados por un camino de pajitas
que se tocan.
Especificación Matemática
Dado un conjunto S = {s₁, s₂, ..., sₙ} de segmentos de
línea en R², donde cada sᵢ está definido por sus puntos
extremos (x₁ᵢ, y₁ᵢ) y (x₂ᵢ, y₂ᵢ), el objetivo es construir un
grafo G = (V, E) donde V representa el conjunto de
pajitas y E las relaciones de adyacencia basadas en
intersecciones geométricas
Restricciones del problema:
1 < n < 13 pajitas por caso
Coordenadas menores a 100
No existen pajitas de longitud cero
Consultas múltiples por caso de prueba
Algoritmo de Detección de
Intersecciones
El algoritmo utiliza la función de orientación basada en el
producto cruzado de vectores para determinar la relación
espacial entre tres puntos, constituyendo el fundamento
matemático para la detección de intersecciones entre
segmentos de línea en el plano euclidiano.
Algoritmo de Detección de
Intersecciones
Construcción del Grafo de Adyacencia
• ANÁLISIS CRÍTICO: Implementación de Grafos en
el Algoritmo
• La construcción del grafo constituye el núcleo
fundamental del algoritmo, donde cada pajita se mapea
a un vértice y las intersecciones geométricas definen
las aristas, creando una representación abstracta del
problema físico mediante estructuras de datos
especializadas en teoría de grafos.
GRAFO: Construcción de Aristas
mediante Intersecciones
Búsqueda en Anchura (BFS) para
Conectividad
• El algoritmo BFS se ejecuta sobre el grafo de
adyacencia construido para determinar la conectividad
entre pares específicos de pajitas, explorando
sistemáticamente todas las componentes conexas
mediante una estrategia de búsqueda nivel por nivel
desde el vértice origen hasta alcanzar el vértice destino.
Búsqueda en Anchura (BFS) para
Conectividad
Complejidad Temporal
• El análisis de complejidad temporal revela que la
construcción del grafo domina el costo computacional
con O(n²) comparaciones de intersección, mientras que
cada consulta BFS requiere O(n + m) operaciones,
donde m representa el número de aristas en el grafo
construido.
Complejidad Espacial
• La complejidad espacial está determinada por la
representación del grafo mediante listas de adyacencia,
requiriendo O(n + m) espacio, donde m ≤ n(n-1)/2 en el
caso de un grafo completo, resultando en una
complejidad espacial total de O(n²) en el peor caso.
Estructura Espacio
Lista Adyacencia O(n + m)
Array Visitados O(n)
Cola BFS O(n)
Total O(n²)
Síntesis del Análisis de Grafos
El problema Jack Straws ejemplifica magistralmente la
aplicación de teoría de grafos en geometría
computacional, donde la abstracción matemática
mediante grafos no dirigidos permite resolver
eficientemente problemas de conectividad espacial que
serían computacionalmente prohibitivos mediante
enfoques geométricos puros.
Aplicación y extensiones del problema
Robótica: Planificación Redes: Conectividad en
de rutas con obstáculos topologías complejas