Graf invariant

En grafinvariant i grafteori är ett vanligtvis numeriskt värde eller en ordnad uppsättning värden ( hashfunktion ) , vilket kännetecknar grafens struktur och inte beror på metoden för att markera hörnen eller grafisk representation av grafen . Det spelar en viktig roll för att kontrollera grafernas isomorfism , såväl som i datorkemiproblem . $G=\langle A,V\rangle$

Exempel på invarianter

Grafinvarianter inkluderar:

Diametern på grafen är längden på den kortaste vägen (avståndet) mellan paret av de mest avlägsna hörnen. $\mathrm {diam} (G)$
Invariant av Colin de Verdière .
Wienerindexet är värdet , där är det minsta avståndet mellan hörnen och . $w=\sum _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i},v_{j})$ $v_{i}$ $v_{j}$
Randic index är värdet . $r=\summa _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) ) }}$
Hosoya-indexet är antalet kantmatchningar i grafen plus en.
Mini- och maxkod för närliggande matris, erhållen genom att skriva ut de binära värdena för närliggande matris på en rad, följt av att konvertera det resulterande binära talet till decimalform. Minikod motsvarar en sådan ordning av rader och kolumner, där det resulterande värdet är det minsta möjliga; maxi-kod - respektive maximum. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
Det minsta antalet hörn som måste tas bort för att få en frånkopplad graf .
Det minsta antalet kanter som måste tas bort för att få en frånkopplad graf.
Det minsta antalet hörn som behövs för att täcka kanter.
Det minsta antalet kanter som behövs för att täcka topparna.
Otätheten för en graf är antalet hörn av en maximal (med avseende på inkludering) kantlös subgraf (det största antalet parvisa icke-angränsande hörn). Det är lätt att se det och . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
Grafens omkrets är antalet kanter i den minsta cykeln.
Adjacensmatrisdeterminant . _
Grafens densitet är antalet hörn med den maximala inkluderingsklicken . $\varphi (G)$
En stigande eller fallande vektor av vertexgrader — när man använder uppräkningsalgoritmer för att bestämma grafisomorfism, väljs hörn med sammanfallande grader som förment isomorfa hörnpar, vilket hjälper till att minska komplexiteten i uppräkningen. Användningen av denna invariant för k-homogena grafer minskar inte beräkningskomplexiteten för uppräkning, eftersom graderna för alla hörn i en sådan graf är desamma: . $s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))$ $s(G)=(k,k,\prickar,k)$
En stigande eller fallande vektor av egenvärden för en grafs närliggande matris (grafspektrum). Själva närliggande matrisen är inte en invariant, eftersom när numreringen av hörn ändras, genomgår den en permutation av rader och kolumner.
Antal hörn och antal bågar/kanter . $n(G)=|A|$ $m(G)=|V|$
Antalet anslutna komponenter i grafen . $\kappa (G)$
Hadwiger nummer . $\eta (G)$
Det karakteristiska polynomet för närliggande matris.
Kromatiskt nummer . $\chi (G)$

Som en invariant kan man betrakta inte ett av ovanstående tal, utan deras tupel (superindex) av formen , som i sin tur kan associeras med ett polynom av formen $(p_{0},p_{1},p_{2},\dots )$

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

summering utförs upp till det sista värdet som inte är noll . På liknande sätt kan flera grafinvarianter introduceras: $pi}$

$D(G)=\summa _{{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}$ , där är antalet hörn av grad i; $gräv)$
$E(G)=\summa _{{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 }}$ , där är antalet kantlösa i-vertex subgrafer; $e_{i}(G)$
$F(G)=\summa _{{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 }}$ , där är antalet kompletta i-vertex subgrafer (i-klickar); $fikon)$
$H(G)=\summa _{{i=1}}^{{\eta (G)))h_{i}(G)x^{i}=h_{1}(G)x+h_{2 }(G)x^{2}+\dots +h_{{\eta }}(G)x^{{\eta }}$ , där är antalet olika sammandragningar av den anslutna grafen per klick; $Hej g)$ $G$
$K(G)=\summa _{{i=1}}^{n}k_{i}(G)x^{i}=k_{1}(G)x+k_{2}(G)x^ {2}+\dots +k_{n}(G)x^{n}$ , där är antalet anslutna komponenter från i hörn; $k_{i}(G)$
$Y(G)=\summa _{{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}$ , där är antalet i-färgningar i grafen (korrekta färger med exakt i-färger). $y_{i}(G)$

System av grafinvarianter beroende på två eller flera parametrar kan skrivas som polynom i flera formella variabler. Till exempel: $x,y,z,\prickar$

$A(G)=\summa _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , där är antalet subgrafer i grafen som har hörn och kanter; $\alpha _{{ij}}(G)$ $G$ $i$ $j$
$B(G)=\summa _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , där är antalet i-vertex subgrafer för vilka antalet nålar (kanter som förbinder subgrafens hörn med resten av grafens hörn) är lika med ; $\beta _{{ik}}(G)$ $k$
$S(G)=\summa _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , där är antalet i-vertex subgrafer med kanter och nålar (generalisering av invarianter och ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polynom Tatta .

Sammankomsten av invarianter är ett nödvändigt men inte tillräckligt villkor för närvaron av en isomorfism [1]

Komplett invariant

En invariant sägs vara komplett om sammanträffandet av grafinvarianter är nödvändig och tillräcklig för att etablera en isomorfism. Till exempel är vart och ett av värdena och en fullständig invariant för en graf med ett fast antal hörn . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Komplexiteten i beräkningen

Invarianterna skiljer sig åt i beräkningens komplexitet. Invarianterna , , och beräknas trivialt, medan beräkningen av invarianterna , , , , , och de som beror på dem kan vara ganska beräkningsmässigt svårt . Det finns probabilistiska algoritmer för att bestämma värdena för de givna "svårberäknade" invarianterna, men användningen av sådana algoritmer är inte alltid tillåten. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

För närvarande är en komplett grafinvariant som kan beräknas i polynomtid okänd, men det har inte bevisats att den inte existerar. Försök att hitta det gjordes upprepade gånger på 60-80-talet av XX-talet , men misslyckades.

Tillämpningar inom datorkemi

Många invarianter ( topologiska index ) används inom datorkemi för att lösa en lång rad allmänna och speciella problem [2] . Dessa uppgifter inkluderar: sökning efter substanser med förutbestämda egenskaper (sökning efter "struktur-egenskap", "struktur-farmakologisk aktivitet" typ beroenden), primär filtrering av strukturell information för icke-repetitiv generering av molekylära grafer av en given typ, och ett antal andra. Ofta, tillsammans med topologiska index (beroende endast på molekylens struktur), används också information om föreningens kemiska sammansättning [3] .

Se även

Anteckningar

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov Fundamentals of Graph Theory]. — M .: Nauka, 1986. — 384 sid. - ISBN 978-5-9502-0057-1 .
↑ Kemiska tillämpningar av topologi och grafteori = Kemiska tillämpningar av topologi och grafteori / Ed. R. kung. — M .: Mir, 1987. — 560 sid.
↑ M. I. Trofimov, E. A. Smolensky, Proceedings of the Academy of Sciences. Chemical series , 2005, sid. 2166-2176.