isomorfismo del grafico - Graph isomorphism

Nella teoria dei grafi , un isomorfismo dei grafi G e H è una biiezione tra gli insiemi di vertici di G e H

${\displaystyle f\due punti V(G)\a V(H)}$

tale che due vertici qualsiasi u e v di G sono adiacenti in G se e solo se e sono adiacenti in H . Questo tipo di biiezione è comunemente descritto come "biezione che preserva i bordi", in accordo con la nozione generale di isomorfismo come biiezione che preserva la struttura. ${\displaystyle f(u)}$${\displaystyle f(v)}$

Se esiste un isomorfismo tra due grafici, allora i grafici sono chiamati isomorfi e indicati come . Nel caso in cui la biiezione sia una mappatura di un grafo su se stesso, cioè quando G e H sono uno e lo stesso grafo, la biiezione è detta automorfismo di G . ${\displaystyle G\simeq H}$

L'isomorfismo dei grafi è una relazione di equivalenza sui grafi e come tale suddivide la classe di tutti i grafi in classi di equivalenza . Un insieme di grafi isomorfi tra loro è chiamato classe di isomorfismo di grafi.

I due grafici mostrati di seguito sono isomorfi, nonostante i loro disegni dall'aspetto diverso .

Grafico G	Grafico H	Un isomorfismo tra G e H
		f ( a ) = 1 f ( b ) = 6 f ( c ) = 8 f ( d ) = 3 f ( g ) = 5 f ( h ) = 2 f ( io ) = 4 f ( j ) = 7

Variazioni

Nella definizione di cui sopra, i grafici sono intesi come grafici non pesati non etichettati unidirezionali . Tuttavia, la nozione di isomorfo può essere applicata a tutte le altre varianti della nozione di grafo, aggiungendo i requisiti per preservare i corrispondenti elementi aggiuntivi della struttura: direzioni degli archi, pesi degli spigoli, ecc., con la seguente eccezione.

Isomorfismo di grafici etichettati

Per i grafici etichettati , sono in uso due definizioni di isomorfismo.

Secondo una definizione, un isomorfismo è una biiezione di vertice che preserva sia il bordo che l'etichetta.

Sotto un'altra definizione, un isomorfismo è una biiezione dei vertici che preserva gli archi che conserva le classi di equivalenza delle etichette, cioè i vertici con etichette equivalenti (ad esempio, le stesse) sono mappati sui vertici con etichette equivalenti e viceversa; lo stesso con le etichette sui bordi.

Ad esempio, il grafo con i due vertici etichettati con 1 e 2 ha un singolo automorfismo sotto la prima definizione, ma sotto la seconda definizione ci sono due automorfismi. ${\displaystyle K_{2}}$

La seconda definizione viene assunta in determinate situazioni quando i grafi sono dotati di etichette univoche comunemente prese dall'intervallo di interi 1,..., n , dove n è il numero dei vertici del grafo, utilizzato solo per identificare in modo univoco i vertici. In tali casi due grafi etichettati sono talvolta detti isomorfi se i corrispondenti grafi non etichettati sottostanti sono isomorfi (altrimenti la definizione di isomorfismo sarebbe banale).

Motivazione

La nozione formale di "isomorfismo", ad esempio, di "isomorfismo grafico", cattura la nozione informale che alcuni oggetti hanno "la stessa struttura" se si ignorano le distinzioni individuali dei componenti "atomici" degli oggetti in questione. Ogni volta che l'individualità dei componenti "atomici" (vertici e bordi, per i grafici) è importante per la corretta rappresentazione di ciò che è modellato dai grafici, il modello viene affinato imponendo ulteriori restrizioni alla struttura e vengono utilizzati altri oggetti matematici: digrafi , grafici etichettati , grafici colorati , alberi radicati e così via. La relazione di isomorfismo può essere definita anche per tutte queste generalizzazioni di grafi: la biiezione di isomorfismo deve preservare gli elementi di struttura che definiscono il tipo di oggetto in questione: archi , etichette, colori vertice/bordo, radice dell'albero radicato, ecc.

La nozione di "isomorfismo dei grafi" permette di distinguere le proprietà dei grafi inerenti alle strutture dei grafi stessi dalle proprietà associate alle rappresentazioni dei grafi : disegni di grafi , strutture dati per grafi , etichettature di grafi , ecc. Ad esempio, se un grafo ha esattamente un ciclo , allora anche tutti i grafi nella sua classe di isomorfismo hanno esattamente un ciclo. D'altra parte, nel caso comune in cui i vertici di un grafo sono ( rappresentati da) gli interi 1, 2,... N , allora l'espressione

${\displaystyle \sum _{v\in V(G)}v\cdot {\text{gradi}}v}$

può essere diverso per due grafi isomorfi.

teorema di Whitney

L'eccezione del teorema di Whitney: questi due grafici non sono isomorfi ma hanno grafici a linee isomorfi.

Il teorema di isomorfismo dei grafi di Whitney , mostrato da Hassler Whitney , afferma che due grafi connessi sono isomorfi se e solo se i loro grafi lineari sono isomorfi, con un'unica eccezione: K ₃ , il grafo completo su tre vertici e il grafo bipartito completo K _{1 ,3} , che non sono isomorfi ma hanno entrambi K ₃ come grafico a linee. Il teorema del grafo di Whitney può essere esteso agli ipergrafi .

Riconoscimento dell'isomorfismo del grafo

Mentre l'isomorfismo dei grafi può essere studiato in modo matematico classico, come esemplificato dal teorema di Whitney, si riconosce che è un problema da affrontare con un approccio algoritmico. Il problema computazionale di determinare se due grafi finiti sono isomorfi è chiamato problema dell'isomorfismo dei grafi.

Le sue applicazioni pratiche includono principalmente la chemininformatica , la chimica matematica (identificazione di composti chimici) e l'automazione della progettazione elettronica (verifica dell'equivalenza di varie rappresentazioni della progettazione di un circuito elettronico ).

Il problema dell'isomorfismo dei grafi è uno dei pochi problemi standard nella teoria della complessità computazionale appartenente a NP , ma non noto per appartenere a nessuno dei suoi sottoinsiemi ben noti (e, se P ≠ NP , disgiunti): P e NP-completo . È uno dei soli due, su 12 totali, problemi elencati in Garey & Johnson (1979) la cui complessità rimane irrisolta, l'altro è la fattorizzazione di interi . È comunque noto che se il problema è NP-completo allora la gerarchia polinomiale collassa a un livello finito.

Nel novembre 2015, László Babai , un matematico e informatico dell'Università di Chicago, ha affermato di aver dimostrato che il problema dell'isomorfismo dei grafi è risolvibile in tempo quasi-polinomiale . Ha pubblicato versioni preliminari di questi risultati negli atti del Symposium on Theory of Computing 2016 e del International Congress of Mathematicians 2018 . Nel gennaio 2017, Babai ha brevemente ritrattato l'affermazione di quasi-polinomialità e ha dichiarato invece un limite di complessità temporale sub-esponenziale . Ha ripristinato la richiesta originale cinque giorni dopo. A partire dal 2020, la versione completa del giornale di Babai non è stata ancora pubblicata.

La sua generalizzazione, il problema dell'isomorfismo del sottografo , è noto per essere NP-completo.

Le principali aree di ricerca per il problema sono la progettazione di algoritmi veloci e indagini teoriche della sua complessità computazionale , sia per il problema generale che per classi speciali di grafi.

Guarda anche

• Omomorfismo grafico
• Problema di automorfismo del grafico
• Problema di isomorfismo del grafico
• Canonizzazione del grafico

Appunti

Riferimenti

• Garey, Michael R. ; Johnson, David S. (1979), Computer e intrattabilità: una guida alla teoria della completezza NP , W. H. Freeman , ISBN 0-7167-1045-5