Grafisk isomorfi

I grafteori er en grafisomorfi en bijektion mellem sæt af toppunkter af grafer , således at alle to toppunkter og grafen er tilstødende, hvis og kun hvis toppunkterne og er tilstødende i grafen . Her forstås grafer som urettede og uden top- og kantvægte. Hvis begrebet isomorfi anvendes på rettede eller vægtede grafer, pålægges der yderligere begrænsninger for bevarelsen af bueorientering og vægtværdier. Hvis grafernes isomorfi er etableret, kaldes de isomorfe og betegnes som . $G=\venstre\langle V_{G},E_{G}\right\rangle$ $H=\venstre\langle V_{H},E_{H}\højre\rangle$ $f\colon\V_{G}\rightarrow V_{H}$ $u$ $v$ $G$ $f(u)$ $f(v)$ $H$ $G\simeq H$

Nogle gange skrives en bijektion som en isomorfisubstitution . Nogle grafbehandlingsproblemer kræver ikke kun at kontrollere isomorfi, men også at finde ud af dens substitution. $f$ ${\begin{pmatrix}a_{1}&a_{2}&\dots &a_{n}\\f(a_{1})&f(a_{2})&\dots &f(a_{n})\end{ pmatrix}}$

Grafisomorfi-relationen er en ækvivalensrelation, der er defineret for grafer og tillader, at den oprindelige klasse af alle grafer kan opdeles i ækvivalensklasser . Sættet af grafer, der er isomorfe i forhold til hinanden, kaldes grafisk isomorfisme-klassen , deres antal afhængigt af er sekvensen A000088 i OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, . .). $n$

Hvis bijektionen kortlægger grafen på sig selv (graferne og falder sammen), kaldes det en grafautomorfi . $f$ $G$ $H$ $G$

Der er også relaterede problemer i grafteori, såsom at finde en isomorf subgraf og finde en maksimal almindelig isomorf subgraf , som tilhører klassen af NP-komplet . I beslægtede grene af matematik er der lignende problemer, for eksempel isomorfien af projektive planer og isomorfien af endelige grupper , som er polynomisk reducerbare til grafisomorfiproblemet (muligheden for invers polynomiel reducerbarhed er ikke blevet bevist i det generelle tilfælde ) [1] .

Eksempel

De to grafer, der er givet i eksemplet, er isomorfe.

Kurve $G$	Kurve $H$	Isomorfi mellem grafer og $G$ $H$	Isomorfi substitution $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}}$

Generel grafisomorfi

Grafer og er isomorfe, hvis det ved at permutere rækkerne og kolonnerne i grafens tilstødende matrix er muligt at opnå grafens tilstødende matrix . Imidlertid er opregningen af alle mulige permutationer karakteriseret ved beregningsmæssig kompleksitet (forudsat at tilstødende matricer sammenlignes i en tid uafhængig af , hvilket normalt er uretfærdigt og yderligere øger ovenstående estimat), hvilket væsentligt begrænser anvendelsen af denne tilgang i praksis. Der er metoder til begrænset opregning af mulige par af formodet isomorfe hjørner (analog med branch and bound-metoden ), men de forbedrer en smule ovenstående asymptotik [2] . $G$ $H$ $G$ $H$ $PÅ!)$ $N$

Whitneys teorem

Whitneys grafiske isomorfismesætning [3] [4] , formuleret af Hassler Whitney i 1932 , siger, at to forbundne grafer er isomorfe, hvis og kun hvis deres linjegrafer er isomorfe, bortset fra grafer (en komplet graf med 3 hjørner) og en komplet todelt graf , som ikke er isomorfe, men begge har en graf som en linjegraf. Whitneys sætning kan generaliseres til hypergrafer [5] . $K_{3}$ $K_{{1,3}}$ $K_{3}$

Invarianter

Der er et sæt numeriske karakteristika af grafer, kaldet invarianter , som falder sammen for isomorfe grafer (sammenfald af invarianter er en nødvendig, men ikke tilstrækkelig betingelse for isomorfi) [6] . Disse inkluderer antallet af toppunkter og antallet af buer/kanter af grafen G , vektoren af grader af toppunkter ordnet i stigende eller faldende rækkefølge, vektoren af egenværdier af grafens tilstødende matrix (grafspektret) ordnet i stigende eller faldende rækkefølge. faldende rækkefølge, det kromatiske tal osv. Det faktum, at invarianter falder sammen, indeholder normalt ikke information om isomorfisubstitution. $n(G)$ $m(G)$ $s(G)=(\rho (v_{1}),\rho (v_{2}),\dots ,\rho (v_{n}))$ $\chi (G)$

En invariant siges at være komplet , hvis sammenfaldet af grafinvarianter er nødvendig og tilstrækkelig til at etablere en isomorfi. For eksempel er hver af værdierne og (mini- og maxikoden for tilstødende matrix) en fuldstændig invariant for en graf med et fast antal hjørner . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Forskellige invarianter har forskellig beregningsmæssig kompleksitet. I øjeblikket er en komplet grafinvariant, der kan beregnes i polynomiel tid, ukendt, men det er ikke blevet bevist, at den ikke eksisterer. Forsøg på at finde det blev gentagne gange gjort i 60'erne - 80'erne af det XX århundrede , men var mislykkede.

Modulært Weesing-produkt

Det modulære produkt af grafer , foreslået af V. G. Vizing , giver os mulighed for at reducere problemet med at kontrollere isomorfi til problemet med at bestemme tætheden af en graf, der indeholder hjørner. Hvis , , så indeholder grafen en undergraf, der er isomorf i forhold til grafen . $Y=G\pastill H$ $\varphi (Y)$ $n(G)\cdot n(H)$ $\varphi (Y)=n(G)$ $n(G)\leq n(H)$ $H$ $G$

Isomorfi af grafer af en speciel form

Beregningsmæssig kompleksitet

Selvom grafisomorfiproblemet hører til NP-klassen , vides det ikke, om det er NP-komplet eller tilhører P-klassen (forudsat at P ≠ NP ). Desuden er problemet med at finde en isomorf subgraf i en graf NP-komplet . Moderne forskning er rettet mod at udvikle hurtige algoritmer til løsning af både det generelle problem med isomorfi af vilkårlige grafer og grafer af en speciel type.

Ansøgninger

I praksis opstår behovet for at kontrollere grafernes isomorfi ved løsning af problemer inden for kemoinformatik , matematisk (computer) kemi [7] , automatisering af design af elektroniske kredsløb (verifikation af forskellige repræsentationer af et elektronisk kredsløb ) [2] , programoptimering (identifikation af almindelige underudtryk).

Se også

Invariant (matematik)
åbne matematiske problemer
Problemet med at finde en isomorf subgraf
maksimale almindelige isomorfe subgraf

Noter

↑ Ponomarenko I. N. Problemet med grafisomorfi: algoritmiske aspekter (noter til forelæsninger) Arkiveksemplar af 22. juni 2018 på Wayback Machine
↑ 1 2 Kureichik V. M., Glushan V. M., Shcherbakov L. I. Kombinatoriske hardwaremodeller og algoritmer i CAD. - M . : Radio og kommunikation, 1990. - 216 s.
↑ H. Whitney. Overensstemmende grafer og tilslutningsmuligheder af grafer // Am. J. Math .. - 1932. - T. 54 . - S. 160-168 . - doi : 10.2307/2371086 .
↑ Harari F. Grafteori . - M . : Mir , 1973. (Red. 3, M .: KomKniga, 2006. - 296 s.)
↑ Dirk L. Vertigan, Geoffrey P. Whittle. En 2-isomorfismesætning for hypergrafer // J. Comb. Teori, Ser. B. - 1997. - T. 71 , no. 2 . - S. 215-230 . - doi : 10.1006/jctb.1997.1789 .
↑ Zykov A. A. . Grundlæggende om grafteori. — M .: Nauka, 1986. — 384 s. - ISBN 978-5-9502-0057-1 .
↑ Trofimov M. I., Smolensky E. A. Anvendelse af elektronegativitetsindekser for organiske molekyler i problemer med kemisk informatik // Izvestiya fra Videnskabernes Akademi. Kemisk serie. - 2005. - S. 2166-2176 .