Gráfico de un politopo

En la teoría de politopos , el grafo de aristas (también conocido como grafo vértice-arista o simplemente grafo ) de un politopo es un grafo combinatorio cuyos vértices y aristas corresponden directamente a los vértices y aristas del politopo. Como objeto puramente combinatorio , el grafo de aristas codifica información de incidencia, capturando qué vértices están conectados por aristas, pero no retiene datos geométricos como posiciones de vértices o longitudes de aristas. Otros nombres comunes para el grafo de aristas son esqueleto y 1-esqueleto , aunque algunos autores reservan estos términos para la incrustación geométrica formada por los vértices y aristas en el espacio ambiente del politopo . No existe una notación universalmente aceptada para el grafo de aristas de un politopo.${\displaystyle P}$Las notaciones comunes incluyen:${\displaystyle G_{P}}$,${\displaystyle G(P)}$o${\displaystyle \operatorname {skel} (P)}$.

No todos los grafos se pueden realizar como grafos de aristas de politopos; aquellos que sí se pueden realizar de esta manera se denominan grafos politópicos . Los grafos de aristas de politopos tridimensionales también se denominan grafos poliédricos . El problema de determinar si un grafo dado es politópico o no se conoce como problema de realización y es NP-difícil en dimensión general. En dimensión tres, el problema también se denomina problema de Steinitz, en reconocimiento a su resolución por Ernst Steinitz .

La información sobre las caras del politopo de dimensión dos o superior no es inmediatamente accesible desde el grafo de aristas, y a menudo no se puede reconstruir a partir de él en absoluto. Para capturar la estructura combinatoria completa de un politopo, incluyendo el número de caras de cada dimensión y las relaciones de incidencia entre ellas, es necesario trabajar con la red de caras del politopo . En analogía con el término "1-esqueleto", la parte de la red de caras que contiene la información sobre la combinatoria de las caras hasta la dimensión${\displaystyle k}$se llama el${\displaystyle k}$-esqueleto del politopo.

El grafo de aristas de un politopo convexo es un grafo simple finito . Es conexo , ya que se puede obtener un camino entre dos vértices cualesquiera mediante el algoritmo simplex . Para politopos de baja dimensión, la estructura del grafo de aristas está esencialmente determinada por la dimensión del politopo:

• El único politopo de dimensión 0 es el punto; su grafo de aristas es${\displaystyle K_{1}}$.
• El único politopo unidimensional es el segmento de línea; su grafo de aristas es${\displaystyle K_{2}}$.
• Los politopos bidimensionales son polígonos . El grafo de aristas de un${\displaystyle n}$-polígono de lados es${\displaystyle C_{n}}$, el ciclo con${\displaystyle n}$vértices.
• Los grafos de aristas de los politopos tridimensionales son ricos en estructura pero bien comprendidos: según el teorema de Steinitz, los grafos de aristas de los 3-politopos son precisamente los grafos planares conectados por 3 vértices , por esta razón también conocidos como grafos poliédricos .

Para${\displaystyle d}$-politopos con${\displaystyle d\geq 4}$No se conoce ninguna caracterización de los grafos de aristas. Se pueden hacer algunas afirmaciones generales:

• el grafo de aristas tiene un grado mínimo al menos${\displaystyle d}$. Si cada vértice de un${\displaystyle d}$-el politopo tiene grado exactamente${\displaystyle d}$(es decir, el grafo de aristas es${\displaystyle d}$-regular ), entonces se dice que el politopo es simple .
• el grafo de aristas es${\displaystyle d}$-conexo por vértices . Esto se conoce como el teorema de Balinski .
• El grafo de aristas contiene una subdivisión del grafo completo.${\displaystyle K_{d+1}}$. ^{[ 1 ]} En particular, para${\displaystyle d\geq 4}$, el grafo de aristas contiene un${\displaystyle K_{5}}$-menor y no es planar.

En general, no es trivial determinar si un grafo dado es el grafo de aristas de un politopo, es decir, si es un grafo politópico . Para algunas clases de grafos, como los grafos de grado mínimo${\displaystyle \delta \leq 3}$Las propiedades mencionadas anteriormente pueden ayudar a resolver esta cuestión. Por ejemplo, el grafo de Petersen es 3-regular . Por lo tanto, si fuera politopal, sería el grafo de aristas de un politopo tridimensional. Sin embargo, el grafo de Petersen no es planar y, por consiguiente, no puede ser el grafo de aristas de un 3-politopo.

Para gráficos de grado mínimo${\displaystyle \delta \geq 4}$Estas preguntas suelen ser mucho más difíciles de responder. Por ejemplo, a julio de 2025 se desconoce si el producto cartesiano de dos grafos de Petersen es politópico. ^{[ 2 ]} Se sabe que, si fuera politópico, el politopo debe tener dimensión cuatro o cinco. ^{[ 3 ]}

Algunas operaciones realizadas sobre politopos se traducen de forma natural a sus grafos de aristas.

• El grafo de aristas del producto cartesiano${\displaystyle P\times Q}$de dos politopos es el producto cartesiano de los grafos de aristas de${\displaystyle P}$y${\displaystyle Q}$. Por ejemplo, el producto de un gráfico cíclico y${\displaystyle K_{1}}$es el grafo de aristas de un prisma . Hay grafos no politópicos cuyo producto es politópico. ^{[ 3 ]}
• El grafo de aristas de la unión${\displaystyle P\star Q}$de dos politopos es la unión gráfica de los grafos de aristas de${\displaystyle P}$y${\displaystyle Q}$La unión de grafos se construye a partir de la unión disjunta de los grafos de aristas sumando todas las aristas entre ellos. Se obtiene el mismo grafo de aristas para la suma directa.${\displaystyle P\oplus Q}$(el dual del producto cartesiano) bajo el supuesto de que ambos${\displaystyle P}$y${\displaystyle Q}$son de dimensión al menos dos.
• Para politopos tridimensionales, el grafo de aristas del politopo dual es el grafo dual de su grafo de aristas.

Dado el grafo de aristas de un politopo de dimensión tres o inferior, es posible reconstruir la combinatoria completa del politopo , es decir, la lista completa de caras e incidencias entre ellas. Por ejemplo, las caras bidimensionales de un politopo de dimensión 3 corresponden exactamente a los ciclos inducidos no separables en el grafo de aristas. ^{[ 5 ]} Además, para politopos de dimensión hasta tres, es posible determinar la dimensión del politopo a partir del grafo de aristas. En dimensión${\displaystyle d\geq 4}$Ninguna de estas afirmaciones es cierta. Existen politopos combinatoriamente distintos con grafos de aristas isomorfos , e incluso politopos de diferentes dimensiones con grafos de aristas isomorfos.

• El algoritmo simplex recorre el grafo de aristas de un politopo para encontrar la solución óptima a un programa lineal .
• La conjetura de Hirsch afirma que el grafo de aristas de un${\displaystyle d}$-el politopo tiene un diámetro como máximo${\displaystyle d}$Santos encontró un contraejemplo en 2012. ^{[ 12 ]} Desde entonces, la conjetura se ha reformulado de diferentes maneras. A junio de 2025, no existe una cota polinómica para el diámetro en${\displaystyle d}$es conocido.
• Históricamente, los términos "vértice" y "arista" para los grafos se originaron en el estudio de los poliedros y solo posteriormente fueron adoptados en la teoría de grafos .