Teorema de Steinitz

En la combinatoria polièdrica, una branca de les matemàtiques, la teorema de Steinitz és una caracterisació dels grafos no dirigits formats per les arestes i els vèrtiços de poliedres convexos tridimensionals: són exactament els grafos planars de 3 vèrtiços conectats. És dir, tot poliedre convexo forma un grafo pla de 3 vèrtiços, i tot grafo pla de 3 vèrtiços pot representar-se com el grafo d'un poliedre convexo. Per esta raó, els grafos plans de 3 conexions també es coneixen com grafos polièdrics.

Este resultat proporciona un teorema de classificació per als poliedres convexos tridimensionals, alguna cosa que no es coneix en dimensions superiors. Proporciona una descripció completa i purament combinatòria dels grafos d'estos poliedres, permetent que atres resultats sobre ells, com el teorema de Eberhard sobre la realisació de poliedres en determinats tipos de cares, es demostren més fàcilment, sense referència a la geometria d'estes formes. Ademés, s'ha aplicat en el dibuix de grafos, com una forma de construir visualisacions tridimensionals de grafos abstractes. Branko Grünbaum ha cridat a esta teorema «el resultat més important i profunt conegut sobre els 3-politopos».

La teorema apareix en una publicació de 1922 d'Ernst Steinitz, que li dona nom. Pot demostrar-se per inducció matemàtica (com va fer Steinitz), trobant l'estat d'energia mínima d'un sistema de molls bidimensional i traslladant el resultat a tres dimensions, o utilisant el teorema del empaquetamiento de circumferències. Es coneixen vàries extensions de la teorema, en les que el poliedre que realisa un grafo dau té restriccions adicionals; per eixemple, tot grafo polièdric és el grafo d'un poliedre convexo en coordenades sanceres, o el grafo d'un poliedre convexo totes les arestes de les quals són tangentes a una semiesfera comuna.

Definicions i enunciat de la teorema

Allumenar l'esquelet d'un poliedre convexo des d'una font de llum propenca a una de les seues cares fa que les seues ombres formen un diagrama de Schlegel pla.

Un grafo no dirigit és un sistema de vèrtiços i arestes, cada una de les quals conecta dos dels vèrtiços. Com és habitual en la teoria de grafos, a efectes de la teorema de Steinitz estos grafos es llimiten a ser finitos (els vèrtiços i les arestes són conjunts finitos) i simples (no hi ha dos arestes que conecten els dos mateixos vèrtiços, i cap aresta conecta un vèrtiç en si mateixa). A partir de qualsevol poliedre es pot formar un grafo, fent que els vèrtiços del grafo corresponguen als vèrtiços del poliedre i conectant dos vèrtiços qualssevol del grafo per mig d'una aresta sempre que els dos vèrtiços corresponents del poliedre siguen els punts extrems d'una aresta del poliedre. Este grafo es coneix com l'esquelet del poliedre.

Un grafo és pla si es pot dibuixar en els seus vèrtiços com a punts en el pla euclídeo, i les seues arestes com a curves que conecten estos punts, de manera que no es creuen dos curves d'aresta i que el punt que representa un vèrtiç es trobe en la curva que representa una aresta només quan el vèrtiç és un extrem de l'aresta. Pel teorema de Fáry, tot dibuix pla pot endreçar-se de modo que les curves que representen les arestes siguen segments rectes. Un grafo està 3-conectat si té més de tres vèrtiços i, despuix de l'eliminació de dos dels seus vèrtiços qualssevol, qualsevol atre parell de vèrtiços permaneix conectat per un camí. La teorema de Steinitz afirma que estes dos condicions són necessàries i suficients per a caracterisar els esquelets dels poliedres convexos tridimensionals: un grafo donat $G$ és el gràfic d'un poliedre tridimensional convexo, si i només si $G$ és pla i està conectat per 3 vèrtiços.

Proves

Ilustració de la demostració del teorema de Balinski, que mostra el conjunt zero d'una funció llineal (blava) que passa per dos vèrtiços donats (groc) i els camins del método simplex que conecten el restant del gràfic (vert).

Una de les direccions de la teorema de Steinitz (la més fàcil de demostrar) afirma que el grafo de tot poliedre convexo és pla i està conectat per 3 punts. Com es mostra en l'ilustració, la planaridad pot demostrar-se utilisant un diagrama de Schlegel: si es coloca una font de llum prop d'una cara del poliedre, i un pla en l'atra cara, les ombres de les arestes del poliedre formaran un grafo planar, incrustat de tal manera que les arestes són segments de llínea recta. La 3-conectivitat d'un grafo polièdric és un cas especial del teorema de Balinski segons el qual el grafo de qualsevol $k$ dimensional politopo convexo està $k$ conectat. La conectivitat del grafo d'un politopo, despuix d'eliminar qualsevol $k-1$ dels seus vèrtiços, pot demostrar-se elegint un vèrtiç més $v$, trobant una funció llineal que siga zero en el conjunt resultant de vèrtiços $k$ i seguint els camins generats pel método simplex per a conectar cada vèrtiç en un dels dos vèrtiços extrems de la funció llineal, en el vèrtiç elegit $v$ conectat a abdós.

L'atra direcció, més difícil, de la teorema de Steinitz afirma que tot grafo pla de 3 conexions és el grafo d'un poliedre convexo. Existixen tres enfocaments estàndar per a esta part: proves per inducció, elevació d'embebidos bidimensionales de Tutte a tres dimensions per mig de la correspondència Maxwell-Cremona i métodos que utilisen el teorema del empaquetamiento de circumferència per a generar un poliedre canònic.

Inducció

ΔY- i IΔ-transformació d'un poliedre

Encara que la prova original de Steinitz no es va expressar en térmens de teoria de grafos, pot reescriure's en eixos térmens i consistix en trobar una seqüència de transformacions ΔY- i IΔ que reduïxen qualsevol grafo pla de 3 conexions a $K_4$, el grafo del tetraedre. Una transformació I elimina un vèrtiç de grau tres d'un grafo, afegint arestes entre tots els seus veïns anteriors si eixes arestes no existien ya; la transformació inversa, una transformació ΔI, elimina les arestes d'un triàngul d'un grafo i les substituïx per un nou vèrtiç de grau tres adjacent als mateixos tres vèrtiços. Una volta trobada una seqüència d'este tipo, pot invertir-se i convertir-se en operacions geomètriques que construïxquen pas a pas el poliedre desijat partint d'un tetraedre. Cada transformació I de la seqüència inversa pot realisar-se geomètricament tallant un vèrtiç de grau tres d'un poliedre. Una transformació ΔI en la seqüència inversa pot realisar-se geomètricament eliminant una cara triangular d'un poliedre i estenent les seues cares veïnes fins al punt a on es troben, pero només quan eixe punt d'intersecció triple de les tres cares veïnes està en el costat més alluntat de la cara eliminada del poliedre. Quan el punt de triple intersecció no està en el costat lluntà d'esta cara, basta una transformació proyectiva del poliedre per a moure-ho al costat correcte. Per tant, per inducció sobre el número de transformacions ΔY- i IΔ necessàries per a reduir un grafo donat a $K_4$, tot grafo polièdric pot realisar-se com un poliedre.

Un treball posterior de Epifanov va reforçar la prova de Steinitz de que tot grafo polièdric pot reduir-se a $K_4$ per mig de transformacions ΔY- i IΔ. Epifanov va demostrar que si s'especifiquen dos vèrtiços en un grafo pla, llavors el grafo pot reduir-se a una sola aresta entre eixos terminals combinant transformacions ΔY- i IΔ en reduccions serie-paralel. La prova de Epifanov era complicada i no constructiva, pero va ser simplificada per Truemper usant métodos basats en menors de grafos. Truemper va observar que tot grafo reticular és reducible per mig de transformacions ΔY- i IΔ d'esta manera, que esta reducibilidad es conserva per mig de menors de grafos, i que tot grafo pla és un menor d'un grafo reticular. Esta idea pot utilisar-se per a substituir el lema de Steinitz de que existix una seqüència de reducció. Despuix d'esta substitució, el restant de la demostració es pot portar a terme utilisant l'inducció de la mateixa manera que la demostració original de Steinitz. Per a estes demostracions, portades a terme utilisant qualsevol de les formes de trobar seqüències de ΔY- i IΔ-transformacions, existixen grafos polièdrics que requerixen un número no llineal de passos. Més concretament, tot grafo pla pot reduir-se utilisant un número de passos com a màxim proporcional a $n^{3/2}$, i infinites gràfiques requerixen un número de passos a lo manco proporcional a $n^{3/2}$, a on $n$ és el número de vèrtiços del grafo.

Una forma alternativa de prova per inducció es basa en eliminar arestes (i comprimir els vèrtiços de grau dos que puguen quedar despuix d'esta eliminació) o contraure arestes i formar un menor del grafo pla dau. Qualsevol grafo polièdric pot reduir-se a $K_4$ per un número llineal d'estes operacions, i de nou les operacions poden invertir-se i les operacions invertides realisar-se geomètricament, donant una realisació polièdrica del grafo. No obstant, encara que és més senzill demostrar que existix una seqüència de reducció per a este tipo d'argument, i les seqüències de reducció són més curtes, els passos geomètrics necessaris per a invertir la seqüència són més complicats.

Elevació

Si es dibuixa un gràfic en el pla en arestes rectilíneas, es definix una tensió d'equilibri com una assignació d'número real distints de zero

(pesos) a les arestes, en la propietat de que cada vèrtiç està en la posició donada per la mija ponderada dels seus veïns. Segons la correspondència Maxwell-Cremona, una tensió d'equilibri pot elevar-se a una superfície tridimensional contínua llineal a trossos tal que les arestes que formen els llímits entre les parts planes de la superfície es proyecten al dibuix donat. El pes i la llongitut de cada aresta determinen la diferència de pendents de la superfície a abdós costats de l'aresta, i la condició de que cada vèrtiç estiga en equilibri en els seus veïns equival a la condició de que estes diferències de pendents facen que la superfície es trobe en si mateixa correctament en el veïnat del vèrtiç. Els pesos positius es traduïxen en ànguls diedros convexos entre dos cares de la superfície llineal a trossos, i els pesos negatius es traduïxen en ànguls diedros cóncaus. A l'inversa, tota superfície llineal a trossos contínua procedix d'una tensió d'equilibri d'esta manera. Si es dibuixa un grafo pla finito i se li dona una tensió d'equilibri de tal forma que totes les arestes interiors del dibuix tinguen pesos positius, i totes les arestes exteriors tinguen pesos negatius, en traslladar esta tensió a una superfície tridimensional d'esta forma, i després substituir la superfície plana que representa l'exterior del grafo pel seu complement en el mateix pla, s'obté un poliedre convexo, en la propietat adicional de que la seua proyecció perpendicular sobre el pla no té creus.

La correspondència Maxwell-Cremona s'ha utilisat per a obtindre realisacions polièdriques de grafos polièdrics combinant-la en un método de dibuix de grafos en el pla de W. T. Tutte, l'embedido de Tutte. El método de Tutte comença fixant una cara d'un grafo polièdric en posició convexa en el pla. Esta cara es convertirà en la cara exterior del dibuix d'un grafo. El método continua establint un sistema d'equacions llineals en les coordenades dels vèrtiços, segons el qual cada vèrtiç restant deu situar-se en la mija dels seus veïns. Llavors, com va demostrar Tutte, este sistema d'equacions tindrà una solució única en la que cada cara del grafo es dibuixa com un polígon convexo. Intuitivamente, esta solució descriu el patró que s'obtindria substituint les arestes interiors del grafo per molls ideals i deixant que s'asentir en el seu estat de mínima energia. El resultat és casi una tensió d'equilibri: si s'assigna pes un a cada aresta interior, llavors cada vèrtiç interior del dibuix està en equilibri. No obstant, no sempre és possible assignar números negatius a les arestes exteriors per a que també estiguen en equilibri. Dita assignació sempre és possible quan la cara exterior és un triàngul, per lo que este método pot utilisar-se per a realisar qualsevol grafo polièdric que tinga una cara triangular. Si un grafo polièdric no conté una cara triangular, la seua grafo dual conté un triàngul i també és polièdric, per lo que es pot realisar el dual d'esta manera i després realisar el grafo original com el poliedre polar de la realisació dual. Un método alternatiu per a realisar poliedres utilisant elevació evita la dualitat per mig de l'elecció de qualsevol cara en un màxim de cinc vèrtiços com la cara exterior. Tot grafo polièdric té una cara d'este tipo, i elegint la forma fixa d'esta cara en més cuidat, es pot alçar la incrustación de Tutte del restant del grafo.

Empaquetamiento de circumferències

Un poliedre realisat a partir d'un empaquetamiento de círculs en la semiesfera blava. Cada vèrtiç del poliedre està representat en el empaquetamiento pel seu círcul horisó (roig). Cada cara està representada pel círcul format per la seua intersecció en l'esfera.

Segons una variant del teorema de empaquetamiento de circumferències, per a tot grafo polièdric existix un sistema de círculs en el pla o en qualsevol esfera, que representen els vèrtiços i les cares del grafo, de modo que:

• cada dos vèrtiços adjacents del grafo estan representats per círculs tangentes,
• cada dos cares adjacents del grafo estan representades per círculs tangentes,
• cada parell d'un vèrtiç i una cara a la que toca estan representats per círculs que es creuen en àngul recte, i
• tots els demés parells de círculs estan separats entre sí.

El mateix sistema de círculs forma una representació del grafo dual intercanviant els papers dels círculs que representen els vèrtiços i els círculs que representen les cares. A partir de qualsevol representació d'este tipo en una esfera, incrustada en un espai euclidiano tridimensional, es pot formar un poliedre convexo que és combinatoriamente equivalent al grafo donat, com una intersecció de semiespacios els llímits de la qual passen pels círculs de les cares. A partir de cada vèrtiç d'este poliedre, el horisó en l'esfera, vist des d'eixe vèrtiç, és el círcul que ho representa. Esta propietat de l'horisó determina la posició tridimensional de cada vèrtiç, i el poliedre pot definir-se equivalentemente com l'envolvente convexo dels vèrtiços, colocats d'esta forma. L'esfera es convertix en la semiesfera de la realisació: cada aresta del poliedre és tangente a l'esfera, en un punt a on dos círculs tangentes als vèrtiços creuen dos círculs tangentes a les cares.