Izomorfismul grafic

În teoria grafurilor, un izomorfism de graf este o bijecție între seturi de vârfuri de grafuri , astfel încât oricare două vârfuri și graficul sunt adiacente dacă și numai dacă vârfurile și sunt adiacente în grafic . Aici, graficele sunt înțelese a fi nedirecționate și neavând greutăți de vârf și margini. Dacă conceptul de izomorfism este aplicat graficelor direcționate sau ponderate, se impun restricții suplimentare privind păstrarea orientării arcului și a valorilor de greutate. Dacă se stabilește izomorfismul graficelor, acestea se numesc izomorfe și se notează ca . $G=\stanga\langle V_{G},E_{G}\dreapta\rangle$ $H=\stanga\langule V_{H},E_{H}\dreapta\rangle$ $f\colon\V_{G}\rightarrow V_{H}$ $u$ $v$ $G$ $f(u)$ $f(v)$ $H$ $G\simeq H$

Uneori, o bijecție este scrisă ca o substituție de izomorfism . Unele probleme de procesare a graficelor necesită nu numai verificarea izomorfismului, ci și găsirea substituției acestuia. $f$ ${\begin{pmatrix}a_{1}&a_{2}&\dots &a_{n}\\f(a_{1})&f(a_{2})&\dots &f(a_{n})\end{ pmatrix}}$

Relația de izomorfism grafic este o relație de echivalență definită pentru grafice și permite ca clasa originală a tuturor graficelor să fie împărțită în clase de echivalență . Setul de grafice izomorfe unul față de celălalt se numește clasa de izomorfism grafic , numărul lor în funcție de succesiunea A000088 în OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, .. .) . $n$

Dacă bijecția mapează graficul pe el însuși (graficele și coincid), se numește automorfism de grafic . $f$ $G$ $H$ $G$

Există, de asemenea, probleme înrudite în teoria grafurilor, cum ar fi găsirea unui subgraf izomorf și găsirea unui subgraf izomorf comun maxim , care aparțin clasei de NP-complet . În ramurile conexe ale matematicii, există probleme similare, de exemplu, izomorfismul planurilor proiective și izomorfismul grupurilor finite , care sunt polinomial reductibile la problema izomorfismului de graf (posibilitatea reducției polinomiale inverse nu a fost dovedită în cazul general). ) [1] .

Exemplu

Cele două grafice prezentate în exemplu sunt izomorfe.

Grafic $G$	Grafic $H$	Izomorfismul dintre grafice și $G$ $H$	Substituția izomorfismului $f$
		$f(a)=1$ $f(b)=6$ $f(c)=8$ $f(d)=3$ $f(g)=5$ $f(h)=2$ $f(i)=4$ $f(j)=7$	${\begin{pmatrix}a&b&c&d&g&h&i&j\\1&6&8&3&5&2&4&7\end{pmatrix}}$

Izomorfism general al graficului

Grafice si sunt izomorfe daca prin permutarea randurilor si coloanelor matricei de adiacenta a graficului se poate obtine matricea de adiacenta a graficului . Cu toate acestea, enumerarea tuturor permutărilor posibile este caracterizată de complexitate computațională (cu condiția ca matricele de adiacență să fie comparate într-un timp independent de , ceea ce este de obicei incorect și în plus crește estimarea de mai sus), ceea ce limitează semnificativ aplicarea acestei abordări în practică. Există metode pentru enumerarea limitată a posibilelor perechi de vârfuri presupus izomorfe (analoage metodei ramificației și legate ), dar îmbunătățesc ușor asimptoticele de mai sus [2] . $G$ $H$ $G$ $H$ $PE!)$ $N$

Teorema lui Whitney

Teorema izomorfismului grafului lui Whitney [3] [4] , formulată de Hassler Whitney în 1932 , afirmă că două grafuri conectate sunt izomorfe dacă și numai dacă grafurile lor liniare sunt izomorfe, cu excepția grafurilor (un graf complet de 3 vârfuri) și a unui bipartit complet. graph , care nu sunt izomorfe, dar ambele au un graf ca graf cu linii. Teorema lui Whitney poate fi generalizată la hipergrafe [5] . $K_{3}$ $K_{{1,3}}$ $K_{3}$

Invarianți

Există un set de caracteristici numerice ale graficelor, numite invarianți , care coincid pentru graficele izomorfe (coincidența invarianților este o condiție necesară dar nu suficientă pentru izomorfism) [6] . Acestea includ numărul de vârfuri și numărul de arce/margini ale graficului G , vectorul de grade de vârfuri ordonate în ordine crescătoare sau descrescătoare, vectorul valorilor proprii ale matricei de adiacență a graficului (spectrul graficului) ordonat crescător sau ordinea descrescătoare, numărul cromatic etc. Faptul că invarianții coincid de obicei nu conține informații despre substituția izomorfismului. $n(G)$ $m(G)$ $s(G)=(\rho (v_{1}),\rho (v_{2}),\dots ,\rho (v_{n}))$ $\chi (G)$

Se spune că un invariant este complet dacă coincidența invarianților graficului este necesară și suficientă pentru a stabili un izomorfism. De exemplu, fiecare dintre valorile și (mini- și maxi-codul matricei de adiacență) este un invariant complet pentru un grafic cu un număr fix de vârfuri . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Invarianții diferiți au complexitate de calcul diferită. În prezent, un invariant grafic complet calculat în timp polinomial este necunoscut, dar nu s-a dovedit că nu există. Încercările de a-l găsi au fost făcute în mod repetat în anii 60 - 80 ai secolului XX , dar nu au avut succes.

Produs Modular Weesing

Produsul modular al grafurilor , propus de V. G. Vizing , ne permite să reducem problema verificării izomorfismului la problema determinării densității unui graf care conține vârfuri. Dacă , , atunci graficul conține un subgraf izomorf cu graficul . $Y=G\pastilă H$ $\varphi (Y)$ $n(G)\cdot n(H)$ $\varphi (Y)=n(G)$ $n(G)\leq n(H)$ $H$ $G$

Izomorfismul graficelor de o formă specială

Complexitate computațională

Deși problema izomorfismului de graf aparține clasei NP , nu se știe dacă este NP-complet sau aparține clasei P (presupunând P ≠ NP ). Mai mult, problema găsirii unui subgraf izomorf într-un graf este NP-complet . Cercetarea modernă are ca scop dezvoltarea algoritmilor rapizi pentru rezolvarea atât a problemei generale a izomorfismului graficelor arbitrare, cât și a graficelor de tip special.

Aplicații

În practică, necesitatea verificării izomorfismului graficelor apare la rezolvarea problemelor de chimioinformatică , chimie matematică (calculatoare) [7] , automatizarea proiectării circuitelor electronice (verificarea diferitelor reprezentări ale unui circuit electronic ) [2] , optimizarea programului (identificarea subexpresiilor comune).

Vezi și

Link -uri

Problema izomorfismului grafic _ _

Note

↑ Ponomarenko I. N. Problema izomorfismului grafului: aspecte algoritmice (note pentru prelegeri) Copie de arhivă din 22 iunie 2018 la Wayback Machine
↑ 1 2 Kureichik V. M., Glushan V. M., Shcherbakov L. I. Modele hardware combinatorii și algoritmi în CAD. - M . : Radio şi comunicare, 1990. - 216 p.
↑ H. Whitney. Grafice congruente și conectivitatea graficelor // Am. J. Matematică .. - 1932. - T. 54 . - S. 160-168 . - doi : 10.2307/2371086 .
↑ Harari F. Teoria grafurilor . - M . : Mir , 1973. (Ed. 3, M .: KomKniga, 2006. - 296 p.)
↑ Dirk L. Vertigan, Geoffrey P. Whittle. O teoremă cu 2 izomorfisme pentru hipergrafe // J. Comb. Teorie, Ser. B. - 1997. - T. 71 , nr. 2 . - S. 215-230 . - doi : 10.1006/jctb.1997.1789 .
↑ Zykov A. A. . Fundamentele teoriei grafurilor. — M .: Nauka, 1986. — 384 p. - ISBN 978-5-9502-0057-1 .
↑ Trofimov M. I., Smolensky E. A. Aplicarea indicilor de electronegativitate ai moleculelor organice în probleme de informatică chimică // Izvestiya a Academiei de Științe. Seria chimică. - 2005. - S. 2166-2176 .