Grafo cúbico para niños

Un grafo cúbico es un tipo especial de grafo en el que cada punto (llamado vértice) está conectado a exactamente tres líneas (llamadas aristas). Imagina una red donde cada nudo tiene exactamente tres caminos que salen de él. En el mundo de las matemáticas, a esto se le llama también un grafo 3-regular.

Cuando un grafo cúbico es además un grafo bipartito (lo que significa que sus vértices se pueden dividir en dos grupos, y las aristas solo conectan vértices de grupos diferentes), se le llama grafo bicúbico.

¿Quiénes estudiaron los grafos cúbicos?

Los grafos cúbicos han sido un tema interesante para muchos matemáticos a lo largo de la historia. Aquí te contamos algunos momentos importantes:

Primeras ideas y desafíos

• En 1880, un matemático llamado Peter Guthrie Tait pensó que todos los grafos cúbicos que se podían dibujar en un plano sin que sus líneas se cruzaran y que no tuvieran "puentes" (aristas que, si se quitan, dividen el grafo en dos partes) siempre tendrían un "circuito hamiltoniano". Un circuito hamiltoniano es un camino que visita cada vértice del grafo exactamente una vez y regresa al punto de partida.
• Sin embargo, en 1946, otro matemático, William Thomas Tutte, encontró un ejemplo de un grafo cúbico que no cumplía con la idea de Tait. Este grafo tenía 46 vértices y ahora se le conoce como el grafo de Tutte.

Colecciones de grafos especiales

• En 1934, Ronald M. Foster empezó a reunir ejemplos de grafos cúbicos que eran "simétricos". Esto significa que se veían igual desde diferentes puntos de vista. Esta colección se convirtió en el famoso Censo de Foster, una lista importante para los matemáticos.

Nuevos retos y descubrimientos

• En 1971, William Tutte propuso otra idea: que todos los grafos bicúbicos tendrían circuitos hamiltonianos. Pero, al igual que con la idea de Tait, otro matemático llamado Horton encontró un contraejemplo en 1976, un grafo de 96 vértices que no tenía un circuito hamiltoniano.
• En 2003, Petr Hliněný demostró que calcular el "número de cruzamiento" de un grafo cúbico es un problema muy difícil. El número de cruzamiento es la cantidad mínima de veces que las aristas de un grafo se cruzan cuando lo dibujas en un plano. Aunque es complicado, existen métodos para encontrar soluciones aproximadas.

Galería de imágenes

• 

  El Grafo de Petersen es un grafo cúbico.

Véase también

En inglés: Cubic graph Facts for Kids