Grafisomorfism

I grafteorin är en isomorfism av graferna G och H en bijektion mellan vertexuppsättningarna av G och H

f\colon V(G)\to V(H)

så att godtyckliga två hörn u och v i G är intilliggande i G om och endast om $f(u)$ och $f(v)$ är intilliggande i H . Denna typ av bijektion beskrivs vanligen som "kantbevarande bijektion", i enlighet med den allmänna uppfattningen att isomorfism är en strukturbevarande bijektion. Om det finns en isomorfism mellan två grafer, kallas graferna isomorfa och betecknas som $G\simeq H$ . I det fall då bijektionen är en avbildning av en graf på sig själv, dvs när G och H är en och samma graf, kallas bijektionen en automorfism av G . Om en graf är ändlig kan vi bevisa att den är bijektiv genom att visa att den är en-en/på; du behöver inte visa båda. Grafisomorfism är en ekvivalensrelation på grafer och som sådan delar den upp klassen för alla grafer i ekvivalensklasser . En uppsättning grafer som är isomorfa i förhållande till varandra kallas en isomorfismklass av grafer. Frågan om grafisomorfism kan bestämmas i polynomtid är ett stort olöst problem inom datavetenskap.

De två graferna som visas nedan är isomorfa, trots att de ser olika ut .

Graf 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 oriktade icke-märkta icke-vägda grafer. Begreppet isomorf kan dock tillämpas på alla andra varianter av begreppet graf, genom att lägga till kraven för att bevara motsvarande ytterligare strukturelement: 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 vertexbijektion som är både kantbevarande och etikettbevarande.

Enligt en annan definition är en isomorfism en kantbevarande vertexbijektion som bevarar ekvivalensklasser av etiketter, dvs. hörn med ekvivalenta (t.ex. samma) etiketter mappas till hörnen med ekvivalenta etiketter och vice versa; samma sak med kantetiketter.

Till exempel har $K_{2}$ -grafen med de två hörnen 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 vanligtvis tas från heltalsintervallet 1,..., n , där n är numret på grafens hörn, som endast används för att unikt identifiera hörnen. I sådana fall sägs ibland två märkta grafer vara isomorfa om de motsvarande underliggande omärkta graferna är isomorfa (annars skulle definitionen av isomorfism vara trivial).

Motivering

Det formella begreppet "isomorfism", t.ex. om "grafisomorfism", fångar den informella föreställningen att vissa objekt har "samma struktur" om man bortser från individuella distinktioner av "atomära" komponenter av objekten i fråga. Närhelst individualitet hos "atomära" komponenter (spetsar och kanter, för grafer) är viktig för korrekt representation av vad som helst som modelleras av grafer, förfinas modellen genom att införa ytterligare restriktioner för strukturen, och andra matematiska objekt används: digrafer , märkta grafer , färgade grafer , rotade träd och så vidare. Isomorfismrelationen kan också definieras för alla dessa generaliseringar av grafer: isomorfismbijektionen måste bevara de strukturelement som definierar objekttypen i fråga: bågar , etiketter, vertex-/kantfärger, roten av det rotade trädet, etc.

Begreppet "grafisomorfism" tillåter oss att skilja grafegenskaper som är inneboende i själva grafernas strukturer från egenskaper som är associerade med grafrepresentationer: grafritningar , datastrukturer för grafer , grafetiketter , etc. Om en graf till exempel har exakt en cykel , då har alla grafer i dess isomorfismklass också exakt en cykel. Å andra sidan, i det vanliga fallet när toppen av en graf är ( representerade av) heltal 1, 2,... N , då uttrycket

\sum _{v\in V(G)}v\cdot {\text{deg }}v

kan vara olika för två isomorfa grafer.

Whitneys sats

Undantaget från Whitneys teorem: dessa två grafer är inte isomorfa utan har isomorfa linjediagram.

Whitney -grafens isomorfismsats , visad av Hassler Whitney , säger att två sammankopplade grafer är isomorfa om och endast om deras linjegrafer är isomorfa, med ett enda undantag: K ₃ , den fullständiga grafen på tre hörn, och den fullständiga tvådelade grafen K _{1 ,3} , som inte är isomorfa men båda har K ₃ som linjediagram. Whitneys grafsats kan utvidgas till hypergrafer .

Igenkänning av grafisomorfism

Medan grafisomorfism kan studeras på ett klassiskt matematiskt sätt, vilket exemplifieras av Whitneys sats, är det känt att det är ett problem att hantera med ett algoritmiskt tillvägagångssätt. Beräkningsproblemet att avgöra om två finita grafer är isomorfa kallas grafisomorfismproblemet.

Dess praktiska tillämpningar inkluderar främst kemiformatik , matematisk kemi (identifiering av kemiska föreningar) och elektronisk designautomation (verifiering av likvärdighet av olika representationer av designen av en elektronisk krets ).

Grafisomorfismproblemet är ett av få standardproblem inom beräkningskomplexitetsteori som tillhör NP , men som inte är känt för att tillhöra någon av dess välkända (och, om P ≠ NP , disjunkta) delmängder: P och NP-komplett . Det är ett av endast två, av totalt 12, problem listade i Garey & Johnson (1979) vars komplexitet förblir olöst, det andra är heltalsfaktorisering . Det är dock känt att om problemet är NP-komplett så polynomhierarkin till en ändlig nivå.

I november 2015 hävdade László Babai , en matematiker och datavetare vid University of Chicago, att han har bevisat att problemet med grafisomorfism är lösbart i kvasi-polynomisk tid . Han publicerade preliminära versioner av dessa resultat i 2016 års Symposium on Theory of Computing och 2018 års internationella matematikkongress . I januari 2017 drog Babai kort tillbaka påståendet om kvasipolynomialitet och angav istället en subexponentiell tidskomplexitetsbunden . Han återställde det ursprungliga anspråket fem dagar senare. Från och med 2020 har den fullständiga tidskriftsversionen av Babais papper ännu inte publicerats.

Dess generalisering, subgraph isomorphism problem , är känd för att vara NP-komplett.

De huvudsakliga forskningsområdena för problemet är design 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.

Se även

Anteckningar

Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5