Graf invariant

En grafinvariant i grafteori er en normalt numerisk værdi eller et ordnet sæt værdier ( hash-funktion ) , hvilket karakteriserer grafens struktur og ikke afhænger af metoden til markering af hjørnerne eller grafisk gengivelse af grafen . Det spiller en vigtig rolle i at kontrollere grafernes isomorfi , såvel som i computerkemiproblemer . $G=\langle A,V\rangle$

Eksempler på invarianter

Grafinvarianter inkluderer:

Grafens diameter er længden af den korteste vej (afstand) mellem parret af de fjerneste hjørner. $\mathrm {diam} (G)$
Invariant af Colin de Verdière .
Wienerindekset er værdien , hvor er minimumsafstanden mellem hjørnerne og . $w=\sum _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i},v_{j})$ $v_{i}$ $v_{j}$
Det randiske indeks er værdien . $r=\sum _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) ) }}$
Hosoya-indekset er antallet af kantmatchninger i grafen plus én.
Mini- og maxi-kode for tilstødende matrix, opnået ved at skrive de binære værdier af tilstødende matrix ud i en linje, efterfulgt af at konvertere det resulterende binære tal til decimalform. Mini-kode svarer til en sådan rækkefølge af rækker og kolonner, hvor den resulterende værdi er den mindst mulige; maxi-kode - henholdsvis maksimum. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
Det mindste antal hjørner, der skal fjernes for at opnå en afbrudt graf .
Det mindste antal kanter, der skal fjernes for at opnå en afbrudt graf.
Det mindste antal hjørner, der er nødvendige for at dække kanter.
Det mindste antal kanter, der er nødvendige for at dække hjørnerne.
Ikke-densiteten af en graf er antallet af hjørner af en maksimal (med hensyn til inklusion) kantløs undergraf (det største antal parvise ikke-tilstødende hjørner). Det er nemt at se det og . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
Omkredsen af grafen er antallet af kanter i minimumscyklussen.
Adjacency matrix determinant .
Densiteten af grafen er antallet af hjørner med den maksimale inklusionsklike . $\varphi (G)$
En stigende eller faldende vektor af toppunktsgrader — når der bruges optællingsalgoritmer til at bestemme grafisomorfi, vælges toppunkter med sammenfaldende grader som angiveligt isomorfe toppunkter, hvilket hjælper med at reducere kompleksiteten af opregning. Brugen af denne invariant til k-homogene grafer reducerer ikke beregningskompleksiteten ved opregning, da graderne af alle hjørner af en sådan graf er de samme: . $s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))$ $s(G)=(k,k,\prikker,k)$
En stigende eller faldende vektor af egenværdier af en grafs tilstødende matrix (grafspektrum). Den tilstødende matrix i sig selv er ikke en invariant, da når nummereringen af knudepunkter ændres, gennemgår den en permutation af rækker og kolonner.
Antal hjørner og antal buer/kanter . $n(G)=|A|$ $m(G)=|V|$
Antallet af forbundne komponenter i grafen . $\kappa (G)$
Hadwiger nummer . $\eta (G)$
Det karakteristiske polynomium af tilstødende matrix.
Kromatisk tal . $\chi (G)$

Som en invariant kan man ikke betragte et af ovenstående tal, men deres tupel (superindeks) af formen , som igen kan associeres med et polynomium af formen $(p_{0},p_{1},p_{2},\dots )$

P(x)=\sum _{{i\geq 0}}p_{i}x^{i}=p_{0}+p_{1}x+p_{2}x^{2}+\dots,

summering udføres op til den sidste ikke-nul værdi . På lignende måde kan flere grafinvarianter introduceres: $p_{i}$

$D(G)=\sum _{{i=0}}^{n}d_{i}(G)x^{i}=d_{0}(G)+d_{1}(G)x+d_ {2}(G)x^{2}+\dots +d_{n}(G)x^{n}$ , hvor er antallet af hjørner af grad i; $grave)$
$E(G)=\sum _{{i=0}}^{{\epsilon (G)}}e_{i}(G)x^{i}=e_{0}(G)+e_{1} (G)x+e_{2}(G)x^{2}+\dots +e_{{\epsilon }}(G)x^{{\epsilon }}$ , hvor er antallet af kantløse i-vertex subgrafer; $e_{i}(G)$
$F(G)=\sum _{{i=0}}^{{\varphi (G)))f_{i}(G)x^{i}=f_{0}(G)+f_{1} (G)x+f_{2}(G)x^{2}+\dots +f_{{\varphi }}(G)x^{{\varphi }}$ , hvor er antallet af komplette i-vertex subgrafer (i-kliker); $f_{i}(G)$
$H(G)=\sum _{{i=1}}^{{\eta (G)))h_{i}(G)x^{i}=h_{1}(G)x+h_{2 }(G)x^{2}+\dots +h_{{\eta }}(G)x^{{\eta }}$ , hvor er antallet af forskellige sammentrækninger af den forbundne graf pr. klike; $h_{i}(G)$ $G$
$K(G)=\sum _{{i=1}}^{n}k_{i}(G)x^{i}=k_{1}(G)x+k_{2}(G)x^ {2}+\dots +k_{n}(G)x^{n}$ , hvor er antallet af tilsluttede komponenter fra i hjørner; $k_{i}(G)$
$Y(G)=\sum _{{i=\chi (G)}}^{n}y_{i}(G)x^{i}=y_{{\chi }}(G)x^{{ \chi }}+y_{{\chi +1}}(G)x^{{\chi +1}}+\dots +y_{n}(G)x^{n}$ , hvor er antallet af i-farvninger af grafen (korrekte farver med nøjagtig i-farver). $y_{i}(G)$

Systemer af grafinvarianter afhængigt af to eller flere parametre kan skrives som polynomier i flere formelle variable. For eksempel: $x,y,z,\prikker$

$A(G)=\sum _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , hvor er antallet af undergrafer i grafen , der har spidser og kanter; $\alpha _{{ij}}(G)$ $G$ $jeg$ $j$
$B(G)=\sum _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , hvor er antallet af i-vertex subgrafer, for hvilke antallet af nåle (kanter, der forbinder subgrafens toppunkter med resten af grafens toppunkter) er lig med ; $\beta _{{ik}}(G)$ $k$
$S(G)=\sum _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , hvor er antallet af i-vertex subgrafer med kanter og nåle (generalisering af invarianter og ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polynomial Tatta .

Sammenfaldet af invarianter er en nødvendig, men ikke tilstrækkelig betingelse for tilstedeværelsen af en isomorfi [1]

Komplet invariant

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 en fuldstændig invariant for en graf med et fast antal hjørner . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Kompleksiteten af beregningen

Invarianterne adskiller sig i kompleksiteten af beregningen. Invarianterne , , og beregnes trivielt, mens beregningen af invarianterne , , , , , og de afhængige af dem kan være temmelig beregningsmæssigt vanskelig . Der er probabilistiske algoritmer til at bestemme værdierne af de givne "svære at beregne" invarianter, men brugen af sådanne algoritmer er ikke altid tilladt. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

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.

Ansøgninger i computerkemi

Mange invarianter ( topologiske indekser ) bruges i computerkemi til at løse en lang række generelle og specielle problemer [2] . Disse opgaver omfatter: søgning efter stoffer med forudbestemte egenskaber (søgning efter "struktur-egenskab", "struktur-farmakologisk aktivitet" type afhængigheder), primær filtrering af strukturel information til ikke-gentagen generering af molekylære grafer af en given type, og en række andre. Ofte bruges der sammen med topologiske indekser (kun afhængig af molekylets struktur) information om forbindelsens kemiske sammensætning [3] .

Se også

Noter

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov Fundamentals of Graph Theory]. — M .: Nauka, 1986. — 384 s. - ISBN 978-5-9502-0057-1 .
↑ Kemiske anvendelser af topologi og grafteori = Kemiske anvendelser af topologi og grafteori / Ed. R. Konge. — M .: Mir, 1987. — 560 s.
↑ M. I. Trofimov, E. A. Smolensky, Proceedings of the Academy of Sciences. Chemical series , 2005, s. 2166-2176.