Graf isomorfism - Graph isomorphism
I grafteorin är en isomorfism av graferna G och H en sammanhängning mellan toppuppsättningarna G och H
så att varje två hörn u och v av G är intilliggande i G om och endast om och är angränsande i H . Denna typ av bindning beskrivs vanligen som "kantbevarande bindning", i enlighet med den allmänna uppfattningen att isomorfism är en strukturbevarande bindning.
Om det finns en isomorfism mellan två grafer kallas graferna isomorf och betecknas som . I det fall när bijektion är en mappning av en graf på sig själv, dvs när G och H är ett och samma graf, är bijektion kallas en automorfism av G .
Grafisomorfism är en ekvivalensrelation på grafer och delar som sådan klassen för alla grafer i ekvivalensklasser . En uppsättning diagram isomorfa till varandra kallas en isomorfismklass av grafer.
De två diagrammen nedan är isomorfa, trots deras olika letar ritningar .
| Diagram G | Diagram H | En isomorfism mellan G och H. |
|---|---|---|
|
|
f ( a ) = 1
f ( b ) = 6 f ( c ) = 8 f ( d ) = 3 f ( g ) = 5 f ( h ) = 2 f ( i ) = 4 f ( j ) = 7 |
Variationer
I ovanstående definition förstås grafer som enriktade icke-märkta icke-viktade grafer. Begreppet isomorf kan emellertid tillämpas på alla andra varianter av begreppet graf genom att lägga till kraven för att bevara motsvarande ytterligare element av struktur: bågriktningar, kantvikter etc. med följande undantag.
Isomorfism av märkta grafer
För märkta grafer används två definitioner av isomorfism.
Enligt en definition är en isomorfism en vertexbindning som är både kantbevarande och etikettbevarande.
Under en annan definition är en isomorfism en kantbevarande vertex-bindning som bevarar ekvivalensklasser av etiketter, dvs. vertikaler med ekvivalenta (t.ex. samma) etiketter mappas på topparna med ekvivalenta etiketter och vice versa; samma med kantetiketter.
Till exempel har diagrammet med de två hörn som är märkta med 1 och 2 en enda automorfism under den första definitionen, men under den andra definitionen finns det två automorfismer.
Den andra definitionen antas i vissa situationer när grafer är utrustade med unika etiketter som vanligen tas från heltalsområdet 1, ..., n , där n är antalet kurvor i grafen, som endast används för att identifiera topparna. I sådana fall sägs ibland två märkta grafer vara isomorfa om motsvarande underliggande omärkta grafer är isomorfa (annars skulle definitionen av isomorfism vara trivial).
Motivering
Det formella begreppet "isomorfism", t.ex. "grafisomorfism", fångar den informella uppfattningen att vissa objekt har "samma struktur" om man ignorerar individuella skillnader mellan "atomiska" komponenter i föremål i fråga. Närhelst individualitet "atomära" komponenter (hörn och kanter, för grafer) är viktigt för korrekt representation av det som modelleras av grafer, har modellen förfinas genom att införa ytterligare begränsningar på strukturen, och andra matematiska objekt används: digraphs , märkta grafer , färgade grafer , rotade träd och så vidare. Isomorfismrelationen kan också definieras för alla dessa generaliseringar av grafer: isomorfismens sammanhang måste bevara strukturelementen som definierar objekttypen i fråga: bågar , etiketter, topp- / kantfärger, roten till det rotade trädet etc.
Begreppet "grafisomorfism" gör det möjligt för oss att skilja grafegenskaper som är inneboende i själva kurvorna från egenskaper som är associerade med grafrepresentationer: grafritningar , datastrukturer för grafer , grafetiketter etc. Till exempel om en graf har exakt en cykel , då har alla grafer i dess isomorfismklass också exakt en cykel. Å andra sidan, i det vanliga fallet när kurvorna i en graf är ( representerade av) heltal 1, 2, ... N , då uttrycket
kan vara annorlunda för två isomorfa grafer.
Whitney-satsen
Den Whitney graf isomorfism teorem , som visas av Hassler Whitney , anges att två anslutna grafer är isomorfa om och endast om deras linjediagram är isomorfa, med ett enda undantag: K 3 , den fullständiga grafen på tre hörn, och komplett bipartit graf K 1 , 3 , som inte är isomorfa men båda har K 3 som sin linjegraf. Whitney-grafsatsen kan utvidgas till hypergrafer .
Erkännande av grafisomorfism
Medan grafisomorfism kan studeras på ett klassiskt matematiskt sätt, vilket exemplifieras av Whitney-satsen, är det erkänt att det är ett problem att tackla med en algoritmisk metod. Beräkningsproblemet med att bestämma om två ändliga grafer är isomorfa kallas grafisomorfismproblemet.
Dess praktiska tillämpningar innefattar främst keminformatik , matematisk kemi (identifiering av kemiska föreningar) och elektronisk designautomation (verifiering av ekvivalens hos olika representationer av designen av en elektronisk krets ).
Grafen isomorfismproblem är ett av få standardproblem i beräkningskomplexitetsteori som tillhör NP , men inte känt för att tillhöra någon av dess välkända (och, om P ≠ NP , ojämna) delmängder: P och NP-komplett . Det är ett av endast två, av 12 totalt, problem som listas i Garey & Johnson (1979) vars komplexitet förblir olöst, den andra är heltalsfaktorisering . Det är dock känt att om problemet är NP-komplett då polynomet hierarkin kollapsar till en ändlig nivå.
I november 2015 hävdade László Babai , en matematiker och datavetare vid University of Chicago, att ha bevisat att grafen isomorfism är löst på kvasipolynomisk tid . Han publicerade preliminära versioner av dessa resultat i förfarandena för 2016 Symposium on Theory of Computing , och 2018 års internationella kongress för matematiker . I januari 2017 återkallade Babai kortfattat kravet på kvasipolynomitet och angav en subexponentiell tidskomplexitet istället. Han återställde det ursprungliga fordran fem dagar senare. Från och med 2020 har den fullständiga journalversionen av Babais tidning ännu inte publicerats.
Dess generalisering, subgrafens isomorfismproblem , är känd för att vara NP-komplett.
De viktigaste forskningsområdena för problemet är utformningen av snabba algoritmer och teoretiska undersökningar av dess beräkningskomplexitet , både för det allmänna problemet och för speciella klasser av grafer.