Théorème de Steinitz

Théorème de Steinitz (Redirigé à partir du théorème de Steinitz) Aller à la navigation Aller à la recherche Cet article concerne le théorème sur les graphes de polyèdres. Pour d'autres usages, voir le théorème de Steinitz (désambiguïsation).

En combinatoire polyédrique, une branche des mathématiques, Le théorème de Steinitz est une caractérisation des graphes non orientés formés par les arêtes et les sommets de polyèdres convexes tridimensionnels: ce sont exactement les graphes planaires connectés à 3 sommets. C'est-à-dire, tout polyèdre convexe forme un graphe planaire 3-connexe, et chaque graphe planaire 3-connexe peut être représenté comme le graphe d'un polyèdre convexe. Pour cette raison, les graphes planaires 3-connexes sont également appelés graphes polyédriques.[1] Ce résultat fournit un théorème de classification pour les polyèdres convexes tridimensionnels, quelque chose qui n'est pas connu dans les dimensions supérieures.[2] Il fournit une description complète et purement combinatoire des graphes de ces polyèdres, permettant d'autres résultats sur eux, comme le théorème d'Eberhard sur la réalisation de polyèdres avec des types de faces donnés, se prouver plus facilement, sans référence à la géométrie de ces formes.[3] En outre, il a été appliqué dans le dessin graphique, comme moyen de construire des visualisations tridimensionnelles de graphiques abstraits.[4] Branko Grünbaum a appelé ce théorème "le résultat connu le plus important et le plus profond sur les 3-polytopes."[5] Le théorème apparaît dans un 1922 édition d'Ernst Steinitz,[6] d'après qui il porte le nom. Il peut être prouvé par induction mathématique (comme l'a fait Steinitz), en trouvant l'état d'énergie minimale d'un système de ressort bidimensionnel et en élevant le résultat en trois dimensions, ou en utilisant le théorème d'emballage du cercle. Plusieurs extensions du théorème sont connues, dans lequel le polyèdre qui réalise un graphe donné a des contraintes supplémentaires; par exemple, tout graphe polyédrique est le graphe d'un polyèdre convexe de coordonnées entières, ou le graphe d'un polyèdre convexe dont toutes les arêtes sont tangentes à une sphère médiane commune.

Contenu 1 Définitions et énoncé du théorème 2 Preuves 2.1 Induction 2.2 Levage 2.3 Emballage circulaire 3 Réalisations avec des propriétés supplémentaires 3.1 Coordonnées entières 3.2 Pentes égales 3.3 Spécification de la forme d'un visage 3.4 Sphères tangentes 4 Résultats associés 5 Histoire 6 Références Définitions et énoncé du théorème L'éclairage du squelette d'un polyèdre convexe à partir d'une source lumineuse proche de l'une de ses faces fait que ses ombres forment un diagramme de Schlegel planaire.

Un graphe non orienté est un système de sommets et d'arêtes, chaque arête reliant deux des sommets. A partir de n'importe quel polyèdre on peut former un graphe, en faisant correspondre les sommets du graphe aux sommets du polyèdre et en reliant deux sommets quelconques du graphe par une arête chaque fois que les deux sommets correspondants du polyèdre sont les extrémités d'une arête du polyèdre. Ce graphe est connu sous le nom de squelette du polyèdre.[7] Un graphe est plan s'il peut être dessiné avec ses sommets comme des points dans le plan euclidien, et ses bords comme des courbes qui relient ces points, de sorte que deux courbes d'arête ne se croisent pas et que le point représentant un sommet se trouve sur la courbe représentant une arête uniquement lorsque le sommet est une extrémité de l'arête. Par le théorème de Fáry, chaque dessin planaire peut être redressé de sorte que les courbes représentant les bords soient des segments de ligne. Un graphe est 3-connexe s'il a plus de trois sommets et, après la suppression de deux de ses sommets, toute autre paire de sommets reste connectée par un chemin. Le théorème de Steinitz stipule que ces deux conditions sont à la fois nécessaires et suffisantes pour caractériser les squelettes de polyèdres convexes tridimensionnels: un graphique donné {style d'affichage G} est le graphe d'un polyèdre tridimensionnel convexe, si et seulement si {style d'affichage G} est planaire et connexe à 3 sommets.[5][8] Preuves Illustration de la preuve du théorème de Balinski, montrant l'ensemble zéro d'une fonction linéaire (bleu) passant par deux sommets donnés (jaune) et les chemins de la méthode du simplexe reliant le graphe restant (vert) Une direction du théorème de Steinitz (la direction la plus facile à prouver) déclare que le graphe de chaque polyèdre convexe est planaire et 3-connexe. Comme le montre l'illustration, la planéité peut être montrée à l'aide d'un diagramme de Schlegel: si l'on place une source lumineuse près d'une face du polyèdre, et un avion de l'autre côté, les ombres des arêtes du polyèdre formeront un graphe planaire, intégré de manière à ce que les bords soient des segments de droite. La 3-connectivité d'un graphe polyédrique est un cas particulier du théorème de Balinski selon lequel le graphe de tout {style d'affichage k} -polytope convexe dimensionnel est {style d'affichage k} -lié. La connectivité du graphe d'un polytope, après avoir retiré tout {style d'affichage k-1} de ses sommets, peut être prouvé en choisissant un sommet de plus {style d'affichage v} , trouver une fonction linéaire nulle sur l'ensemble résultant de {style d'affichage k} sommets, et en suivant les chemins générés par la méthode du simplexe pour connecter chaque sommet à l'un des deux sommets extrêmes de la fonction linéaire, avec le sommet choisi {style d'affichage v} connecté aux deux.[9] L'autre, Plus difficile, la direction du théorème de Steinitz stipule que tout graphe planaire 3-connexe est le graphe d'un polyèdre convexe. Il existe trois approches standard pour cette partie: preuves par induction, soulever les plongements de Tutte bidimensionnels en trois dimensions à l'aide de la correspondance Maxwell – Cremona, et procédés utilisant le théorème d'emballage circulaire pour générer un polyèdre canonique.

Induction Δ-Y and Y-Δ transforms of a polyhedron Although Steinitz's original proof was not expressed in terms of graph theory, il peut être réécrit en ces termes, et implique de trouver une séquence de transformées Δ-Y et Y-Δ qui réduisent tout graphe planaire 3-connexe à {style d'affichage K_{4}} , le graphique du tétraèdre. Une transformée Y-Δ supprime un sommet de degré trois d'un graphique, ajouter des arêtes entre tous ses anciens voisins si ces arêtes n'existaient pas déjà; la transformation inverse, une transformée Δ-Y, supprime les arêtes d'un triangle d'un graphe et les remplace par un nouveau sommet de degré trois adjacent aux trois mêmes sommets. Une fois qu'une telle séquence est trouvée, il peut être inversé et converti en opérations géométriques qui construisent pas à pas le polyèdre désiré à partir d'un tétraèdre. Chaque transformée Y-Δ dans la séquence inversée peut être effectuée géométriquement en découpant un sommet de degré trois d'un polyèdre. Une transformée Δ-Y dans la séquence inversée peut être effectuée géométriquement en supprimant une face triangulaire d'un polyèdre et en étendant ses faces voisines jusqu'au point où elles se rencontrent, mais seulement lorsque ce triple point d'intersection des trois faces voisines se trouve du côté éloigné de la face retirée du polyèdre. Lorsque le triple point d'intersection n'est pas de l'autre côté de cette face, une transformation projective du polyèdre suffit pour le déplacer du bon côté. Par conséquent, par induction sur le nombre de transformées Δ-Y et Y-Δ nécessaires pour réduire un graphe donné à {style d'affichage K_{4}} , tout graphe polyédrique peut être réalisé comme un polyèdre.[5] Un travail ultérieur d'Epifanov a renforcé la preuve de Steinitz selon laquelle chaque graphe polyédrique peut être réduit à {style d'affichage K_{4}} par transformées Δ-Y et Y-Δ. Epifanov a prouvé que si deux sommets sont spécifiés dans un graphe planaire, alors le graphe peut être réduit à un seul bord entre ces terminaux en combinant les transformées Δ-Y et Y-Δ avec des réductions série-parallèle.[10] La preuve d'Epifanov était compliquée et non constructive, mais il a été simplifié par Truemper en utilisant des méthodes basées sur les mineurs de graphe. Truemper a observé que chaque graphe de grille est réductible par les transformées Δ-Y et Y-Δ de cette manière, que cette réductibilité est préservée par les mineurs de graphe, et que chaque graphe planaire est un mineur d'un graphe en grille.[11] Cette idée peut être utilisée pour remplacer le lemme de Steinitz selon lequel une séquence de réduction existe. Après ce remplacement, le reste de la preuve peut être effectué par induction de la même manière que la preuve originale de Steinitz.[8] Pour ces preuves, effectué en utilisant l'une des manières de trouver des séquences de transformées Δ-Y et Y-Δ, il existe des graphes polyédriques qui nécessitent un nombre non linéaire d'étapes. Plus précisément, une infinité de graphes nécessitent un nombre de pas au moins proportionnel à {displaystyle n^{3/2}} , où {displaystyle n} est le nombre de sommets du graphe, et la meilleure borne supérieure connue sur le nombre d'étapes qui suffisent est plus grande, proportionnel à {displaystyle n^{2}} .[12] Une forme alternative de preuve par induction est basée sur la suppression des bords (et compression des sommets de degré deux qui pourraient rester après cette suppression) ou en contractant des arêtes et en formant un mineur du graphe planaire donné. Tout graphe polyédrique peut être réduit à {style d'affichage K_{4}} par un nombre linéaire de ces opérations, et encore les opérations peuvent être inversées et les opérations inversées effectuées géométriquement, donnant une réalisation polyédrique du graphe. Cependant, alors qu'il est plus simple de prouver qu'une suite de réduction existe pour ce type d'argument, et les séquences de réduction sont plus courtes, les étapes géométriques nécessaires pour inverser la séquence sont plus compliquées.[13] Contrainte d'équilibre de levage sur le graphe d'un cube Un frustum soulevant le dessin accentué (avec les mêmes positions 2d) into 3d If a graph is drawn in the plane with straight line edges, alors une contrainte d'équilibre est définie comme une affectation de nombres réels non nuls (poids) jusqu'aux bords, avec la propriété que chaque sommet est dans la position donnée par la moyenne pondérée de ses voisins. Selon la correspondance Maxwell-Cremona, une contrainte d'équilibre peut être élevée jusqu'à une surface tridimensionnelle continue linéaire par morceaux de sorte que les bords formant les limites entre les parties plates de la surface se projettent sur le dessin donné. Le poids et la longueur de chaque bord déterminent la différence des pentes de la surface de chaque côté du bord, et la condition que chaque sommet soit en équilibre avec ses voisins est équivalente à la condition que ces différences de pente font que la surface se rejoigne correctement au voisinage du sommet. Les poids positifs se traduisent par des angles dièdres convexes entre deux faces de la surface linéaire par morceaux, et les poids négatifs se traduisent par des angles dièdres concaves. inversement, chaque surface continue linéaire par morceaux provient d'une contrainte d'équilibre de cette manière. Si un graphe planaire fini est dessiné et reçoit une contrainte d'équilibre de telle sorte que tous les bords intérieurs du dessin aient des poids positifs, et toutes les arêtes extérieures ont des poids négatifs, puis en traduisant cette contrainte en une surface tridimensionnelle de cette manière, puis en remplaçant la surface plane représentant l'extérieur du graphe par son complément dans le même plan, on obtient un polyèdre convexe, avec la propriété supplémentaire que sa projection perpendiculaire sur le plan n'a pas de croisements.[14][15] La correspondance Maxwell – Cremona a été utilisée pour obtenir des réalisations polyédriques de graphes polyédriques en la combinant avec une méthode de dessin de graphe planaire de W. J. Tout, l'encastrement Tutte. La méthode de Tutte commence par fixer une face d'un graphe polyédrique en position convexe dans le plan. Cette face deviendra la face extérieure d'un dessin de graphe. La méthode se poursuit en mettant en place un système d'équations linéaires aux coordonnées des sommets, selon lequel chaque sommet restant doit être placé à la moyenne de ses voisins. Puis, comme Tutte l'a montré, ce système d'équations aura une solution unique dans laquelle chaque face du graphique est dessinée comme un polygone convexe.[16] Intuitivement, cette solution décrit le modèle qui serait obtenu en remplaçant les bords intérieurs du graphique par des ressorts idéaux et en les laissant se stabiliser à leur état d'énergie minimale.[17] Le résultat est presque une contrainte d'équilibre: si l'on attribue un poids un à chaque bord intérieur, alors chaque sommet intérieur du dessin est en équilibre. Cependant, il n'est pas toujours possible d'attribuer des nombres négatifs aux bords extérieurs afin qu'ils, aussi, sont en équilibre. Une telle affectation est toujours possible lorsque la face extérieure est un triangle, et donc cette méthode peut être utilisée pour réaliser n'importe quel graphe polyédrique qui a une face triangulaire. Si un graphe polyédrique ne contient pas de face triangulaire, son graphe dual contient un triangle et est également polyédrique, on peut donc réaliser le dual de cette manière et ensuite réaliser le graphe original comme le polyèdre polaire de la réalisation duale.[4][18] Une méthode alternative pour réaliser des polyèdres à l'aide de levages évite la dualité en choisissant n'importe quelle face avec au plus cinq sommets comme face extérieure. Tout graphe polyédrique a une telle face, et en choisissant plus soigneusement la forme fixe de ce visage, l'intégration de Tutte du reste du graphique peut être levée.[19] Emballage circulaire Un polyèdre réalisé à partir d'un emballage circulaire sur la sphère médiane bleue. Chaque sommet de polyèdre est représenté dans le garnissage par son cercle d'horizon (rouge). Chaque face est représentée par le cercle formé par son intersection avec la sphère.

Selon une variante du théorème d'emballage du cercle, pour tout graphe polyédrique, il existe un système de cercles dans le plan ou sur n'importe quelle sphère, représentant les sommets et les faces du graphe, pour que: chacun des deux sommets adjacents du graphe est représenté par des cercles tangents, chacune des deux faces adjacentes du graphe est représentée par un cercle tangent, chaque paire d'un sommet et d'une face qu'elle touche est représentée par des cercles qui se croisent à angle droit, et toutes les autres paires de cercles sont séparées les unes des autres.[20] Le même système de cercles forme une représentation du graphe dual en échangeant les rôles des cercles qui représentent les sommets, et des cercles qui représentent des visages. De toute représentation de ce type sur une sphère, intégré dans un espace euclidien tridimensionnel, on peut former un polyèdre convexe combinatoirement équivalent au graphe donné, comme une intersection de demi-espaces dont les limites passent par les cercles de face. De chaque sommet de ce polyèdre, l'horizon sur la sphère, vu de ce sommet, est le cercle qui le représente. Cette propriété d'horizon détermine la position tridimensionnelle de chaque sommet, et le polyèdre peut être défini de manière équivalente comme la coque convexe des sommets, positionné de cette façon. La sphère devient la sphère médiane de la réalisation: chaque arête du polyèdre est tangente à la sphère, en un point où deux cercles de sommets tangents croisent deux cercles de faces tangentes.[21] Realizations with additional properties Integer coordinates It is possible to prove a stronger form of Steinitz's theorem, que tout graphe polyédrique peut être réalisé par un polyèdre convexe dont les coordonnées sont des nombres entiers.[22] Par exemple, La preuve originale basée sur l'induction de Steinitz peut être renforcée de cette manière. Cependant, les nombres entiers qui résulteraient de la construction de Steinitz sont doublement exponentiels en nombre de sommets du graphe polyédrique donné. L'écriture de nombres de cette grandeur en notation binaire nécessiterait un nombre exponentiel de bits.[18] Géométriquement, cela signifie que certaines caractéristiques du polyèdre peuvent avoir une taille doublement exponentiellement plus grande que d'autres, rendant les réalisations dérivées de cette méthode problématiques pour des applications en dessin de graphes.[4] Des chercheurs ultérieurs ont trouvé des algorithmes de réalisation basés sur le levage qui n'utilisent qu'un nombre linéaire de bits par sommet.[19][23] Il est également possible d'assouplir l'exigence que les coordonnées soient des nombres entiers, et attribuer des coordonnées de manière à ce que {style d'affichage x} -les coordonnées des sommets sont des entiers distincts dans la plage de 0 à {style d'affichage 2n-4} et les deux autres coordonnées sont des nombres réels dans l'intervalle unitaire, de sorte que chaque arête a une longueur d'au moins un tandis que le polyèdre global a un volume linéaire.[24][25] Certains graphes polyédriques sont connus pour être réalisables sur des grilles de taille polynomiale uniquement; en particulier c'est vrai pour les pyramides (réalisations de graphes roues), prismes (réalisations de graphes prismatiques), et polyèdres empilés (réalisations de réseaux apolliniens).[26] Une autre façon d'énoncer l'existence de réalisations entières est que chaque polyèdre convexe tridimensionnel a un polyèdre entier combinatoirement équivalent.[22] Par exemple, le dodécaèdre régulier n'est pas lui-même un polyèdre entier, à cause de ses faces pentagonales régulières, mais il peut être réalisé comme un pyritoèdre entier équivalent.[19] Ce n'est pas toujours possible dans les dimensions supérieures, où il existe des polytopes (tels que ceux construits à partir de la configuration Perles) qui n'ont pas d'équivalent entier.[27] Equal slopes A Halin graph is a special case of a polyhedral graph, formé à partir d'un arbre plan enfoui (sans sommets de degré deux) en reliant les feuilles de l'arbre dans un cycle. Pour les graphiques de Halin, on peut choisir des réalisations polyédriques d'un type spécial: le cycle extérieur forme une face de base convexe horizontale, et toutes les autres faces se trouvent directement au-dessus de la face de base (comme dans les polyèdres réalisés par soulèvement), avec toutes ces faces supérieures ayant la même pente. Surfaces polyédriques avec des faces à pente égale sur n'importe quel polygone de base (pas nécessairement convexe) peut être construit à partir du squelette droit du polygone, et une manière équivalente de décrire cette réalisation est que la projection bidimensionnelle de l'arbre sur la face de base forme son squelette droit. La preuve de ce résultat utilise l'induction: tout arbre enraciné peut être réduit à un arbre plus petit en supprimant les feuilles d'un nœud interne dont les enfants sont tous des feuilles, le graphe de Halin formé à partir du plus petit arbre a une réalisation par l'hypothèse d'induction, et il est possible de modifier cette réalisation afin d'ajouter un nombre quelconque d'enfants feuilles au nœud d'arbre dont les enfants ont été supprimés.[28] Specifying the shape of a face In any polyhedron that represents a given polyhedral graph {style d'affichage G} , les visages de {style d'affichage G} sont exactement les cycles dans {style d'affichage G} qui ne se séparent pas {style d'affichage G} en deux composants: C'est, retirer un cycle facial de {style d'affichage G} laisse le reste de {style d'affichage G} sous forme de sous-graphe connexe. Ces cycles sont appelés cycles périphériques. Ainsi, la structure combinatoire des faces (mais pas leurs formes géométriques) est déterminé de manière unique à partir de la structure du graphe. Un autre renforcement du théorème de Steinitz, de Barnette et Grünbaum, déclare que pour tout graphe polyédrique, n'importe quelle face du graphique, et tout polygone convexe représentant cette face, il est possible de trouver une réalisation polyédrique du graphe entier qui a la forme spécifiée pour la face désignée. Ceci est lié à un théorème de Tutte, que tout graphe polyédrique peut être dessiné dans le plan avec toutes les faces convexes et toute forme spécifiée pour sa face extérieure. Cependant, les dessins de graphes plans produits par la méthode de Tutte ne se lèvent pas nécessairement en polyèdres convexes. À la place, Barnette et Grünbaum prouvent ce résultat en utilisant une méthode inductive.[29] Il est aussi toujours possible, étant donné un graphe polyédrique {style d'affichage G} et un cycle arbitraire {displaystyle C} dans {style d'affichage G} , trouver une réalisation pour laquelle {displaystyle C} forme la silhouette de la réalisation en projection parallèle.[30] Tangent spheres The realization of polyhedra using the circle packing theorem provides another strengthening of Steinitz's theorem: chaque graphe planaire 3-connexe peut être représenté comme un polyèdre convexe de telle sorte que toutes ses arêtes soient tangentes à la même sphère unitaire, la sphère médiane du polyèdre.[21] En effectuant une transformation de Möbius soigneusement choisie d'un garnissage circulaire avant de le transformer en polyèdre, il est possible de trouver une réalisation polyédrique qui réalise toutes les symétries du graphe sous-jacent, en ce sens que tout automorphisme de graphe est une symétrie de la réalisation polyédrique.[31][32] Plus généralement, si {style d'affichage G} est un graphe polyédrique et {style d'affichage K} est tout corps convexe tridimensionnel lisse, il est possible de trouver une représentation polyédrique de {style d'affichage G} où toutes les arêtes sont tangentes à {style d'affichage K} .[33] Les méthodes d'emballage de cercle peuvent également être utilisées pour caractériser les graphes de polyèdres qui ont une circonférence à travers tous leurs sommets, ou une sphère intérieure tangente à toutes leurs faces. (Les polyèdres avec une circonférence sont également importants en géométrie hyperbolique en tant que polyèdres idéaux.) Dans les deux cas, l'existence d'une sphère équivaut à la solvabilité d'un système d'inégalités linéaires sur des variables réelles positives associées à chaque arête du graphe. Dans le cas de l'insphère, ces variables doivent totaliser exactement un sur chaque cycle de face du graphique, et à plus d'un sur chaque cycle sans visage. Doublement, pour la circonférence, les variables doivent totaliser un à chaque sommet, et plus d'un à travers chaque coupe avec deux sommets ou plus de chaque côté de la coupe. Bien qu'il puisse y avoir un nombre exponentiel d'inégalités linéaires à satisfaire, une solution (s'il en existe un) peut être trouvé en temps polynomial en utilisant la méthode de l'ellipsoïde. Les valeurs des variables d'une solution déterminent les angles entre des paires de cercles dans un emballage circulaire dont le polyèdre correspondant a la relation souhaitée avec sa sphère.[34][35] Résultats associés Les graphiques de polyèdres tridimensionnels non convexes peuvent ne pas être connectés (la gauche), et même pour les polyèdres topologiquement sphériques dont les faces sont de simples polygones, ces graphes pourraient ne pas être 3-connectés (droit).[36] Dans toute dimension supérieure à trois, le problème algorithmique de Steinitz consiste à déterminer si un réseau donné est le réseau de faces d'un polytope convexe. Il est peu probable qu'il ait une complexité polynomiale en temps, car il est NP-difficile et plus fortement complet pour la théorie existentielle des réels, même pour les polytopes à quatre dimensions, par le théorème d'universalité de Richter-Gebert.[37] Ici, la théorie existentielle des réels est une classe de problèmes informatiques qui peuvent être formulés en termes de recherche de variables réelles qui satisfont un système donné d'équations polynomiales et d'inégalités. Pour le problème algorithmique de Steinitz, les variables d'un tel problème peuvent être les coordonnées des sommets d'un polytope, et les équations et inégalités peuvent être utilisées pour spécifier la planéité de chaque face dans le réseau de faces donné et la convexité de chaque angle entre les faces. L'exhaustivité signifie que tous les autres problèmes de cette classe peuvent être transformés en une instance équivalente du problème algorithmique de Steinitz, en temps polynomial. L'existence d'une telle transformation implique que, si le problème algorithmique de Steinitz admet une solution polynomiale en temps, il en va de même pour tous les problèmes de la théorie existentielle des réels, et chaque problème dans NP.[38] Cependant, car un graphe donné peut correspondre à plus d'un réseau de faces, il est difficile d'étendre ce résultat de complétude au problème de reconnaissance des graphes de 4-polytopes. La détermination de la complexité de calcul de ce problème de reconnaissance de graphes reste ouverte.[39] Les chercheurs ont également trouvé des caractérisations théoriques des graphes des graphes de certaines classes spéciales de polyèdres non convexes tridimensionnels[36][40] et polytopes convexes à quatre dimensions.[39][41][42] Cependant, dans les deux cas, le problème général reste non résolu. En effet, même le problème de déterminer quels graphes complets sont les graphes de polyèdres non convexes (autre que {style d'affichage K_{4}} pour le tétraèdre et {style d'affichage K_{7}} pour le polyèdre Empereur) reste non résolu.[43] Le théorème d'Eberhard caractérise partiellement les multi-ensembles de polygones qui peuvent être combinés pour former les faces d'un polyèdre convexe. Cela peut être prouvé en formant un graphe planaire à 3 connexions avec l'ensemble donné de faces de polygones, puis en appliquant le théorème de Steinitz pour trouver une réalisation polyédrique de ce graphe.[3] László Lovász a montré une correspondance entre des représentations polyédriques de graphes et des matrices réalisant les invariants de graphes de Colin de Verdière des mêmes graphes. L'invariant de Colin de Verdière est le co-rang maximum d'une matrice d'adjacence pondérée du graphe, sous certaines conditions supplémentaires qui ne sont pas pertinentes pour les graphes polyédriques. Ce sont des matrices carrées symétriques indexées par les sommets, avec le poids du sommet {style d'affichage i} dans le coefficient diagonal {style d'affichage M_{je,je}} et avec le poids du bord {style d'affichage i,j} dans les coefficients hors diagonale {style d'affichage M_{je,j}} et {style d'affichage M_{j,je}} . Lorsque les sommets {style d'affichage i} et {displaystyle j} ne sont pas adjacents, le coefficient {style d'affichage M_{je,j}} doit être nul. Cet invariant est au plus égal à trois si et seulement si le graphe est un graphe planaire. Comme le montre Lovász, lorsque le graphe est polyédrique, une représentation de celui-ci sous forme de polyèdre peut être obtenue en trouvant une matrice d'adjacence pondérée de corank trois, trouver trois vecteurs formant une base pour son espace nul, en utilisant les coefficients de ces vecteurs comme coordonnées des sommets d'un polyèdre, et mettre à l'échelle ces sommets de manière appropriée.[44] History The history of Steinitz's theorem is described by Grünbaum (2007),[45] qui note sa première apparition sous une forme cryptique dans une publication d'Ernst Steinitz, écrit à l'origine dans 1916.[6] Steinitz a fourni plus de détails dans des notes de cours ultérieures, publié après son 1928 décès. Bien que les traitements modernes du théorème de Steinitz l'énoncent comme une caractérisation théorique des graphes des polyèdres, Steinitz n'a pas utilisé le langage des graphes.[45] La formulation théorique des graphes du théorème a été introduite au début des années 1960 par Branko Grünbaum et Theodore Motzkin, avec sa preuve également convertie en théorie des graphes dans Grünbaum 1967 texte polytopes convexes.[45] Les travaux d'Epifanov sur les transformées Δ-Y et Y-Δ, renforcer la preuve de Steinitz, était motivée par d'autres problèmes que la caractérisation des polyèdres. Vraimper (1989) attribue à Grünbaum l'observation de la pertinence de ce travail pour le théorème de Steinitz.[11] La correspondance Maxwell – Cremona entre les diagrammes de contraintes et les levages polyédriques a été développée dans une série d'articles de James Clerk Maxwell de 1864 à 1870, d'après les travaux antérieurs de Pierre Varignon, Guillaume Rankine, et d'autres, et a été popularisé à la fin du XIXe siècle par Luigi Cremona.[46] The observation that this correspondence can be used with the Tutte embedding to prove Steinitz's theorem comes from Eades & Garvan (1995).[4] Le théorème d'emballage du cercle a été prouvé par Paul Koebe dans 1936[47][48] et (indépendamment) au revoir. M. Andreïev dans 1970;[48][49] il a été popularisé au milieu des années 1980 par William Thurston, qui (malgré la citation de Koebe et Andreev) est souvent considéré comme l'un de ses découvreurs.[48] La version d'Andreev du théorème était déjà formulée comme une caractérisation de type Steinitz pour certains polyèdres dans l'espace hyperbolique,[49] et l'utilisation de l'emballage circulaire pour réaliser des polyèdres avec des sphères médianes provient des travaux de Thurston.[50] Le problème de la caractérisation des polyèdres à sphères inscrites ou circonscrites, finalement résolu à l'aide d'une méthode basée sur des réalisations d'emballage circulaire, remonte aux travaux inédits de René Descartes vers 1630[51] et à Jakob Steiner dans 1832;[34][52] les premiers exemples de polyèdres qui n'ont pas de réalisation avec une sphère circonscrite ou insphérique ont été donnés par Steinitz dans 1928.[34][53] Références ^ Weissstein, Éric W., "Graphe polyédrique", MathWorld ^ Stormrock, Bernd (1987), "Les complexes limites de polytopes convexes ne peuvent pas être caractérisés localement", Journal de la Société mathématique de Londres, Deuxième série, 35 (2): 314–326, CiteSeerX 10.1.1.106.3222, est ce que je:10.1112/jlms/s2-35.2.314, M 0881520 ^ Sauter à: a b Malkevitch, Joseph, "Techniques pour prouver des théorèmes combinatoires sur les 3-polytopes", Structures géométriques (notes de cours), Université de la ville de New York ^ Aller à: a b c d Eades, Pierre; Garvan, patrick (1995), "Dessiner des graphes planaires accentués en trois dimensions", dans le Brandebourg, François-Joseph (éd.), Dessin graphique, Symposium sur le dessin de graphes, GD '95, Passau, Allemagne, Septembre 20-22, 1995, Procédure, Notes de cours en informatique, volume. 1027, Springer, pp. 212–223, est ce que je:10.1007/BFb0021805, M 1400675 ^ Sauter à: a b c Grünbaum, Branko (2003), "13.1 Théorème de Steinitz", Polytopes convexes, Textes d'études supérieures en mathématiques, volume. 221 (2sd éd.), Springer Verlag, pp. 235–244, ISBN 0-387-40409-0 ^ Sauter à: a b Steinitz, Ernst (1922), "IIIAB12: polyèdres et divisions de l'espace", Encyclopédie des sciences mathématiques (en allemand), volume. Band 3 (Géométries), pp. 1–139, Terminé le 31. Août 1916 ^ Plus techniquement, ce graphe est le 1-squelette; voir Grünbaum (2003), p. 138, et Ziegler (1995), p. 64. ^ Sauter à: a b Ziegler, Günter M. (1995), "Chapitre 4: Théorème de Steinitz pour les 3-polytopes", Conférences sur les polytopes, Textes d'études supérieures en mathématiques, volume. 152, Springer Verlag, pp. 103–126, ISBN 0-387-94365-X ^ Balinski, M. L. (1961), "Sur la structure graphique des polyèdres convexes dans l'espace n", Pacific Journal of Mathematics, 11 (2): 431–434, est ce que je:10.2140/pjm.1961.11.431, M 0126765 ^ Epifanov, g. V. (1966), "Réduction d'un graphe plan à une arête par des transformations étoile-triangle", Doklady Akademii Nauk SSSR (en russe), 166: 19–22, M 0201337, Zbl 0149.21301 ^ Sauter à: a b Truemper, K. (1989), "Sur la réduction delta-wye pour les graphes planaires", Journal de théorie des graphes, 13 (2): 141–148, est ce que je:10.1002/jgt.3190130202, M 0994737 ^ Chang, Hsien-Chih; Cossarini, Marcos; Erickson, Jef (2019), "Bornes inférieures pour la réduction électrique sur les surfaces", à Baréquet, Gill; Wang, Jésus (éd.), 35e Symposium international sur la géométrie computationnelle (SoCG 2019), Procédures internationales Leibniz en informatique (LIPics), volume. 129, Chaise de jour, Allemagne: Schloss Dagstuhl Leibniz Center for Computer Science, pp. 25:1–25:16, arXiv:1707.04683, est ce que je:10.4230/LIPics.SoCG.2019.25, ISBN 978-3-95977-104-7, M 3968611 ^ Barette, David W; Grünbaum, Branko (1969), "Sur le théorème de Steinitz concernant les 3-polytopes convexes et sur quelques propriétés des graphes planaires", à Chartrand, G.; Kapoor, S. F. (éd.), Les nombreuses facettes de la théorie des graphes: Actes de la conférence tenue à l'Université Western Michigan, Kalamazoo, MI., Octobre 31 - Novembre 2, 1968, Notes de cours en mathématiques, volume. 110, Springer, pp. 27–40, est ce que je:10.1007/BFb0060102, M 0250916 ^ Maxwell, J. Employé de bureau (1864), "Sur les figures réciproques et les diagrammes de forces", Magazine philosophique, 4ème série, 27 (182): 250–261, est ce que je:10.1080/14786446408643663 ^ Whiteley, Walter (1982), "Mouvements et contraintes des polyèdres projetés", Topologie structurelle, 7: 13–38, hdl:2099/989, M 0721947 ^ Tous, O. J. (1963), "Comment dessiner un graphique", Actes de la London Mathematical Society, 13: 743–767, est ce que je:10.1112/plms/s3-13.1.743, M 0158387 ^ Brandes, Ulrik (2001), "S'appuyant sur des analogies physiques", en marchand, Michael; wagner, Dorothée (éd.), Dessiner des graphiques: Méthodes et modèles, Notes de cours en informatique, volume. 2025, Berlin: Springer, pp. 71–86, CiteSeerX 10.1.1.9.5023, est ce que je:10.1007/3-540-44969-8_4, M 1880146 ^ Sauter à: un b Onn, Shmouel; tempête de roche, Bernd (1994), "Un théorème quantitatif de Steinitz", Contributions à l'algèbre et à la géométrie, 35 (1): 125–129, M 1287206 ^ Sauter à: a b c Ruban teint, Arès; Rotation, Günter; Schulz, André (2011), "Petits plongements de grille de 3-polytopes", Discrete & Computational Geometry, 45 (1): 65–87, arXiv:0908.0488, est ce que je:10.1007/s00454-010-9301-0, M 2765520, S2CID 10141034 ^ Brightwell, Graham R.; Scheinermann, Edouard R. (1993), "Représentations de graphes planaires", SIAM Journal sur les mathématiques discrètes, 6 (2): 214–229, est ce que je:10.1137/0406017, M 1215229 ^ Sauter à: a b Ziegler, Günter M. (2007), "Polytopes convexes: constructions extrêmes et formes vectorielles f. Section 1.3: Théorème de Steinitz via les emballages circulaires", à Miller, Esdras; Reiner, Victor; tempête de roche, Bernd (éd.), Combinatoire géométrique, Série de mathématiques IAS / Park City, volume. 13, Société mathématique américaine, pp. 628–642, ISBN 978-0-8218-3736-8 ^ Sauter à: a b Grünbaum (2003), théorème 13.2.3, p. 244, indique ceci sous une forme équivalente où les coordonnées sont des nombres rationnels. ^ Buchin, Kévin; Schulz, André (2010), "Sur le nombre d'arbres couvrants, un graphe planaire peut avoir", dans la montagne, Marquer; Meyer, Ulrich (éd.), Algorithmes - ESA 2010, 18e Symposium européen annuel, Liverpool, ROYAUME-UNI, Septembre 6-8, 2010, Procédure, Première partie, Notes de cours en informatique, volume. 6346, Springer, pp. 110–121, CiteSeerX 10.1.1.746.942, est ce que je:10.1007/978-3-642-15775-2_dix, ISBN 978-3-642-15774-5, M 2762847, S2CID 42211547 ^ Chrobak, marek; Goodrich, Michel T.; Tamassie, Robert (1996), "Dessins convexes de graphiques en deux et trois dimensions", Actes du 12e symposium de l'ACM sur la géométrie computationnelle (SoCG '96), ACM, pp. 319–328, est ce que je:10.1145/237218.237401, S2CID 1015103 ^ Schulz, André (2011), "Dessin de 3-polytopes avec une bonne résolution de vertex", Journal des algorithmes et applications de graphes, 15 (1): 33–52, est ce que je:10.7155/vraiment.00216, M 2776000 ^ Demaine, Éric D.; Schulz, André (2017), "Intégration de polytopes empilés sur une grille de taille polynomiale", Discrete & Computational Geometry, 57 (4): 782–809, arXiv:1403.7980, est ce que je:10.1007/s00454-017-9887-6, M 3639604, S2CID 104867 ^ Grünbaum (2003), p. 96un. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; hacher, Thomas; Huber, Stéphane; Li, Brian; Risteski, Andrej (2012), "Qu'est-ce qui fait d'un arbre un squelette droit?" (PDF), Actes de la 24e Conférence canadienne sur la géométrie computationnelle (CCCG'12) ^ Barette, David W; Grünbaum, Branko (1970), "Préassigner la forme d'un visage", Pacific Journal of Mathematics, 32 (2): 299–306, est ce que je:10.2140/pjm.1970.32.299, M 0259744 ^ Barette, David W.. (1970), "Projections de 3-polytopes", Journal israélien de mathématiques, 8 (3): 304–308, est ce que je:10.1007/BF02771563, M 0262923, S2CID 120791830 ^ Hart, George W. (1997), "Calcul des polyèdres canoniques", Mathematica dans l'éducation et la recherche, 6 (3): 5–10 ^ Berne, Marshall W.; Epstein, David (2001), "Transformations optimales de Möbius pour la visualisation et le maillage des informations", en étirement, Franck K. H. UN.; Sac, Jörg-Rüdiger; Tamassie, Robert (éd.), Algorithmes et structures de données, 7ème Atelier International, WADS 2001, Providence, IR, Etats-Unis, Août 8-10, 2001, Procédure, Notes de cours en informatique, volume. 2125, Springer, pp. 14–25, arXiv:cs/0101006, est ce que je:10.1007/3-540-44634-6_3, S2CID 3266233 ^ Schramm, Oded (1992), "Comment mettre un oeuf en cage", Découvertes mathématiques, 107 (3): 543–560, Code bib:1992DansMat.107..543S, est ce que je:10.1007/BF01231901, M 1150601, S2CID 189830473 ^ Sauter à: a b c Rivin, Igor (1996), "Une caractérisation des polyèdres idéaux dans l'espace 3 hyperbolique", Annales de Mathématiques, Deuxième série, 143 (1): 51–70, est ce que je:10.2307/2118652, JSTOR 2118652, M 1370757 ^ Dillencourt, Michel B.; Forgeron, Warren D.. (1996), "Conditions théoriques des graphes pour l'inscriptibilité et la réalisabilité de Delaunay", Mathématiques discrètes, 161 (1–3): 63–77, est ce que je:10.1016/0012-365X(95)00276-3, M 1420521 ^ Sauter à: a b Eppstein, David; Mumford, Hélène (2014), "Théorèmes de Steinitz pour les polyèdres orthogonaux simples", Journal de géométrie computationnelle, 5 (1): 179–244, est ce que je:10.20382/jocg.v5i1a10, M 3259910, S2CID 8531578 ^ Richter-Gebert, Jürgen (1996), Espaces de réalisation des polytopes, Notes de cours en mathématiques, volume. 1643, Springer Verlag, CiteSeerX 10.1.1.2.3495, est ce que je:10.1007/BFb0093761, ISBN 978-3-540-62084-6, M 1482230 ^ Schäfer, Marc (2013), "Réalisabilité des graphiques et des liens", à Pach, John (éd.), Trente essais sur la théorie des graphes géométriques, New York: Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, est ce que je:10.1007/978-1-4614-0110-0_24, M 3205168 ^ Sauter à: a b Eppstein, David (2020), "Les cimes des arbres et leurs graphiques", Discrete & Computational Geometry, 64 (2): 259–289, arXiv:1510.03152, est ce que je:10.1007/s00454-020-00177-0, M 4131546, S2CID 213885326 ^ Hong, Seok-Hee; Nagamochi, Hiroshi (2011), "Extension du théorème de Steinitz aux polyèdres en forme d'étoile vers le haut et aux polyèdres sphériques", Algorithmique, 61 (4): 1022–1076, est ce que je:10.1007/s00453-011-9570-x, M 2852056, S2CID 12622357 ^ Blind, Roswitha; Mani-Levitska, Pierre (1987), "Puzzles et isomorphismes polytopiques", Équations mathématiques, 34 (2–3): 287–297, est ce que je:10.1007/BF01830678, M 0921106, S2CID 120222616 ^ Kalai, Gil (1988), "Un moyen simple de distinguer un polytope simple de son graphe", Journal de théorie combinatoire, Série A, 49 (2): 381–383, est ce que je:10.1016/0097-3165(88)90064-7, M 0964396 ^ Ziegler, Günter M. (2008), "Surfaces polyédriques de genre élevé", Géométrie différentielle discrète, Séminaires Oberwolfach, volume. 38, Springer, pp. 191–213, arXiv:mathématiques/0412093, est ce que je:10.1007/978-3-7643-8621-4_dix, ISBN 978-3-7643-8620-7, M 2405667, S2CID 15911143 ^ Lovász, László (2001), "Représentations de Steinitz des polyèdres et du nombre de Colin de Verdière", Journal de théorie combinatoire, Série B, 82 (2): 223–236, est ce que je:10.1006/jctb.2000.2027, M 1842113 ^ Sauter à: a b c Grünbaum, Branko (2007), "Graphes de polyèdres; polyèdres sous forme de graphes", Mathématiques discrètes, 307 (3–5): 445–463, est ce que je:10.1016/j.disc.2005.09.037, hdl:1773/2276, M 2287486 ^ Erickson, Jef; Lin, patrick (2020), "Une correspondance toroïdale Maxwell-Crémone-Delaunay", à Cabello, Sergio; Chen, Danny Z. (éd.), 36e Symposium international sur la géométrie computationnelle (SoCG 2020), Procédures internationales Leibniz en informatique (LIPics), volume. 164, Chaise de jour, Allemagne: Schloss Dagstuhl Leibniz Center for Computer Science, pp. 40:1–40:17, arXiv:2003.10057, est ce que je:10.4230/LIPics.SoCG.2020.40, ISBN 978-3-95977-143-6, S2CID 209514295 ^ Koebe, Paul (1936), "Problèmes de contact de cartographie conforme", Rapports sur les négociations de l'Académie des sciences de Saxe à Leipzig: Cours de mathématiques-physique (en allemand), 88: 141–164 ^ Passer à: a b c Stephenson, Kenneth (2003), "Emballage circulaire: un conte mathématique" (PDF), Avis de l'American Mathematical Society, 50 (11): 1376–1388, CiteSeerX 10.1.1.101.5592, M 2011604 ^ Sauter à: a b Andreïev, E. M. (1970), "Polyèdres convexes dans les espaces de Lobačevskiĭ", Mathematicheskii Sbornik, 81 (123): 445–478, M 0259734 ^ Schramm, Oded (1991), "Existence et unicité des garnissages avec des combinatoires spécifiées", Journal israélien de mathématiques, 73 (3): 321–341, est ce que je:10.1007/BF02773845, M 1135221, S2CID 121855202; voir la discussion suivante Corollaire 3.8, p. 329 ^ Federico, Pascal Joseph (1982), Descartes sur les polyèdres: Une étude de la "Des éléments solides", Sources dans l'histoire des mathématiques et des sciences physiques, volume. 4, Springer, p. 52 ^ Steiner, Jacob (1832), "Question 77", Développement systématique de la dépendance des formes géométriques les unes aux autres (en allemand), Berlin: g. Fincke, p. 316 ^ Steinitz, Ernst (1928), "À propos des problèmes isopérimétriques avec des polyèdres convexes", Journal de mathématiques pures et appliquées (en allemand), 1928 (159): 133–143, est ce que je:10.1515/crll.1928.159.133, M 1581158, S2CID 199546274 Catégories: Graphes planairesThéorie des graphes géométriquesCombinatoire polyédriqueThéorèmes en théorie des graphesThéorèmes en géométrie discrète