Izomorfism de grafuri

În teoria grafurilor, un izomorfism al grafurilor G și H este o bijecție între mulțimile de noduri ale lui G și H

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

cu proprietatea că oricare două noduri u și v ale lui G sunt adiacente în G dacă și numai dacă $f(u)$ și $f(v)$ sunt adiacente în H. Acest tip de bijecție este adeseori descris ca „bijecție care păstrează muchiile”, în conformitate cu faptul că noțiunea generală de izomorfism este o bijecție care păstrează structura.

Dacă există un izomorfism între două grafuri, atunci grafurile se numesc izomorfe și se notează $G\simeq H$ . În cazul în care izomorfismul este o aplicație de la un graf la el însuși, adică atunci când G și H sunt unul și același graf, izomorfismul se numește automorfism al lui G.

Izomorfismul de grafuri formează o relație de echivalență pe mulțimea grafurilor și ca atare parționează clasa tuturor grafurilor în clase de echivalență. O mulțime de grafuri izomorfe între ele se numește clasă de izomorfism de grafuri. Întrebarea dacă izomorfismul grafului poate fi determinat în timp polinomial este o problemă majoră nerezolvată în informatică, cunoscută sub denumirea de problema izomorfismului grafurilor.^[1]^[2]

Cele două grafuri prezentate mai jos sunt izomorfe, în ciuda aspectului diferit al desenelor.

Graful G	Graful H	Un izomorfism între G și 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

Variații

În definiția de mai sus, prin graf se înțelege un graf neorientat, neetichetat și neponderat. Totuși, noțiunea de izomorfism poate fi aplicată tuturor celorlalte variante ale noțiunii de graf prin adăugarea condițiilor de păstrare a elementelor suplimentare de structură corespunzătoare: direcțiile arcelor, ponderile muchiilor etc., cu următoarea excepție.

Izomorfismul grafurilor etichetate

Pentru grafurile etichetate sunt în uz două definiții ale izomorfismului.

Conform unei definiții, un izomorfism este o bijecție a nodurilor care păstrează atât muchiile, cât și etichetele.^[3]^[4]

Conform altei definiții, un izomorfism este o bijecție a nodurilor care păstrează muchiile și clasele de echivalență de etichete, adică nodurile cu etichete echivalente (de exemplu cu etichete identice) sunt trimise surjectiv în nodurile cu etichete echivalente și vice versa; la fel cu etichetele de muchii.^[5]

De exemplu, graful $K_{2}$ cu cele două noduri etichetate cu 1 și 2 are un singur automorfism conform primei definiții, dar conform celei de-a doua definiții există două automorfisme.

A doua definiție este folosită în anumite situații când grafurile sunt dotate cu etichete unice luate de obicei din mulțimea {1,2,3,...,n}, unde n este numărul de noduri ale grafului, folosit doar pentru a identifica unic nodurile. În astfel de cazuri, se spune uneori că două grafuri etichetate sunt izomorfe dacă grafurile subiacente neetichetate corespunzătoare sunt izomorfe (în caz contrar, definiția izomorfismului ar fi trivială).

Motivația

Noțiunea formală de „izomorfism”, de exemplu de „izomorfism de grafuri”, încapsulează noțiunea informală cum că niște obiecte au „aceeași structură” dacă se ignoră distincțiile individuale ale componentelor „atomice” ale obiectelor în cauză. Ori de câte ori individualitatea componentelor „atomice” (nodurile și muchiile în cazul grafurilor) este importantă pentru reprezentarea corectă a ceea ce este modelat prin grafuri, modelul este rafinat prin impunerea unor restricții suplimentare asupra structurii și sunt utilizate alte obiecte matematice: digrafuri, grafuri etichetate, grafuri colorate, arbori cu rădăcină și așa mai departe. Relația de izomorfism poate fi de asemenea definită pentru toate aceste generalizări ale grafurilor: bijecția izomorfismului trebuie să păstreze elementele de structură care definesc tipul de obiect în cauză: arce, etichete, culorile nodurilor/muchiilor, rădăcina arborelui cu rădăcină etc.

Noțiunea de „izomorfism de grafuri” ne permite să distingem proprietățile grafurilor inerente structurilor grafurilor în sine de proprietățile asociate reprezentărilor grafurilor: desenări de grafuri, structuri de date pentru grafuri, etichetări de grafuri etc. De exemplu, dacă un graf are exact un ciclu, atunci toate grafurile din clasa sa de izomorfism au de asemenea exact un ciclu. Pe de altă parte, în cazul în care nodurile unui graf sunt (reprezentate prin) numerele întregi 1, 2,..., N, expresia

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

poate fi diferită pentru două grafuri izomorfe.

Teorema lui Whitney

Excepția de la teorema lui Whitney: aceste două grafuri nu sunt izomorfe, dar au grafurile linii izomorfe.

Teorema izomorfismului de grafuri a lui Whitney,^[6] demonstrată de Hassler Whitney, afirmă că două grafuri conexe sunt izomorfe dacă și numai dacă au grafurile linie izomorfe, cu o singură excepție: graful complet cu trei noduri K₃ și graful bipartit complet K_1,3, care nu sunt izomorfe, dar ambele au K₃ drept graf linie. Teorema lui Whitney poate fi extinsă la hipergrafuri.^[7]

Recunoașterea izomorfismului de grafuri

În timp ce izomorfismul de grafuri poate fi studiat într-o manieră matematică clasică, cum este exemplificat de teorema lui Whitney, se consideră că este o problemă de abordat prin metode algoritmice. Problema computațională a determinării dacă două grafuri finite sunt izomorfe se numește problema izomorfismului grafurilor.

Aplicațiile sale practice includ în primul rând chemoinformatica, chimia matematică (identificarea compușilor chimici) și automatizarea proiectării electronice (verificarea echivalenței diferitelor reprezentări ale proiectării unui circuit electronic).

Problema izomorfismului de grafuri este una dintre puținele probleme standard din teoria computațională a complexității ce aparține clasei NP și despre care nu se cunoaște dacă aparține uneia dintre cele bine-cunoscute (și, dacă P ≠ NP, disjuncte) submulțimi: P și NP-complet. Este una dintre cele două (din totalul de 12) probleme enumerate în Garey & Johnson (1979) a cărei complexitate rămâne nerezolvată, cealaltă fiind factorizarea numerelor întregi. Cu toate acestea, se știe că dacă problema este NP-completă, atunci ierarhia polinomială se prăbușește la un nivel finit.^[8]

În noiembrie 2015, László Babai, matematician și informatician la Universitatea din Chicago, a afirmat că a demonstrat că problema izomorfismului de grafuri este rezolvabilă în timp cvasi-polinomal.^[9]^[10] El a publicat versiuni preliminare ale acestor rezultate în lucrările Simpozionului de Teoria Computației din 2016^[11], și al Congresului Internațional al Matematicienilor din 2018.^[12] În ianuarie 2017, Babai a retras temporar afirmația legată de timpul cvasi-polinomial și a declarat în schimb o margine sub-exponentială a complexității în timp. El a restaurat afirmația inițială cinci zile mai târziu.^[13] În 2024, versiunea completă a articolului lui Babai nu a fost încă publicată.

Generalizarea sa, problema izomorfismului de subgrafuri, este cunoscută ca fiind NP-completă.

Principalele domenii de cercetare pentru problemă sunt proiectarea de algoritmi rapizi și investigările teoretice ale complexității sale computaționale, atât pentru problema generală, cât și pentru clase speciale de grafuri.

Testul de izomorfism de grafuri al lui Weisfeiler Leman poate fi folosit pentru a testa euristic izomorfismul de grafuri.^[14] În cazul în care testul este negativ, cele două grafuri de intrare sunt garantate a fi neizomorfe. Dacă testul este pozitiv, grafurile pot fi sau nu izomorfe. Există generalizări ale algoritmului de testare care garantează detectarea izomorfismelor, însă timpul lor de rulare este exponențial.

Un alt algoritm bine-cunoscut pentru izomorfismul de grafuri este algoritmul vf2, dezvoltat de Cordella și colaboratorii săi în 2001.^[15] Algoritmul vf2 este un algoritm de căutare în adâncime care încearcă să construiască un izomorfism între două grafuri în mod incremental. Acesta folosește un set de reguli de fezabilitate pentru a reduce spațiul de căutare, permițându-i să gestioneze eficient grafuri cu mii de noduri. Algoritmul vf2 a fost utilizat pe scară largă în diverse aplicații, cum ar fi recunoașterea de modele, viziunea computerizată și bioinformatica. Deși are o complexitate în timp exponențială în cel mai rău caz, funcționează bine în practică pentru multe tipuri de grafuri.

Note

^ Grohe, Martin (1 noiembrie 2020). „The Graph Isomorphism Problem”. Communications of the ACM. 63 (11): 128–134. doi:10.1145/3372123. Accesat în 6 martie 2023. Mentenanță CS1: Dată și an (link)
^ Klarreich, Erica (14 decembrie 2015). „Landmark Algorithm Breaks 30-Year Impasse”. Quanta Magazine. Accesat în 6 martie 2023.
^ p.424
^ Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). „Efficient Method to Perform Isomorphism Testing of Labeled Graphs”. Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science. 3984. pp. 422–431. doi:10.1007/11751649_46. ISBN 978-3-540-34079-9.
^ Pierre-Antoine Champin, Christine Solnon, "Measuring the Similarity of Labeled Graphs" în: Lecture Notes in Computer Science, vol. 2689, pp 80–95
^ Whitney, Hassler (ianuarie 1932). „Congruent Graphs and the Connectivity of Graphs”. American Journal of Mathematics. 54 (1): 150–168. doi:10.2307/2371086. JSTOR 2371086.
^ Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
^ Schöning, Uwe (1988). „Graph isomorphism is in the low hierarchy”. Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.
^ Cho, Adrian (10 noiembrie 2015), „Mathematician claims breakthrough in complexity theory”, Science, doi:10.1126/science.aad7416 .
^ Klarreich, Erica (14 decembrie 2015), „Landmark Algorithm Breaks 30-Year Impasse”, Quanta Magazine
^ Babai, László (2016), „Graph isomorphism in quasipolynomial time [extended abstract]”, STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, pp. 684–697, doi:10.1145/2897518.2897542, MR 3536606
^ Babai, László (2018), „Group, graphs, algorithms: the graph isomorphism problem”, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR 3966534
^ Babai, László (9 ianuarie 2017), Graph isomorphism update
^ Huang, Ningyuan Teresa; Villar, Soledad (2021). „A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants”. ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 8533–8537. doi:10.1109/ICASSP39728.2021.9413523. ISBN 978-1-7281-7605-5.
^ Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. (2001). „An Improved Algorithm for Matching Large Graphs”. 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition: 149–159.

Bibliografie

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

Vezi și

[1] Grohe, Martin (1 noiembrie 2020). „The Graph Isomorphism Problem”. Communications of the ACM. 63 (11): 128–134. doi:10.1145/3372123. Accesat în 6 martie 2023. Mentenanță CS1: Dată și an (link)

[2] Klarreich, Erica (14 decembrie 2015). „Landmark Algorithm Breaks 30-Year Impasse”. Quanta Magazine. Accesat în 6 martie 2023.

[3] .424

[4] Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). „Efficient Method to Perform Isomorphism Testing of Labeled Graphs”. Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science. 3984. pp. 422–431. doi:10.1007/11751649_46. ISBN 978-3-540-34079-9.

[5] Pierre-Antoine Champin, Christine Solnon, "Measuring the Similarity of Labeled Graphs" în: Lecture Notes in Computer Science, vol. 2689, pp 80–95

[6] Whitney, Hassler (ianuarie 1932). „Congruent Graphs and the Connectivity of Graphs”. American Journal of Mathematics. 54 (1): 150–168. doi:10.2307/2371086. JSTOR 2371086.

[7] Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.

[8] Schöning, Uwe (1988). „Graph isomorphism is in the low hierarchy”. Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.

[9] Cho, Adrian (10 noiembrie 2015), „Mathematician claims breakthrough in complexity theory”, Science, doi:10.1126/science.aad7416 .

[10] Klarreich, Erica (14 decembrie 2015), „Landmark Algorithm Breaks 30-Year Impasse”, Quanta Magazine

[11] Babai, László (2016), „Graph isomorphism in quasipolynomial time [extended abstract]”, STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, pp. 684–697, doi:10.1145/2897518.2897542, MR 3536606

[12] Babai, László (2018), „Group, graphs, algorithms: the graph isomorphism problem”, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR 3966534

[13] Babai, László (9 ianuarie 2017), Graph isomorphism update

[14] Huang, Ningyuan Teresa; Villar, Soledad (2021). „A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants”. ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 8533–8537. doi:10.1109/ICASSP39728.2021.9413523. ISBN 978-1-7281-7605-5.

[15] Cordella, L. P.; Foggia, P.; Sansone, C.; Vento, M. (2001). „An Improved Algorithm for Matching Large Graphs”. 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition: 149–159.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]