Il teorema di Steinitz

Il teorema di Steinitz (Reindirizzato da teorema di Steinitz) Vai alla navigazione Vai alla ricerca Questo articolo riguarda il teorema sui grafi dei poliedri. Per altri usi, vedi il teorema di Steinitz (disambiguazione).

In combinatoria poliedrica, una branca della matematica, Il teorema di Steinitz è una caratterizzazione dei grafi non orientati formati dai bordi e dai vertici di poliedri convessi tridimensionali: sono esattamente i grafi planari collegati a 3 vertici. Questo è, ogni poliedro convesso forma un grafo planare a 3 connessioni, e ogni grafo planare 3-connesso può essere rappresentato come il grafo di un poliedro convesso. Per questa ragione, i grafi planari 3-connessi sono anche conosciuti come grafi poliedrici.[1] Questo risultato fornisce un teorema di classificazione per i poliedri convessi tridimensionali, qualcosa che non è noto nelle dimensioni superiori.[2] Fornisce una descrizione completa e puramente combinatoria dei grafici di questi poliedri, consentendo altri risultati su di essi, come il teorema di Eberhard sulla realizzazione di poliedri con determinati tipi di facce, da provare più facilmente, senza riferimento alla geometria di queste forme.[3] Inoltre, è stato applicato nel disegno grafico, come un modo per costruire visualizzazioni tridimensionali di grafici astratti.[4] Branko Grünbaum ha chiamato questo teorema "il risultato più importante e più profondo conosciuto sui 3 politopi."[5] Il teorema compare in a 1922 pubblicazione di Ernst Steinitz,[6] da cui prende il nome. Può essere dimostrato per induzione matematica (come fece Steinitz), trovando lo stato di minima energia di un sistema a molla bidimensionale e elevando il risultato in tre dimensioni, o usando il teorema di impaccamento del cerchio. Sono note diverse estensioni del teorema, in cui il poliedro che realizza un dato grafo ha vincoli aggiuntivi; per esempio, ogni grafo poliedrico è il grafico di un poliedro convesso con coordinate intere, o il grafico di un poliedro convesso i cui bordi sono tutti tangenti a una sfera mediana comune.

Contenuti 1 Definizioni ed enunciato del teorema 2 Prove 2.1 Induzione 2.2 Sollevamento 2.3 Imballaggio circolare 3 Realizzazioni con ulteriori proprietà 3.1 Coordinate intere 3.2 Pari pendenze 3.3 Specificare la forma di una faccia 3.4 Sfere tangenti 4 Risultati correlati 5 Storia 6 Riferimenti Definizioni ed enunciato del teorema L'illuminazione dello scheletro di un poliedro convesso da una sorgente luminosa vicino a una delle sue facce fa sì che le sue ombre formino un diagramma di Schlegel planare.

Un grafo non orientato è un sistema di vertici e archi, ogni spigolo collega due dei vertici. Da qualsiasi poliedro si può formare un grafico, lasciando che i vertici del grafo corrispondano ai vertici del poliedro e collegando due vertici del grafo qualsiasi con un bordo ogni volta che i due vertici del poliedro corrispondenti sono i punti finali di un bordo del poliedro. Questo grafico è noto come lo scheletro del poliedro.[7] Un grafo è planare se può essere disegnato con i suoi vertici come punti nel piano euclideo, e i suoi bordi come curve che collegano questi punti, tale che non ci siano due curve di spigolo che si incrociano e tale che il punto che rappresenta un vertice si trovi sulla curva che rappresenta uno spigolo solo quando il vertice è un punto finale dello spigolo. Per il teorema di Fáry, ogni disegno planare può essere raddrizzato in modo che le curve che rappresentano i bordi siano segmenti di linea. Un grafo è 3-connesso se ha più di tre vertici e, dopo la rimozione di due qualsiasi dei suoi vertici, qualsiasi altra coppia di vertici rimane collegata da un percorso. Il teorema di Steinitz afferma che queste due condizioni sono sia necessarie che sufficienti per caratterizzare gli scheletri di poliedri convessi tridimensionali: un dato grafico {stile di visualizzazione G} è il grafico di un poliedro tridimensionale convesso, se e solo se {stile di visualizzazione G} è planare e connesso a 3 vertici.[5][8] Dimostrazioni Illustrazione della dimostrazione del teorema di Balinski, che mostra l'insieme zero di una funzione lineare (blu) passante per due vertici dati (giallo) e i cammini del metodo simplex che collegano il restante grafo (verde) Una direzione del teorema di Steinitz (la direzione più facile da dimostrare) afferma che il grafico di ogni poliedro convesso è planare e 3-connesso. Come mostrato nell'illustrazione, la planarità può essere mostrata usando un diagramma di Schlegel: se si posiziona una sorgente di luce vicino a una faccia del poliedro, e un aereo dall'altra parte, le ombre dei bordi del poliedro formeranno un grafico planare, incorporati in modo tale che i bordi siano segmenti di linea retta. La 3-connettività di un grafo poliedrico è un caso speciale del teorema di Balinski che il grafo di qualsiasi {stile di visualizzazione k} -il politopo convesso dimensionale è {stile di visualizzazione k} -collegato. La connettività del grafo di un politopo, dopo aver rimosso qualsiasi {stile di visualizzazione k-1} dei suoi vertici, può essere dimostrato scegliendo un altro vertice {stile di visualizzazione v} , trovare una funzione lineare che è zero sull'insieme risultante di {stile di visualizzazione k} vertici, e seguendo i percorsi generati dal metodo del simplesso per collegare ogni vertice a uno dei due vertici estremi della funzione lineare, con il vertice scelto {stile di visualizzazione v} collegato ad entrambi.[9] L'altro, più difficile, la direzione del teorema di Steinitz afferma che ogni grafo planare 3-connesso è il grafo di un poliedro convesso. Ci sono tre approcci standard per questa parte: prove per induzione, sollevamento di incorporamenti di Tutte bidimensionali in tre dimensioni utilizzando la corrispondenza Maxwell-Cremona, e metodi che utilizzano il teorema di impacchettamento del cerchio per generare un poliedro canonico.

Induction Δ-Y and Y-Δ transforms of a polyhedron Although Steinitz's original proof was not expressed in terms of graph theory, può essere riscritto in questi termini, e implica la ricerca di una sequenza di trasformate Δ-Y e Y-Δ che riducono qualsiasi grafo planare a 3 connessioni a {stile di visualizzazione K_{4}} , il grafico del tetraedro. Una trasformata Y-Δ rimuove un vertice di grado tre da un grafico, aggiungendo spigoli tra tutti i suoi precedenti vicini se quegli spigoli non esistevano già; la trasformazione inversa, una trasformata Δ-Y, rimuove i bordi di un triangolo da un grafico e li sostituisce con un nuovo vertice di terzo grado adiacente agli stessi tre vertici. Una volta trovata una tale sequenza, può essere invertito e convertito in operazioni geometriche che costruiscono passo dopo passo il poliedro desiderato partendo da un tetraedro. Ogni trasformata Y-Δ nella sequenza inversa può essere eseguita geometricamente tagliando un vertice di grado tre da un poliedro. Una trasformata Δ-Y nella sequenza inversa può essere eseguita geometricamente rimuovendo una faccia triangolare da un poliedro ed estendendo le sue facce vicine fino al punto in cui si incontrano, ma solo quando quel triplo punto di intersezione delle tre facce vicine si trova sul lato opposto della faccia rimossa dal poliedro. Quando il punto di intersezione triplo non è sul lato opposto di questa faccia, basta una trasformazione proiettiva del poliedro per spostarlo dalla parte corretta. Perciò, per induzione sul numero di trasformazioni Δ-Y e Y-Δ necessarie per ridurre un dato grafico a {stile di visualizzazione K_{4}} , ogni grafo poliedrico può essere realizzato come un poliedro.[5] Un lavoro successivo di Epifanov ha rafforzato la prova di Steinitz secondo cui ogni grafo poliedrico può essere ridotto a {stile di visualizzazione K_{4}} dalle trasformazioni Δ-Y e Y-Δ. Epifanov ha dimostrato che se due vertici sono specificati in un grafo planare, quindi il grafico può essere ridotto a un unico arco tra quei terminali combinando le trasformate Δ-Y e Y-Δ con riduzioni serie-parallele.[10] La dimostrazione di Epifanov era complicata e non costruttiva, ma è stato semplificato da Truemper utilizzando metodi basati su graph minors. Truemper ha osservato che ogni grafico a griglia è riducibile dalle trasformazioni Δ-Y e Y-Δ in questo modo, che questa riducibilità è preservata da graph minors, e che ogni grafo planare è un minore di un grafico a griglia.[11] Questa idea può essere utilizzata per sostituire il lemma di Steinitz secondo cui esiste una sequenza di riduzione. Dopo questa sostituzione, il resto della dimostrazione può essere eseguito utilizzando l'induzione allo stesso modo della dimostrazione originale di Steinitz.[8] Per queste prove, effettuato utilizzando uno qualsiasi dei modi per trovare sequenze di trasformate Δ-Y e Y-Δ, esistono grafi poliedrici che richiedono un numero non lineare di passaggi. Più precisamente, infiniti grafici richiedono un numero di passaggi almeno proporzionale a {stile di visualizzazione n^{3/2}} , dove {stile di visualizzazione n} è il numero di vertici nel grafico, e il limite superiore più noto del numero di passi sufficienti è maggiore, proporzionale a {stile di visualizzazione n^{2}} .[12] Una forma alternativa di prova di induzione si basa sulla rimozione dei bordi (e comprimendo i vertici di secondo grado che potrebbero essere rimasti dopo questa rimozione) o contrazione degli archi e formare un minore del grafo planare dato. Qualsiasi grafo poliedrico può essere ridotto a {stile di visualizzazione K_{4}} da un numero lineare di queste operazioni, e ancora le operazioni possono essere invertite e le operazioni invertite possono essere eseguite geometricamente, dando una realizzazione poliedrica del grafo. Tuttavia, mentre è più semplice dimostrare che esiste una sequenza di riduzione per questo tipo di argomento, e le sequenze di riduzione sono più brevi, i passaggi geometrici necessari per invertire la sequenza sono più complicati.[13] Sollecitazione di equilibrio di sollevamento sul grafico di un cubo Un tronco che solleva il disegno sollecitato (con le stesse posizioni 2d) into 3d If a graph is drawn in the plane with straight line edges, quindi uno stress di equilibrio è definito come un'assegnazione di numeri reali diversi da zero (pesi) ai bordi, con la proprietà che ogni vertice si trova nella posizione data dalla media pesata dei suoi vicini. Secondo la corrispondenza Maxwell-Cremona, una sollecitazione di equilibrio può essere sollevata su una superficie tridimensionale continua lineare a tratti in modo tale che i bordi che formano i confini tra le parti piatte della superficie sporgano al disegno dato. Il peso e la lunghezza di ciascun bordo determinano la differenza di pendenza della superficie su entrambi i lati del bordo, e la condizione che ogni vertice sia in equilibrio con i suoi vicini è equivalente alla condizione che queste differenze di pendenza facciano incontrare la superficie correttamente con se stessa nelle vicinanze del vertice. I pesi positivi si traducono in angoli diedri convessi tra due facce della superficie lineare a tratti, e i pesi negativi si traducono in angoli diedri concavi. al contrario, ogni superficie continua a tratti-lineare deriva in questo modo da una sollecitazione di equilibrio. Se viene tracciato un grafo planare finito e viene data una sollecitazione di equilibrio in modo tale che tutti i bordi interni del disegno abbiano pesi positivi, e tutti i bordi esterni hanno pesi negativi, quindi traducendo questa sollecitazione in una superficie tridimensionale in questo modo, e quindi sostituendo la superficie piana che rappresenta l'esterno del grafo con il suo complemento sullo stesso piano, si ottiene un poliedro convesso, con la proprietà aggiuntiva che la sua proiezione perpendicolare sul piano non ha incroci.[14][15] La corrispondenza Maxwell-Cremona è stata utilizzata per ottenere realizzazioni poliedriche di grafi poliedrici combinandola con un metodo di disegno di grafi planari di W. T. Tutte, l'incorporamento di Tutte. Il metodo di Tutte inizia fissando una faccia di un grafo poliedrico in posizione convessa nel piano. Questa faccia diventerà la faccia esterna di un disegno di un grafico. Il metodo prosegue impostando un sistema di equazioni lineari nelle coordinate del vertice, secondo cui ogni vertice rimanente dovrebbe essere posto alla media dei suoi vicini. Poi come ha mostrato Tutte, questo sistema di equazioni avrà una soluzione unica in cui ciascuna faccia del grafico è disegnata come un poligono convesso.[16] Intuitivamente, questa soluzione descrive lo schema che si otterrebbe sostituendo i bordi interni del grafo con molle ideali e lasciandole stabilizzare al loro stato di minima energia.[17] Il risultato è quasi uno stress di equilibrio: se si assegna peso uno a ciascun bordo interno, quindi ogni vertice interno del disegno è in equilibrio. Tuttavia, non è sempre possibile assegnare numeri negativi ai bordi esterni in modo che essi, anche, sono in equilibrio. Tale assegnazione è sempre possibile quando la faccia esterna è un triangolo, e quindi questo metodo può essere utilizzato per realizzare qualsiasi grafo poliedrico che abbia una faccia triangolare. Se un grafo poliedrico non contiene una faccia triangolare, il suo doppio grafo contiene un triangolo ed è anche poliedrico, così si può realizzare il duale in questo modo e poi realizzare il grafo originale come il poliedro polare della realizzazione duale.[4][18] Un metodo alternativo per realizzare i poliedri usando i sollevamenti evita la dualità scegliendo qualsiasi faccia con al massimo cinque vertici come faccia esterna. Ogni grafo poliedrico ha una tale faccia, e scegliendo più accuratamente la forma fissa di questo viso, l'incorporamento di Tutte del resto del grafico può essere sollevato.[19] Imballaggio circolare Un poliedro realizzato da un imballaggio circolare sulla sfera mediana blu. Ciascun vertice del poliedro è rappresentato nell'imballaggio dal suo cerchio di orizzonte (rosso). Ogni faccia è rappresentata dal cerchio formato dalla sua intersezione con la sfera.

Secondo una variante del teorema di impaccamento del cerchio, per ogni grafo poliedrico, esiste un sistema di cerchi nel piano o su qualsiasi sfera, che rappresentano i vertici e le facce del grafico, affinché: ogni due vertici adiacenti del grafico sono rappresentati da cerchi tangenti, ciascuna delle due facce adiacenti del grafico è rappresentata da un cerchio tangente, ogni coppia di un vertice e una faccia che tocca sono rappresentate da cerchi che si incrociano ad angolo retto, e tutte le altre coppie di cerchi sono separate l'una dall'altra.[20] Lo stesso sistema di cerchi forma una rappresentazione del grafo duale scambiando i ruoli dei cerchi che rappresentano i vertici, e cerchi che rappresentano i volti. Da qualsiasi rappresentazione del genere su una sfera, incorporato nello spazio euclideo tridimensionale, si può formare un poliedro convesso che è combinatoriamente equivalente al grafo dato, come un'intersezione di semispazi i cui confini passano attraverso i cerchi delle facce. Da ogni vertice di questo poliedro, l'orizzonte sulla sfera, visto da quel vertice, è il cerchio che lo rappresenta. Questa proprietà dell'orizzonte determina la posizione tridimensionale di ciascun vertice, e il poliedro può essere equivalentemente definito come lo scafo convesso dei vertici, posizionato in questo modo. La sfera diventa la sfera mediana della realizzazione: ogni bordo del poliedro è tangente alla sfera, in un punto in cui due cerchi di vertici tangenti incrociano due cerchi di facce tangenti.[21] Realizations with additional properties Integer coordinates It is possible to prove a stronger form of Steinitz's theorem, che qualsiasi grafo poliedrico può essere realizzato da un poliedro convesso le cui coordinate sono intere.[22] Per esempio, La dimostrazione originale di Steinitz basata sull'induzione può essere rafforzata in questo modo. Tuttavia, gli interi che risulteranno dalla costruzione di Steinitz sono doppiamente esponenziali nel numero di vertici del dato grafo poliedrico. Scrivere numeri di questa grandezza in notazione binaria richiederebbe un numero esponenziale di bit.[18] Geometricamente, ciò significa che alcune caratteristiche del poliedro possono avere dimensioni doppiamente esponenzialmente maggiori di altre, rendendo problematiche le realizzazioni derivate da questo metodo per applicazioni nel disegno grafico.[4] I ricercatori successivi hanno trovato algoritmi di realizzazione basati sul sollevamento che utilizzano solo un numero lineare di bit per vertice.[19][23] È anche possibile attenuare il requisito che le coordinate siano intere, e assegnare le coordinate in modo tale che il {stile di visualizzazione x} -le coordinate dei vertici sono interi distinti nell'intervallo da 0 a {stile di visualizzazione 2n-4} e le altre due coordinate sono numeri reali nell'intervallo unitario, in modo che ogni spigolo abbia almeno una lunghezza mentre il poliedro complessivo ha volume lineare.[24][25] È noto che alcuni grafici poliedrici sono realizzabili su griglie di sole dimensioni polinomiali; in particolare questo vale per le piramidi (realizzazioni di grafici delle ruote), prismi (realizzazioni di grafici prismatici), e poliedri impilati (realizzazioni di reti apollinee).[26] Un altro modo per affermare l'esistenza di realizzazioni intere è che ogni poliedro convesso tridimensionale ha un poliedro intero combinatoriamente equivalente.[22] Per esempio, il dodecaedro regolare non è esso stesso un poliedro intero, a causa delle sue facce regolari pentagonali, ma può essere realizzato come un piritoedro intero equivalente.[19] Questo non è sempre possibile in dimensioni superiori, dove esistono politopi (come quelli costruiti dalla configurazione di Perles) che non hanno equivalente intero.[27] Equal slopes A Halin graph is a special case of a polyhedral graph, formato da un albero incastonato planare (senza vertici di secondo grado) collegando le foglie dell'albero in un ciclo. Per i grafici di Halin, si possono scegliere realizzazioni poliedriche di tipo speciale: il ciclo esterno forma una faccia di base convessa orizzontale, e ogni altra faccia giace direttamente sopra la faccia di base (come nei poliedri realizzati mediante sollevamento), con tutte queste facce superiori che hanno la stessa pendenza. Superfici poliedriche con facce di uguale pendenza su qualsiasi poligono di base (non necessariamente convesso) può essere costruito dallo scheletro rettilineo del poligono, e un modo equivalente per descrivere questa realizzazione è che la proiezione bidimensionale dell'albero sulla faccia di base forma il suo scheletro rettilineo. La dimostrazione di questo risultato utilizza l'induzione: qualsiasi albero radicato può essere ridotto a un albero più piccolo rimuovendo le foglie da un nodo interno i cui figli sono tutti foglie, il grafo di Halin formato dall'albero più piccolo ha una realizzazione dall'ipotesi di induzione, ed è possibile modificare questa realizzazione per aggiungere un numero qualsiasi di figli foglia al nodo albero i cui figli sono stati rimossi.[28] Specifying the shape of a face In any polyhedron that represents a given polyhedral graph {stile di visualizzazione G} , i volti di {stile di visualizzazione G} sono esattamente i cicli in {stile di visualizzazione G} che non si separano {stile di visualizzazione G} in due componenti: questo è, rimuovendo un ciclo facciale da {stile di visualizzazione G} lascia il resto {stile di visualizzazione G} come sottografo connesso. Tali cicli sono chiamati cicli periferici. così, la struttura combinatoria delle facce (ma non le loro forme geometriche) è determinato in modo univoco dalla struttura del grafico. Un altro rafforzamento del teorema di Steinitz, di Barnette e Grünbaum, afferma che per qualsiasi grafo poliedrico, qualsiasi faccia del grafico, e qualsiasi poligono convesso che rappresenti quella faccia, è possibile trovare una realizzazione poliedrica dell'intero grafo che abbia la forma specificata per la faccia designata. Questo è correlato a un teorema di Tutte, che qualsiasi grafo poliedrico può essere disegnato nel piano con tutte le facce convesse e qualsiasi forma specificata per la sua faccia esterna. Tuttavia, i disegni grafici planari prodotti dal metodo di Tutte non si elevano necessariamente a poliedri convessi. Invece, Barnette e Grünbaum dimostrano questo risultato usando un metodo induttivo.[29] È anche sempre possibile, dato un grafo poliedrico {stile di visualizzazione G} e un ciclo arbitrario {stile di visualizzazione C} in {stile di visualizzazione G} , per trovare una realizzazione per la quale {stile di visualizzazione C} forma la sagoma della realizzazione in proiezione parallela.[30] Tangent spheres The realization of polyhedra using the circle packing theorem provides another strengthening of Steinitz's theorem: ogni grafo planare 3-connesso può essere rappresentato come un poliedro convesso in modo tale che tutti i suoi bordi siano tangenti alla stessa sfera unitaria, la sfera mediana del poliedro.[21] Eseguendo una trasformazione di Möbius accuratamente scelta di un imballaggio circolare prima di trasformarlo in un poliedro, è possibile trovare una realizzazione poliedrica che realizzi tutte le simmetrie del grafo sottostante, nel senso che ogni automorfismo del grafo è una simmetria della realizzazione poliedrica.[31][32] Più generalmente, Se {stile di visualizzazione G} è un grafo poliedrico e {stile di visualizzazione K} è qualsiasi corpo convesso tridimensionale liscio, è possibile trovare una rappresentazione poliedrica di {stile di visualizzazione G} in cui tutti gli spigoli sono tangenti a {stile di visualizzazione K} .[33] I metodi di impacchettamento del cerchio possono essere utilizzati anche per caratterizzare i grafici di poliedri che hanno una circonsfera attraverso tutti i loro vertici, o un'insfera tangente a tutti i loro volti. (Anche i poliedri con una circonsfera sono significativi nella geometria iperbolica come poliedri ideali.) In entrambi i casi, l'esistenza di una sfera equivale alla risolvibilità di un sistema di disuguaglianze lineari su variabili reali positive associate a ciascun bordo del grafo. Nel caso dell'insfera, queste variabili devono sommarsi esattamente a una su ogni ciclo di facce del grafico, e a più di uno per ogni ciclo non facciale. Doppiamente, per la circonferenza, le variabili devono sommarsi a una per ogni vertice, e più di uno su ciascun taglio con due o più vertici su ciascun lato del taglio. Sebbene possano esserci esponenzialmente molte disuguaglianze lineari da soddisfare, una soluzione (se ne esiste uno) può essere trovato in tempo polinomiale usando il metodo dell'ellissoide. I valori delle variabili di una soluzione determinano gli angoli tra coppie di cerchi in un imballaggio circolare il cui poliedro corrispondente ha la relazione desiderata con la sua sfera.[34][35] Risultati correlati I grafici dei poliedri tridimensionali non convessi potrebbero non essere collegati (sinistra), e anche per poliedri topologicamente sferici le cui facce sono semplici poligoni questi grafici potrebbero non essere 3-connessi (Giusto).[36] In qualsiasi dimensione superiore a tre, il problema algoritmico di Steinitz consiste nel determinare se un dato reticolo è il reticolo delle facce di un politopo convesso. È improbabile che abbia complessità temporale polinomiale, in quanto è NP-duro e più fortemente completo per la teoria esistenziale dei reali, anche per politopi quadridimensionali, dal teorema di universalità di Richter-Gebert.[37] Qui, la teoria esistenziale dei reali è una classe di problemi computazionali che possono essere formulati in termini di trovare variabili reali che soddisfino un dato sistema di equazioni e disequazioni polinomiali. Per il problema algoritmico di Steinitz, le variabili di un tale problema possono essere le coordinate del vertice di un politopo, e le equazioni e le disuguaglianze possono essere utilizzate per specificare la planarità di ciascuna faccia nel reticolo delle facce e la convessità di ciascun angolo tra le facce. Completezza significa che ogni altro problema in questa classe può essere trasformato in un'istanza equivalente del problema algoritmico di Steinitz, in tempo polinomiale. L'esistenza di una tale trasformazione implica questo, se il problema algoritmico di Steinitz ha una soluzione in tempo polinomiale, allora lo stesso vale per ogni problema nella teoria esistenziale dei reali, e ogni problema in NP.[38] Tuttavia, perché un dato grafico può corrispondere a più di un reticolo di facce, è difficile estendere questo risultato di completezza al problema del riconoscimento dei grafi di 4-politopi. La determinazione della complessità computazionale di questo problema di riconoscimento dei grafi rimane aperta.[39] I ricercatori hanno anche trovato caratterizzazioni grafo-teoriche dei grafici di alcune classi speciali di poliedri tridimensionali non convessi[36][40] e politopi convessi quadridimensionali.[39][41][42] Tuttavia, in entrambi i casi, il problema generale rimane irrisolto. Infatti, anche il problema di determinare quali grafi completi siano i grafi di poliedri non convessi (diverso da {stile di visualizzazione K_{4}} per il tetraedro e {stile di visualizzazione K_{7}} per il poliedro imperatore) rimane irrisolto.[43] Il teorema di Eberhard caratterizza parzialmente i multiinsiemi di poligoni che possono essere combinati per formare le facce di un poliedro convesso. Può essere dimostrato formando un grafo planare a 3 connessioni con il dato insieme di facce poligonali, e quindi applicare il teorema di Steinitz per trovare una realizzazione poliedrica di quel grafo.[3] László Lovász ha mostrato una corrispondenza tra rappresentazioni poliedriche di grafi e matrici realizzando gli invarianti dei grafi di Colin de Verdière degli stessi grafi. L'invariante di Colin de Verdière è il corank massimo di una matrice di adiacenza ponderata del grafico, in alcune condizioni aggiuntive che sono irrilevanti per i grafi poliedrici. Queste sono matrici quadrate simmetriche indicizzate dai vertici, con il peso del vertice {stile di visualizzazione i} nel coefficiente diagonale {stile di visualizzazione M_{io,io}} e con il peso del bordo {stile di visualizzazione i,j} nei coefficienti fuori diagonale {stile di visualizzazione M_{io,j}} e {stile di visualizzazione M_{j,io}} . Quando vertici {stile di visualizzazione i} e {stile di visualizzazione j} non sono adiacenti, il coefficiente {stile di visualizzazione M_{io,j}} deve essere zero. Questo invariante è al massimo tre se e solo se il grafo è un grafo planare. Come mostra Lovász, quando il grafico è poliedrico, una rappresentazione di esso come un poliedro può essere ottenuta trovando una matrice di adiacenza ponderata di corank tre, trovando tre vettori che formano una base per il suo spazio nullo, utilizzando i coefficienti di questi vettori come coordinate per i vertici di un poliedro, e ridimensionare questi vertici in modo appropriato.[44] History The history of Steinitz's theorem is described by Grünbaum (2007),[45] che ne nota la prima apparizione in forma criptica in una pubblicazione di Ernst Steinitz, originariamente scritto 1916.[6] Steinitz ha fornito maggiori dettagli nelle successive dispense, pubblicato dopo il suo 1928 Morte. Sebbene i trattamenti moderni del teorema di Steinitz lo affermino come una caratterizzazione della teoria dei grafi dei poliedri, Steinitz non usava il linguaggio dei grafici.[45] La formulazione della teoria dei grafi del teorema è stata introdotta all'inizio degli anni '60 da Branko Grünbaum e Theodore Motzkin, con la sua dimostrazione convertita anche alla teoria dei grafi in Grünbaum 1967 testo Politopi convessi.[45] Il lavoro di Epifanov sulle trasformazioni Δ-Y e Y-Δ, rafforzando la dimostrazione di Steinitz, era motivato da altri problemi oltre alla caratterizzazione dei poliedri. Verissimo (1989) attribuisce a Grünbaum l'osservazione della rilevanza di questo lavoro per il teorema di Steinitz.[11] La corrispondenza Maxwell-Cremona tra diagrammi di sollecitazione e sollevamenti poliedrici è stata sviluppata in una serie di articoli di James Clerk Maxwell da 1864 a 1870, basato su lavori precedenti di Pierre Varignon, William Rankine, e altri, e fu reso popolare alla fine dell'Ottocento da 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] Il teorema di impacchettamento del cerchio è stato dimostrato da Paul Koebe 1936[47][48] e (indipendentemente) addio. M. Andreev dentro 1970;[48][49] è stato reso popolare a metà degli anni '80 da William Thurston, chi (nonostante citando Koebe e Andreev) è spesso accreditato come uno dei suoi scopritori.[48] La versione di Andreev del teorema era già stata formulata come una caratterizzazione simile a Steinitz per alcuni poliedri nello spazio iperbolico,[49] e l'uso dell'imballaggio circolare per realizzare poliedri con sfere medie deriva dal lavoro di Thurston.[50] Il problema di caratterizzare i poliedri con sfere inscritte o circoscritte, alla fine risolto utilizzando un metodo basato su realizzazioni di impacchettamento del cerchio, risale all'opera inedita di René Descartes circa 1630[51] e a Jakob Steiner in 1832;[34][52] i primi esempi di poliedri che non hanno realizzazione con una circumsphere o insphere furono dati da Steinitz in 1928.[34][53] Riferimenti ^ Weissstein, Eric W., "Grafico poliedrico", MathWorld ^ Stormrock, Bernd (1987), "I complessi di confine di politopi convessi non possono essere caratterizzati localmente", Giornale della London Mathematical Society, Seconda serie, 35 (2): 314–326, CiteSeerX 10.1.1.106.3222, doi:10.1112/jlms/s2-35.2.314, SIG 0881520 ^ Salta su: a b Malkevitch, Joseph, "Tecniche per la dimostrazione di teoremi combinatori sui 3-politopi", Strutture geometriche (appunti del corso), City University di New York ^ Salta su: a b c d Eades, Peter; Garvan, Patrizio (1995), "Disegnare grafici planari sollecitati in tre dimensioni", nel Brandeburgo, Francesco Giuseppe (ed.), Disegno grafico, Simposio sul disegno grafico, GD '95, Passau, Germania, settembre 20-22, 1995, Atti, Appunti delle lezioni in Informatica, vol. 1027, Springer, pp. 212–223, doi:10.1007/BFb0021805, SIG 1400675 ^ Salta su: a b c Grunbaum, Branco (2003), "13.1 Il teorema di Steinitz", Politopi convessi, Testi di laurea in Matematica, vol. 221 (2nd ed.), Springer-Verlag, pp. 235–244, ISBN 0-387-40409-0 ^ Salta su: a b Steinitz, Ernst (1922), "IIIAB12: poliedri e divisioni dello spazio", Enciclopedia delle scienze matematiche (in tedesco), vol. Gruppo musicale 3 (Geometrie), pp. 1–139, Finito il 31. agosto 1916 ^ Più tecnicamente, questo grafico è lo scheletro 1; vedi Grunbaum (2003), p. 138, e Ziegler (1995), p. 64. ^ Salta su: un essere Ziegler, Gunter M. (1995), "Capitolo 4: Teorema di Steinitz per 3-politopi", Lezioni sui politopi, Testi di laurea in Matematica, vol. 152, Springer-Verlag, pp. 103–126, ISBN 0-387-94365-X ^ Balinski, M. l. (1961), "Sulla struttura a grafo di poliedri convessi in n-spazio", Pacific Journal of Mathematics, 11 (2): 431–434, doi:10.2140/pjm.1961.11.431, SIG 0126765 ^ Epifanov, G. V. (1966), "Riduzione di un grafo piano ad uno spigolo mediante trasformazioni stella-triangolo", Doklady Akademii Nauk SSSR (in russo), 166: 19–22, SIG 0201337, Zbl 0149.21301 ^ Salta su: a b Truemper, K. (1989), "Sulla riduzione delta-wye per i grafi planari", Rivista di teoria dei grafi, 13 (2): 141–148, doi:10.1002/jgt.3190130202, SIG 0994737 ^ Chang, Hsien Chih; Cossarini, Marco; Erickson, Jeff (2019), "Limiti inferiori per la riduzione elettrica sulle superfici", a Barquet, Gill; Wang, Gesù (eds.), 35th Simposio Internazionale sulla Geometria Computazionale (SoCG 2019), Leibniz Atti internazionali in informatica (LIPI), vol. 129, Sedia da giorno, Germania: Schloss Dagstuhl Leibniz Center for Computer Science, pp. 25:1–25:16, arXiv:1707.04683, doi:10.4230/LIPics.SoCG.25.2019, ISBN 978-3-95977-104-7, SIG 3968611 ^ Barnette, David W.; Grunbaum, Branco (1969), "Sul teorema di Steinitz sui 3-politopi convessi e su alcune proprietà dei grafi planari", a Chartrand, G.; Kapoor, S. F. (eds.), Le molteplici sfaccettature della teoria dei grafi: Atti della conferenza tenutasi presso la Western Michigan University, Kalamazoo, MI., ottobre 31 – novembre 2, 1968, Appunti delle lezioni in matematica, vol. 110, Springer, pp. 27–40, doi:10.1007/BFb0060102, SIG 0250916 ^ Maxwell, J. Impiegato (1864), "Su figure reciproche e diagrammi di forze", Rivista filosofica, 4esima serie, 27 (182): 250–261, doi:10.1080/14786446408643663 ^ Whiteley, Walter (1982), "Moti e sollecitazioni di poliedri proiettati", Topologia strutturale, 7: 13–38, hdl:2099/989, SIG 0721947 ^ Tutte, w. T. (1963), "Come disegnare un grafico", Atti della London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, SIG 0158387 ^ Brandes, Ulrik (2001), "Attingendo ad analogie fisiche", in commerciante, Michael; Wagner, Dorotea (eds.), Disegnare Grafici: Metodi e modelli, Appunti delle lezioni in Informatica, vol. 2025, Berlino: Springer, pp. 71–86, CiteSeerX 10.1.1.9.5023, doi:10.1007/3-540-44969-8_4, SIG 1880146 ^ Salta su: a b Onn, Shmuel; roccia di tempesta, Bernd (1994), "Un teorema quantitativo di Steinitz", Contributi all'algebra e alla geometria, 35 (1): 125–129, SIG 1287206 ^ Salta su: a b c Nastro tinto, Ares; Ruota, Gunter; Schulz, André (2011), "Incorporamenti di piccole griglie di 3 politopi", Discrete & Computational Geometry, 45 (1): 65–87, arXiv:0908.0488, doi:10.1007/s00454-010-9301-0, SIG 2765520, S2CID 10141034 ^ Brightwell, Graham R.; Scheinerman, Edward R. (1993), "Rappresentazioni di grafi planari", SIAM Journal sulla matematica discreta, 6 (2): 214–229, doi:10.1137/0406017, SIG 1215229 ^ Salta su: un essere Ziegler, Gunter M. (2007), "Politopi convessi: costruzioni estreme e forme f-vettoriali. Sezione 1.3: Il teorema di Steinitz tramite impaccamenti circolari", in Miller, Esdra; Reiner, Vincitore; roccia di tempesta, Bernd (eds.), Combinatoria geometrica, Serie di matematica IAS/Park City, vol. 13, Società matematica americana, pp. 628–642, ISBN 978-0-8218-3736-8 ^ Salta su: a b Grunbaum (2003), teorema 13.2.3, p. 244, lo afferma in una forma equivalente in cui le coordinate sono numeri razionali. ^ Buchino, Kevin; Schulz, André (2010), "Sul numero di spanning tree può avere un grafo planare", Nella montagna, Segno; Meyer, Ulrico (eds.), Algoritmi - ESA 2010, 18Simposio europeo annuale, Liverpool, UK, settembre 6-8, 2010, Atti, Parte I, Appunti delle lezioni in Informatica, vol. 6346, Springer, pp. 110–121, CiteSeerX 10.1.1.746.942, doi:10.1007/978-3-642-15775-2_10, ISBN 978-3-642-15774-5, SIG 2762847, S2CID 42211547 ^ Chrobak, Marek; Goodrich, Michael T.; Tamassia, Roberto (1996), "Disegni convessi di grafici in due e tre dimensioni", Atti del 12° Simposio ACM sulla geometria computazionale (SoCG '96), ACM, pp. 319–328, doi:10.1145/237218.237401, S2CID 1015103 ^ Schulz, André (2011), "Disegnare 3 politopi con una buona risoluzione dei vertici", Journal of Graph algoritmi e applicazioni, 15 (1): 33–52, doi:10.7155/veramente.00216, SIG 2776000 ^ Demaine, Eric D.; Schulz, André (2017), "Incorporamento di politopi impilati su una griglia di dimensioni polinomiali", Discrete & Computational Geometry, 57 (4): 782–809, arXiv:1403.7980, doi:10.1007/s00454-017-9887-6, SIG 3639604, S2CID 104867 ^ Grünbaum (2003), p. 96un. ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; tritare, Tommaso; Huber, Stefano; Li, Brian; Risteski, Andrej (2012), "Cosa rende un albero uno scheletro dritto?" (PDF), Atti della 24a conferenza canadese sulla geometria computazionale (CCCG'12) ^ Barnette, David W.; Grunbaum, Branco (1970), "Preassegnazione della forma di un viso", Pacific Journal of Mathematics, 32 (2): 299–306, doi:10.2140/pjm.1970.32.299, SIG 0259744 ^ Barnette, David W. (1970), "Proiezioni di 3 politopi", Israel Journal of Mathematics, 8 (3): 304–308, doi:10.1007/BF02771563, SIG 0262923, S2CID 120791830 ^ Hart, Giorgio W. (1997), "Calcolo dei poliedri canonici", Matematica in Educazione e Ricerca, 6 (3): 5–10^ Berna, Marshall W.; Eppstein, Davide (2001), "Trasformazioni di Möbius ottimali per la visualizzazione delle informazioni e il meshing", in allungamento, Frank K. H. UN.; Sacco, Jörg-Rüdiger; Tamassia, Roberto (eds.), Algoritmi e strutture dati, 7th Workshop Internazionale, WADS 2001, Provvidenza, RI, Stati Uniti d'America, agosto 8-10, 2001, Atti, Appunti delle lezioni in Informatica, vol. 2125, Springer, pp. 14–25, arXiv:cs/0101006, doi:10.1007/3-540-44634-6_3, S2CID 3266233 ^ Schramm, Oded (1992), "Come ingabbiare un uovo", Scoperte matematiche, 107 (3): 543–560, Bibcode:1992InMat.107..543S, doi:10.1007/BF01231901, SIG 1150601, S2CID 189830473 ^ Salta su: a b c Rivin, Igor (1996), "Una caratterizzazione di poliedri ideali in 3 spazi iperbolici", Annali di matematica, Seconda serie, 143 (1): 51–70, doi:10.2307/2118652, JSTOR 2118652, SIG 1370757 ^ Dillencourt, Michele B.; fabbro, Warren D. (1996), "Condizioni teoriche dei grafi per l'inscrivibilità e la realizzabilità di Delaunay", Matematica discreta, 161 (1–3): 63–77, doi:10.1016/0012-365X(95)00276-3, SIG 1420521 ^ Salta su: a b Eppstein, Davide; Mumford, Elena (2014), "Teoremi di Steinitz per poliedri ortogonali semplici", Giornale di geometria computazionale, 5 (1): 179–244, doi:10.20382/jocg.v5i1a10, SIG 3259910, S2CID 8531578 ^ Richter-Gebert, Jurgen (1996), Realizzazione Spazi di Politopi, Appunti delle lezioni in matematica, vol. 1643, Springer-Verlag, CiteSeerX 10.1.1.2.3495, doi:10.1007/BFb0093761, ISBN 978-3-540-62084-6, SIG 1482230 ^ Schäfer, Marco (2013), "Realizzabilità di grafici e collegamenti", in Pach, John (ed.), Trenta saggi sulla teoria dei grafi geometrici, New York: Springer, pp. 461–482, CiteSeerX 10.1.1.220.9651, doi:10.1007/978-1-4614-0110-0_24, SIG 3205168 ^ Salta su: a b Eppstein, Davide (2020), "Treetopes e loro grafici", Discrete & Computational Geometry, 64 (2): 259–289, arXiv:1510.03152, doi:10.1007/s00454-020-00177-0, SIG 4131546, S2CID 213885326 ^ Hong, Seok-Hee; Nagamochi, Hiroshi (2011), "Estendendo il teorema di Steinitz ai poliedri a forma di stella verso l'alto e ai poliedri sferici", algoritmica, 61 (4): 1022–1076, doi:10.1007/s00453-011-9570-x, SIG 2852056, S2CID 12622357 ^ Blind, Roswitha; Mani-Levitska, Peter (1987), "Enigmi e isomorfismi di politopi", Equazioni matematiche, 34 (2–3): 287–297, doi:10.1007/BF01830678, SIG 0921106, S2CID 120222616 ^ Kalai, Gil (1988), "Un modo semplice per distinguere un semplice politopo dal suo grafico", Rivista di teoria combinatoria, Serie A, 49 (2): 381–383, doi:10.1016/0097-3165(88)90064-7, SIG 0964396 ^ Ziegler, Gunter M. (2008), "Superfici poliedriche di genere elevato", Geometria differenziale discreta, Seminari di Oberwolfach, vol. 38, Springer, pp. 191–213, arXiv:matematica/0412093, doi:10.1007/978-3-7643-8621-4_10, ISBN 978-3-7643-8620-7, SIG 2405667, S2CID 15911143 ^ Lovász, Laszló (2001), "Rappresentazioni di Steinitz di poliedri e numero di Colin de Verdière", Rivista di teoria combinatoria, Serie B, 82 (2): 223–236, doi:10.1006/jctb.2000.2027, SIG 1842113 ^ Salta su: a b c Grunbaum, Branco (2007), "Grafici di poliedri; poliedri come grafici", Matematica discreta, 307 (3–5): 445–463, doi:10.1016/j.disc.2005.09.037, hdl:1773/2276, SIG 2287486 ^ Erickson, Jeff; Lin, Patrizio (2020), "Una corrispondenza toroidale Maxwell-Cremona-Delaunay", a Cabello, Sergio; Chen, Danny Z. (eds.), 36th Simposio Internazionale sulla Geometria Computazionale (SoCG 2020), Leibniz Atti internazionali in informatica (LIPI), vol. 164, Sedia da giorno, Germania: Schloss Dagstuhl Leibniz Center for Computer Science, pp. 40:1–40:17, arXiv:2003.10057, doi:10.4230/LIPics.SoCG.2020.40, ISBN 978-3-95977-143-6, S2CID 209514295 ^ Koebe, Paolo (1936), "Problemi di contatto di mappatura conforme", Rapporti sui negoziati dell'Accademia delle scienze sassone di Lipsia: Corso matematico-fisico (in tedesco), 88: 141–164 ^ Salta su: a b c Stephenson, Kenneth (2003), "Imballaggio circolare: un racconto matematico" (PDF), Avvisi dell'American Mathematical Society, 50 (11): 1376–1388, CiteSeerX 10.1.1.101.5592, SIG 2011604 ^ Salta su: a b Andreev, e. M. (1970), "Poliedri convessi negli spazi di Lobačevskiĭ", Matematicheskii Sbornik, 81 (123): 445–478, SIG 0259734 ^ Schramm, Oded (1991), "Esistenza e unicità di impaccamenti con combinatoria specificata", Israel Journal of Mathematics, 73 (3): 321–341, doi:10.1007/BF02773845, SIG 1135221, S2CID 121855202; vedere la discussione dopo il corollario 3.8, p. 329 ^ Federico, Pasquale Giuseppe (1982), Cartesio sui Poliedri: Uno studio del "Degli elementi solidi", Fonti nella storia della matematica e delle scienze fisiche, vol. 4, Springer, p. 52 ^ Steiner, Jakob (1832), "Domanda 77", Sviluppo sistematico della dipendenza delle forme geometriche l'una dall'altra (in tedesco), Berlino: G. Finck, p. 316 ^ Steinitz, Ernst (1928), "Informazioni sui problemi isoperimetrici con poliedri convessi", Diario di matematica pura e applicata (in tedesco), 1928 (159): 133–143, doi:10.1515/crll.1928.159.133, SIG 1581158, S2CID 199546274 Categorie: Grafici planariTeoria dei grafi geometriciCombinazione poliedricaTeoremi nella teoria dei grafiTeoremi nella geometria discreta