Appiattibilità del grafico

[ad_1]

Appiattibilità in alcuni{\ displaystyle d}lo spazio vettoriale normale -dimensionale è una proprietà dei grafi che afferma che qualsiasi incorporazione , o disegno , del grafo in una dimensione elevata{\ displaystyle d’}può essere “appiattito” per viverci{\ displaystyle d}-dimensioni, tali da preservare le distanze tra coppie di punti collegati da spigoli. Un grafico{\ displaystyle G}è{\ displaystyle d}-appiattibile se ogni sistema di vincolo di distanza (DCS) con{\ displaystyle G}poiché il suo grafo di vincolo ha a{\ displaystyle d}quadro dimensionale . L’appiattibilità è stata inizialmente chiamata realizzabilità, ma il nome è stato cambiato per evitare confusione con un grafo avente alcuni DCS con un{\ displaystyle d}-struttura dimensionale.

L’appiattibilità ha collegamenti con rigidità strutturale , tensegrità , spazi di configurazione di Cayley e una variante del problema di realizzazione del grafico .

Definizioni

Un sistema di vincoli di distanza{\ displaystyle (G, \ delta )}, dove{\ displaystyle G = (V, E)}è un grafico e{\displaystyle \delta:E\freccia destra\mathbb {R} ^{|E|}}è un’assegnazione di distanze sui bordi di{\ displaystyle G}, è{\ displaystyle d}-appiattibile in uno spazio vettoriale normato{\displaystyle \mathbb {R} ^{d}}se esiste un quadro di{\ displaystyle (G, \ delta )}in{\ displaystyle d}-dimensioni.

Un grafico{\ displaystyle G = (V, E)}è{\ displaystyle d}-appiattibile in{\displaystyle \mathbb {R} ^{d}}se ogni sistema di vincoli di distanza con{\ displaystyle G}come è il suo grafico di vincolo{\ displaystyle d}-appiattibile.

L’appiattibilità può anche essere definita in termini di spazi di configurazione Cayley , vedere sotto il collegamento agli spazi di configurazione Cayley .

Proprietà

Chiusura sotto sottoparagrafi. L’appiattibilità è chiusa con i sottotitoli. Per vedere questo, osservalo per alcuni grafici{\ displaystyle G}, tutti i possibili incorporamenti di un sottografo{\ displaystyle H}di{\ displaystyle G}sono contenuti nell’insieme di tutti gli embedding di{\ displaystyle G}.

Minore chiuso. L’appiattibilità è una proprietà minore chiusa da un argomento simile come sopra.

Dimensione appiattita. La dimensione di appiattimento di un grafico{\ displaystyle G}in qualche spazio vettoriale normato è la dimensione più bassa{\ displaystyle d}tale che{\ displaystyle G}è{\ displaystyle d}-appiattibile. La dimensione di appiattimento di un grafico è strettamente correlata alla sua dimensione in grammi. Quello che segue è un limite superiore sulla dimensione di appiattimento di un grafo arbitrario sotto il{\displaystyle l_{2}}-norma.

Teorema. La dimensione di appiattimento di un grafo{\ displaystyle G = \ sinistra (V, E \ destra)}sotto il{\displaystyle l_{2}}-la norma è al massimo{\ displaystyle O \ sinistra ({\ sqrt {\ sinistra | E \ destra |}} \ destra)}.

Per una trattazione dettagliata di questo argomento, si veda il Capitolo 11.2 del.

Appiattibilità euclidea

Questa sezione riguarda i risultati di appiattibilità nello spazio euclideo , dove la distanza viene misurata utilizzando il{\displaystyle l_{2}}norma, detta anche norma euclidea .

-Grafici appiattibili

Il seguente teorema è folclore e mostra che l’unico minore proibito per{\ displaystyle 1}-l’appiattibilità è il grafico completo{\displaystyle K_{3}}.

Teorema. Un grafico è 1-appiattibile se e solo se è una foresta .

Figura 1. A{\ displaystyle 2}in blu è mostrato il quadro dimensionale di un DCS il cui grafo è un albero con sei vertici. UN{\ displaystyle 1}-il quadro dimensionale della stessa DCS è mostrato in rosso.
Figura 1. A{\ displaystyle 2}in blu è mostrato il quadro dimensionale di un DCS il cui grafo è un albero con sei vertici. UN{\ displaystyle 1}-il quadro dimensionale della stessa DCS è mostrato in rosso.

Prova. Una dimostrazione può essere trovata in. Per una direzione, una foresta è un insieme di alberi e qualsiasi sistema di vincoli di distanza il cui grafico è un albero può essere realizzato in{\ displaystyle 1}-dimensione. Per l’altra direzione, se un grafico{\ displaystyle G}non è una foresta, quindi ha il grafico completo{\displaystyle K_{3}}come sottografo. Considera il DCS che assegna la distanza{\ displaystyle 1}ai bordi del{\displaystyle K_{4}}sottografo e la distanza{\ displaystyle 0}a tutti gli altri bordi. Questa DCS ha una realizzazione in 2 dimensioni come lo scheletro 1 di un triangolo, ma non ha realizzazione in{\ displaystyle 1}-dimensione.

Questa prova consentiva di avere distanze sui bordi{\ displaystyle 0}, ma l’argomento vale anche quando ciò non è consentito. Vedere per una spiegazione dettagliata.

Figura 2. Per alcuni collegamenti, questo grafo ha una realizzazione unidimensionale (es. l'assegnazione di 1 a ogni arco). Tuttavia,{\displaystyle C_{3}}C_{3}si ottiene contraendo il bordo{\displaystyle {\bar {AB}}}{\displaystyle {\bar {AB}}}, quindi il grafico non lo è{\ displaystyle 1}1-appiattibile.
Figura 2. Per alcuni collegamenti, questo grafo ha una realizzazione unidimensionale (es. l’assegnazione di 1 a ogni arco). Tuttavia,{\displaystyle C_{3}}C_{3}si ottiene contraendo il bordo{\displaystyle {\bar {AB}}}{\displaystyle {\bar {AB}}}, quindi il grafico non lo è{\ displaystyle 1}1-appiattibile.

2 -Grafici appiattibili

Il seguente teorema è folclore e mostra che l’unico minore proibito per{\ displaystyle 2}-l’appiattibilità è il grafico completo{\displaystyle K_{4}}.

Teorema. Un grafo è 2-appiattibile se e solo se è un 2-albero parziale .

Prova. Una dimostrazione può essere trovata in. Per una direzione, poiché l’appiattibilità è chiusa prendendo i sottografi, è sufficiente mostrare che 2-alberi sono 2-appiattibili. Un 2 alberi con{\ displaystyle n}i vertici possono essere costruiti ricorsivamente prendendo un albero 2 con{\ displaystyle n-1}vertici e collegando un nuovo vertice ai vertici di un bordo esistente. Il caso base è il{\displaystyle K_{3}}. Procedere per induzione sul numero di vertici{\ displaystyle n}. quando{\ displaystyle n=3}, considera qualsiasi assegnazione a distanza{\ displaystyle \ delta}sui bordi{\displaystyle K_{3}}. Nota che se{\ displaystyle \ delta}non obbedisce alla disuguaglianza triangolare , quindi questa DCS non ha una realizzazione in nessuna dimensione. Senza perdere la generalità, posizionare il primo vertice{\displaystyle v_{1}}all’origine e al secondo vertice{\displaystyle v_{2}}lungo l’asse x tale che{\displaystyle \delta {12}}è soddisfatto. Il terzo vertice{\displaystyle v{3}}può essere posizionato all’intersezione dei cerchi con i centri{\displaystyle v_{1}}e{\displaystyle v_{2}}e raggi{\displaystyle \delta {13}}e{\displaystyle \delta _{23}}rispettivamente. Questo metodo di posizionamento è chiamato costruzione di righello e compasso . Quindi,{\displaystyle K{3}}è 2-appiattibile.

Ora, supponiamo un albero 2 con{\ displaystyle k}vertici è 2-appiattibile. Per definizione, un 2-albero con{\ displaystyle k+1}vertici è un albero a 2 con{\ displaystyle k}vertici, diciamo{\ displaystyle T}, e un vertice aggiuntivo{\ displaystyle u}connesso ai vertici di un bordo esistente in{\ displaystyle T}. Per l’ipotesi induttiva,{\ displaystyle T}è 2-appiattibile. Infine, con un argomento simile alla costruzione di righello e compasso come nel caso base,{\ displaystyle u}può essere posizionato in modo tale che si trovi nel piano. Pertanto, 2-alberi sono 2-appiattibili per induzione.

Se un grafico{\ displaystyle G}non è un albero 2 parziale, quindi contiene{\displaystyle K_{4}}come minorenne. Assegnazione della distanza di{\ displaystyle 1}ai bordi del{\displaystyle K_{4}}minore e la distanza di{\ displaystyle 0}a tutti gli altri bordi si ottiene una DCS con una realizzazione in 3 dimensioni come l’1-scheletro di un tetraedro. Tuttavia, questa DCS non ha realizzazione in 2 dimensioni: quando si tenta di posizionare il quarto vertice usando un righello una costruzione a compasso, i tre cerchi definiti dal quarto vertice non si intersecano tutti.

Esempio. Considera il grafico in figura 2. Sommando il bordo{\displaystyle {\bar {AC}}}lo trasforma in un 2-albero; quindi, è un 2 albero parziale. Pertanto, è 2-appiattibile.

Esempio. Il grafico della ruota {\displaystyle W_{5}}contiene{\displaystyle K_{4}}come minorenne. Pertanto, non è 2-appiattibile.

-Grafici appiattibili

La classe di{\ displaystyle 3}-i grafici appiattibili contengono rigorosamente la classe di parziale{\ displaystyle 3}-alberi. Più precisamente, i minorenni vietati per parziali{\ displaystyle 3}-alberi sono il grafico completo{\displaystyle K_{5}}, lo scheletro 1 dell’ottaedro{\displaystyle K_{2,2,2}},{\displaystyle V_{8}}, e{\displaystyle C_{5}\times C_{2}}, ma{\displaystyle V_{8}}, e{\displaystyle C_{5}\times C_{2}}sono{\ displaystyle 3}-appiattibile. Questi grafici sono mostrati in Figura 3. Inoltre, il seguente teorema di mostra che gli unici minorenni vietati per{\ displaystyle 3}-appiattibilità sono{\displaystyle K_{5}}e{\displaystyle K_{2,2,2}}.

Figura 3. I grafici di interesse per{\ displaystyle 3}-appiattibilità.
Figura 3. I grafici di interesse per{\ displaystyle 3}-appiattibilità.

Teorema. Un grafico è{\ displaystyle 3}-appiattibile se e solo se non ha{\displaystyle K_{5}}o{\displaystyle K_{2,2,2}}come minorenne.

Idea di prova: la dimostrazione data in presuppone che{\displaystyle V_{8}}, e{\displaystyle C_{5}\times C_{2}}sono{\ displaystyle 3}-realizzabile. Ciò è dimostrato in utilizzando strumenti matematici della teoria della rigidità, in particolare quelli riguardanti le tensegrità. Il grafico completo{\displaystyle K_{5}}non è{\ displaystyle 3}-appiattibile, e lo stesso argomento che mostra{\displaystyle K_{4}}non è{\ displaystyle 2}-appiattibile e{\displaystyle K_{3}}non è{\ displaystyle 1}-l’appiattibile funziona qui: assegnazione della distanza{\ displaystyle 1}ai bordi di{\displaystyle K_{5}}produce una DCS senza realizzazione in{\ displaystyle 3}-dimensioni. La figura 4 fornisce una prova visiva che il grafico{\displaystyle K_{2,2,2}}non è{\ displaystyle 3}-appiattibile. Vertici{\ displaystyle 1},{\ displaystyle 2}, e{\ displaystyle 3}formare un triangolo degenerato. Per gli spigoli tra i vertici{\ displaystyle 1}{\ displaystyle 5}, bordi{\ displaystyle (1,4)}e{\ displaystyle (3,4)}viene assegnata la distanza{\displaystyle {\sqrt {2}}}e a tutti gli altri bordi viene assegnata la distanza{\ displaystyle 1}. Vertici{\ displaystyle 1}{\ displaystyle 5}avere posizionamenti unici in{\ displaystyle 3}-dimensioni, fino a congruenza. Vertice{\ displaystyle 6}ha{\ displaystyle 2}possibili collocamenti in{\ displaystyle 3}-dimensioni:{\ displaystyle 1}su ciascun lato dell’aereo{\ displaystyle \ Pi}definito da vertici{\ displaystyle 1},{\ displaystyle 2}, e{\ displaystyle 4}. Quindi, il bordo{\ displaystyle (5,6)}ha due valori di distanza che possono essere realizzati in{\ displaystyle 3}-dimensioni. Tuttavia, vertice{\ displaystyle 6}può ruotare attorno all’aereo{\ displaystyle \ Pi}in{\ displaystyle 4}-dimensioni soddisfacendo tutti i vincoli, quindi il bordo{\ displaystyle (5,6)}ha infiniti valori di distanza che possono essere realizzati solo in{\ displaystyle 4}-dimensioni o superiori. Così,{\displaystyle K_{2,2,2}}non è{\ displaystyle 3}-appiattibile. Il fatto che questi grafici non lo siano{\ displaystyle 3}-flattenable dimostra che qualsiasi grafico con entrambi{\displaystyle K_{5}}o{\displaystyle K_{2,2,2}}come un minore non lo è{\ displaystyle 3}-appiattibile.

Figura 4. Fasi di costruzione per mostrare il{\ displaystyle 1}-scheletro di un ottaedro non lo è{\ displaystyle 3}-appiattibile .
Figura 4. Fasi di costruzione per mostrare il{\ displaystyle 1}-scheletro di un ottaedro non lo è{\ displaystyle 3}-appiattibile .

L’altra direzione mostra che se un grafico{\ displaystyle G}non ha{\displaystyle K_{5}}o{\displaystyle K_{2,2,2}}da minorenne, quindi{\ displaystyle G}può essere costruito da parziale{\ displaystyle 3}-alberi,{\displaystyle V_{8}}, e{\displaystyle C_{5}\times C_{2}}tramite [[Somma-clique}|{\ displaystyle 1}-somme]],{\ displaystyle 2}-somme, e{\ displaystyle 3}-somme. Questi grafici sono tutti{\ displaystyle 3}-appiattibile e queste operazioni preservano{\ displaystyle 3}-appiattibilità, quindi{\ displaystyle G}è{\ displaystyle 3}-appiattibile.

Le tecniche in questa dimostrazione producono il seguente risultato da.

Teorema. Ogni 3-realizzabile grafico è un sottografo di un grafico che può essere ottenuto da una sequenza di{\ displaystyle 1}-somme,{\ displaystyle 2}-somme, e{\ displaystyle 3}-somme dei grafici{\displaystyle K_{4}},{\displaystyle V_{8}}, e{\displaystyle C_{5}\times C_{2}}.

Esempio. Il teorema precedente può essere applicato per dimostrare che il{\ displaystyle 1}-Lo scheletro di un cubo è 3-appiattibile. Inizia con il grafico{\displaystyle K_{4}}, che è lo scheletro 1 di un tetraedro. Su ciascuna faccia del tetraedro, esegui una somma 3 con un’altra{\displaystyle K_{4}}grafico, cioè incollare due tetraedri insieme sulle loro facce. Il grafico risultante contiene il cubo come sottografo ed è 3-appiattibile.

Flattenability in dimensioni superiori

Dare una caratterizzazione minore proibita di{\ displaystyle d}-grafici appiattibili, per dimensione{\displaystyle d>3}, è un problema aperto. Per qualsiasi dimensione{\ displaystyle d},{\displaystyle K_{d+2}}e l’1-scheletro del{\ displaystyle d}-l’analogo dimensionale di un ottaedro è vietato ai minori{\ displaystyle d}-appiattibilità. Si ipotizza che il numero di minorenni vietati per{\ displaystyle d}-l’appiattibilità cresce asintoticamente al numero dei minori interdetti per parziale{\ displaystyle d}-alberi, e ci sono finiti{\ displaystyle 75}minorenni vietati per parziale{\ displaystyle 4}-alberi.

Una caratterizzazione alternativa di{\ displaystyle d}-i grafici appiattibili collegano l’appiattibilità agli spazi di configurazione di Cayley. Vedere la sezione Collegamento agli spazi di configurazione Cayley .

Collegamento al problema di realizzazione del grafico

Dati un sistema di vincoli di distanza e una dimensione{\ displaystyle d}, il Problema di realizzazione del grafico richiede a{\ displaystyle d}quadro dimensionale del DCS, se esistente. Ci sono algoritmi da realizzare{\ displaystyle d}-grafici appiattibili in{\ displaystyle d}-dimensioni, per{\ displaystyle d \ leq 3}, che corrono in tempo polinomiale nella dimensione del grafico. Per{\displaystyle d=1}, realizzando ogni albero in una foresta in{\ displaystyle 1}-dimensione è banale da realizzare in tempo polinomiale. Un algoritmo per{\displaystyle d=2}è menzionato in. Per{\displaystyle d=3}, l’algoritmo in ottiene un framework{\ displaystyle r}di un DCS utilizzando tecniche di programmazione semidefinita e quindi utilizza il metodo “folding” descritto in per trasformare{\ displaystyle r}in un{\ displaystyle 3}-struttura dimensionale.

Flattenability in p -norme

Questa sezione riguarda i risultati di appiattibilità per i grafici in generale{\ displaystyle p}
-norme , per{\ displaystyle 1 \ leq p \ leq \ infty}.

Collegamento alla geometria algebrica

Determinazione dell’appiattibilità di un grafo sotto un generale{\ displaystyle p}-norm può essere ottenuto usando metodi in geometria algebrica , come suggerito in La questione se un grafo{\ displaystyle G = (V, E)}è{\ displaystyle d}-flattenable equivale a determinare se due insiemi semialgebrici sono uguali. Prende un algoritmo per confrontare due insiemi semialgebrici{\displaystyle (4|E|)^{O\sinistra(nd|V|^{2}\destra)}}tempo.

Collegamento agli spazi di configurazione Cayley

Per il generale{\displaystyle l_{p}}-norme, esiste una stretta relazione tra l’appiattibilità e gli spazi di configurazione di Cayley . si trovano il seguente teorema e il suo corollario.

Teorema. Un grafico{\ displaystyle G}è{\ displaystyle d}-appiattibile se e solo se per ogni sottografo{\ displaystyle H = G \ setmeno F}di{\ displaystyle G}risultante dalla rimozione di una serie di bordi{\ displaystyle F}a partire dal{\ displaystyle G}e qualsiasi{\displaystyle l_{p}^{p}}-distanza vettore{\displaystyle \delta _{H}}tale che il DCS{\displaystyle (H,\delta _{H})}ha una realizzazione, il{\ displaystyle d}-dimensionale spazio di configurazione di Cayley di{\displaystyle (H,\delta _{H})}terminato{\ displaystyle F}è convesso.

Corollario. Un grafico{\ displaystyle G}non è{\ displaystyle d}-appiattibile se esiste qualche sottografo{\ displaystyle H = G \ setmeno F}di{\ displaystyle G}e alcuni{\displaystyle l_{p}^{p}}-distanza vettore{\ displaystyle \ delta}tale che il{\ displaystyle d}-dimensionale spazio di configurazione di Cayley di{\displaystyle (H,\delta _{H})}terminato{\ displaystyle F}non è convesso.

-Appiattibilità ai sensi del e norme

Il{\displaystyle l_{1}}e{\displaystyle l_{\infty}}le norme sono equivalenti fino ad assi rotanti in{\ displaystyle 2}-dimensioni, così{\ displaystyle 2}-i risultati di appiattibilità per entrambe le norme valgono per entrambi. Questa sezione utilizza il{\displaystyle l_{1}}-norma. Il grafico completo{\displaystyle K_{4}}è{\ displaystyle 2}-appiattibile sotto il{\displaystyle l_{1}}-norma e{\displaystyle K_{5}}è{\ displaystyle 3}-appiattibile, ma non{\ displaystyle 2}-appiattibile. Questi fatti contribuiscono ai seguenti risultati su{\ displaystyle 2}-appiattibilità ai sensi del{\displaystyle l_{1}}-norma trovata in.

Osservazione. L’insieme di{\ displaystyle 2}-grafici appiattibili sotto il{\displaystyle l_{1}}-norma (e{\displaystyle l_{\infty}}-norma) contiene rigorosamente l’insieme di{\ displaystyle 2}-grafici appiattibili sotto il{\displaystyle l_{2}}-norma.

Teorema. A{\ displaystyle 2}-somma di{\ displaystyle 2}-grafici appiattibili è{\ displaystyle 2}-appiattibile se e solo se al massimo un grafo ha a{\displaystyle K_{4}}minore.

Il fatto che{\displaystyle K_{4}}è{\ displaystyle 2}-appiattibile ma{\displaystyle K_{5}}non ha implicazioni sulla caratterizzazione minore proibita per{\ displaystyle 2}-grafici appiattibili sotto il{\displaystyle l_{1}}-norma. Nello specifico, i minori di{\displaystyle K_{5}}potrebbe essere vietato ai minori{\ displaystyle 2}-appiattibilità. I seguenti risultati esplorano queste possibilità e forniscono l’insieme completo dei minori proibiti.

Teorema. Il grafico della banana, o{\displaystyle K_{5}}con un bordo rimosso, non lo è{\ displaystyle 2}-appiattibile.

Osservazione. Il grafico ottenuto rimuovendo due archi incidenti allo stesso vertice da{\displaystyle K_{5}}è{\ displaystyle 2}-appiattibile.

Osservazione. Grafici collegati accesi{\ displaystyle 5}vertici con{\ displaystyle 7}i bordi sono{\ displaystyle 2}-appiattibile.

L’unico minore di{\displaystyle K_{5}}a sinistra è il grafico della ruota{\displaystyle W_{5}}, e il risultato seguente mostra che questo è uno dei minori proibiti.

Teorema. Un grafico è{\ displaystyle 2}-appiattibile sotto il{\displaystyle l_{1}}– o{\displaystyle l_{\infty}}-norma se e solo se non ha nessuno dei seguenti grafici come minori:

  • il grafico della ruota{\displaystyle W_{5}}o
  • il grafico ottenuto prendendo il{\ displaystyle 2}-somma di due copie di{\displaystyle K_{4}}e rimuovendo il bordo condiviso.

Collegamento alla rigidità strutturale

Questa sezione mette in relazione l’appiattibilità con concetti nella teoria della rigidità strutturale (combinatoria) , come il matroide della rigidità . I seguenti risultati riguardano il{\displaystyle l_{p}^{p}}-cono di distanza{\displaystyle \Phi {n,l{p}}}, cioè l’insieme di tutti{\displaystyle l_{p}^{p}}– vettori di distanza realizzabili come configurazione di{\ displaystyle n}punti in una certa dimensione. Una prova che questo insieme è un cono può essere trovata in. Il{\ displaystyle d}-strato di questo cono{\displaystyle \Phi {n,l{p}}^{d}}sono i vettori realizzabili come configurazione di{\ displaystyle n}punti dentro{\ displaystyle d}-dimensioni. La proiezione di{\displaystyle \Phi {n,l{p}}}o{\displaystyle \Phi {n,l{p}}^{d}}sui bordi di un grafico{\ displaystyle G}è l’insieme di{\displaystyle l_{p}^{p}}vettori di distanza che possono essere realizzati come le lunghezze dei bordi di alcuni incorporamenti di{\ displaystyle G}.

Una proprietà generica di un grafico{\ displaystyle G}è uno che quasi tutti i quadri dei sistemi di vincoli di distanza, il cui grafico è{\ displaystyle G}, avere. Un quadro di un DCS{\ displaystyle (G, \ delta )}sotto un{\displaystyle l_{p}}-norm è un framework generico (rispetto a{\ displaystyle d}-appiattibilità) se ricorrono le due seguenti condizioni:

  1. c’è un quartiere aperto{\ displaystyle \ Omega}di{\ displaystyle \ delta}all’interno del cono{\displaystyle \Phi _{n,l_{p}}}, e
  2. il quadro è{\ displaystyle d}-appiattibile se e solo se tutti i framework sono in{\ displaystyle \ Omega}sono{\ displaystyle d}-appiattibile.

La condizione (1) garantisce che il vicinato{\ displaystyle \ Omega}ha il rango pieno. In altre parole,{\ displaystyle \ Omega}ha dimensione uguale alla dimensione di appiattimento del grafico completo{\displaystyle K_{n}}sotto il{\displaystyle l_{p}}-norma. Si veda per una discussione più dettagliata del quadro generico per{\displaystyle l_{p}}-norme. I seguenti risultati si trovano in.

Teorema. Un grafico{\ displaystyle G}è{\ displaystyle d}-appiattibile se e solo se ogni quadro generico di{\ displaystyle G}è{\ displaystyle d}-appiattibile.

Teorema. {\ displaystyle d}-l’appiattibilità non è una proprietà generica dei grafi, anche per il{\displaystyle l_{2}}-norma.

Teorema. Un generico{\ displaystyle d}-struttura appiattibile di un grafo{\ displaystyle G}esiste se e solo se{\ displaystyle G}è indipendente nel generico{\ displaystyle d}matroide di rigidità dimensionale.

Corollario. Un grafico{\ displaystyle G}è{\ displaystyle d}-appiattibile solo se{\ displaystyle G}è indipendente nel{\ displaystyle d}matroide di rigidità dimensionale.

Teorema. Per il generale{\displaystyle l_{p}}-norme, un grafico{\ displaystyle G}è

  1. indipendente nel generico{\ displaystyle d}-matroide di rigidità dimensionale se e solo se la proiezione del{\ displaystyle d}-strato{\displaystyle \Phi _{n,l_{p}}^{d}}sui bordi di{\ displaystyle G}ha dimensione uguale al numero di spigoli di{\ displaystyle G};
  2. massimamente indipendente nel generico{\ displaystyle d}-matroide di rigidità dimensionale se e solo se proiettante il{\ displaystyle d}-strato{\displaystyle \Phi _{n,l_{p}}^{d}}sui bordi di{\ displaystyle G}conserva la sua dimensione e questa dimensione è uguale al numero di bordi di{\ displaystyle G};
  3. rigido dentro{\ displaystyle d}-dimensioni se e solo se si proietta il{\ displaystyle d}-strato{\displaystyle \Phi _{n,l_{p}}^{d}}sui bordi di{\ displaystyle G}conserva la sua dimensione;
  4. non indipendente nel generico{\ displaystyle d}-matroide di rigidità dimensionale se e solo se la dimensione della proiezione del{\ displaystyle d}-strato{\displaystyle \Phi _{n,l_{p}}^{d}}sui bordi di{\ displaystyle G}è rigorosamente inferiore al minimo della dimensione di{\displaystyle \Phi _{n,l_{p}}^{d}}e il numero di bordi di{\ displaystyle G}.

[ad_2] Da Wikipedia, l’enciclopedia libera
Source link

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: