Teorema de Fáry

Archiu:IllustrationZumSatzVonFary.png

Per mig d'un homeomorfisme adequat, B i D també es poden conectar en un segment recte

En el camp matemàtic de la teoria de grafos, la teorema de Fáry establix que qualsevol grafo pla simple pot ser dibuixat sense creus, de modo que totes les seues arestes siguen segments de recta. És dir, la possibilitat de dibuixar arestes curves en lloc de segments de llínea recta no permet dibuixar una classe més gran de grafos. La teorema du el nom d'István Fáry, encara que va ser demostrat de forma independent per Klaus Wagner (1936),István Fáry (1948) i Sherman K. Stein (1951).

Demostració

Archiu:Fary-induction.svg

Pas d'inducció per a la demostració de la teorema de Fáry

Una forma de provar la teorema de Fáry és usar el método d'inducció:

Siga G un grafo pla simple en n vèrtiços; es poden agregar arestes si és necessari per a que G siga un grafo máximamente pla. Si n < 3, el resultat és trivial. Si n ≥ 3, llavors totes les cares de G deuen ser triànguls, ya que es podria agregar una aresta a qualsevol cara en més costats conservant la planaridad, contradient la suposició de planaridad màxima. Ara, s'elegixen tres vèrtiços a, b, c que formen una cara triangular de G. Es prova per inducció sobre n que existix una reincrustación combinatoriamente isomorfa de G per mig de segments rectes en la que el triàngul abc és la cara exterior de la incrustación ("combinatoriamente isomòrfica" significa que els vèrtiços, arestes i cares del nou dibuix es poden fer correspondre en els de el dibuix anterior, de modo que totes les incidències entre arestes, vèrtiços i cares, no solament entre vèrtiços i arestes, es conserven). Com case base, el resultat és trivial quan n= 3 i a, b i c són els únics vèrtiços en G. Aixina, es pot supondre que n ≥ 4.

Per la fòrmula de Euler per a grafos plans, G té 3n − 6 arestes. De manera equivalent, si es definix la deficiència d'un vèrtiç v en G com 6 − grau(v), la suma de les deficiències és 12. Ya que G té a lo manco quatre vèrtiços i totes les cares de G són triànguls, es deduïx que cada vèrtiç en G té un grau d'a lo manco tres. Per lo tant, cada vèrtiç en G té deficiència com a màxim tres, per lo que hi ha a lo manco quatre vèrtiços en deficiència positiva. En particular es pot elegir un vèrtiç v en cinc veïns com a màxim que siga diferent de a, b i c. Siga ara G', que s'obté llevant v de G i retriangulando la cara f formada llevant v. Per inducció, G' té un reintegrament per mig de segments rectes combinatoriamente isomòrfica en la que abc és la cara exterior. Degut a que la reincrustación de G' era combinatoriamente isomorfa a G', en llevar-li les arestes que es varen agregar per a crear G', queda la cara f, que ara és un polígon P en cinc costats com a màxim. Per a completar el dibuix d'un nova incrustación isomòrfica combinatoria per mig de segments rectes de G, v deu colocar-se en el polígon i unir-se per mig de llínees rectes als vèrtiços del polígon. Per teorema de la galeria d'art, existix un punt interior a P en el que es pot colocar v de manera que les arestes des de v fins als vèrtiços de P no creuen cap atra aresta, completant la prova.

El pas d'inducció d'esta prova s'ilustra en l'image de la dreta.

Resultats relacionats

De Fraysseix, Pach i Pollack varen demostrar cóm trobar en temps llineal un dibuix de segments rectes en una cuadrícula en dimensions llineals dependents del tamany del grafo, donant un conjunt de punts universal en tamany quadràtic. Schnyder ha seguit un método similar per a demostrar llímits millorats i una caracterisació de planaridad basada en l'orde parcial d'incidència. El seu treball va emfatisar l'existència d'una partició particular de les vores d'un grafo pla màxim en tres arbres, conegut com bosc de Schnyder.

Les propietats del embebido de Tutte permeten establir que cada grafo pla 3-conectat es pot dibuixar en un pla sense creus, de modo que les seues arestes siguen segments de llínea recta i una cara exterior siga un polígon convexo (Tutte 1963). Dit embebido es pot determinar per mig de la posició d'equilibri d'un sistema de resorts que representa les arestes del grafo.

El teorema de Steinitz establix que cada grafo pla 3-conectat es pot representar com les vores d'un poliedre convexo en un espai tridimensional. Es pot formar un embebido en llínees rectes de $G,$ del tipo descrit per la teorema de Tutte, proyectant dita representació polièdrica en el pla.

El teorema de empaquetamiento de circumferències establix que cada grafo pla pot representar-se com el grafo d'intersecció d'una colecció de círculs que no es creuen en el pla. Colocar cada vèrtiç del grafo en el centre del círcul corresponent conduïx a una representació per mig de llínees rectes.

Plantilla:No resolt Heiko Harborth va plantejar la qüestió de si cada grafo pla té una representació per mig de segments rectes en la que totes les llongituts de les arestes són número entero. La validea de la conjectura de Harborth permaneixia sense demostrar Plantilla:As of. No obstant, se sap que existixen incrustaciones per mig de segments rectes de llongitut sancera para grafos cúbics.

Sachs (1983) va plantejar la qüestió de si cada grafo en un embebido sense enllaços en un espai euclídeo tridimensional té una incrustación sense enllaços en la que totes les vores estan representats per segments de llínea recta, de manera anàloga a la teorema de Fáry per a incrustaciones bidimensionales.

Bibliografia

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .