Kuvaajan invariantti

Graafiinvariantti graafiteoriassa on jokin tavallisesti numeerinen arvo tai järjestys arvojen joukko ( hash-funktio ) , joka kuvaa graafin rakennetta eikä riipu graafin kärkien merkintätavasta tai graafisesta esityksestä . Sillä on tärkeä rooli graafien isomorfismin tarkistamisessa sekä tietokonekemian ongelmissa . $G=\kulma A,V\kulma$

Esimerkkejä invarianteista

Kaavion invariantteja ovat:

Kuvaajan halkaisija on lyhimmän polun (etäisyyden) pituus kaukaisimpien pisteiden parin välillä. $\mathrm {halkaisija} (G)$
Colin de Verdièren invariantti .
Wiener-indeksi on arvo , jossa on pisteiden ja pisteiden välinen vähimmäisetäisyys . $w=\sum _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i}, v_{j})$ $v_{i}$ $v_{j}$
Randic-indeksi on arvo . $r=\sum _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) ) }}$
Hosoya-indeksi on kaavion reunasovitusten lukumäärä plus yksi .
Viereisyysmatriisin mini- ja maksikoodi, joka saadaan kirjoittamalla vierekkäisyysmatriisin binaariarvot riville, jonka jälkeen tuloksena oleva binääriluku muunnetaan desimaalimuotoon. Minikoodi vastaa sellaista rivien ja sarakkeiden järjestystä, jossa tuloksena oleva arvo on pienin mahdollinen; maxi-koodi - vastaavasti maksimi. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
Huippupisteiden vähimmäismäärä, joka on poistettava, jotta saataisiin irrotettu graafi .
Reunojen vähimmäismäärä, joka on poistettava, jotta saadaan irrotettu graafi.
Reunojen peittämiseen tarvittava pisteiden vähimmäismäärä .
Reunojen vähimmäismäärä, joka tarvitaan kärkien peittämiseen.
Graafin ei-tiheys on maksimaalisen (sisällytyksen suhteen) reunattoman aligraafin (suurin määrä pareittain ei-vierekkäisiä pisteitä) kärkien lukumäärä. Se on helppo nähdä ja . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
Kuvaajan ympärysmitta on reunojen lukumäärä minimijaksossa.
Vierekkäisyysmatriisin determinantti .
Graafin tiheys on niiden kärkien lukumäärä, joilla on suurin inkluusioklikki . $\varphi (G)$
Huippuasteiden nouseva tai laskeva vektori — käytettäessä laskenta-algoritmeja graafin isomorfismin määrittämiseen, pisteet, joilla on yhtenevät asteet, valitaan oletettavasti isomorfisiksi pistepareiksi, mikä auttaa vähentämään laskennan monimutkaisuutta. Tämän invariantin käyttö k-homogeenisille graafille ei vähennä laskennan monimutkaisuutta, koska tällaisen graafin kaikkien kärkien asteet ovat samat: . $s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))$ $s(G)=(k,k,\pisteet,k)$
Graafin vierekkäisyysmatriisin (kuvaajaspektri) ominaisarvojen nouseva tai laskeva vektori . Viereisyysmatriisi itsessään ei ole invariantti, koska kun kärkien numerointi muuttuu, se käy läpi rivien ja sarakkeiden permutaatiota.
Huippupisteiden lukumäärä ja kaarien/reunojen määrä . $n(G)=|A|$ $m(G)=|V|$
Kuvaajan yhdistettyjen komponenttien lukumäärä . $\kappa (G)$
Hadwigerin numero . $\eta (G)$
Viereisyysmatriisin ominaispolynomi .
Kromaattinen numero . $\chi (G)$

Invariantina ei voida pitää yhtä yllä olevista luvuista, vaan niiden monikkoa ( superindeksiä ) muodossa , joka puolestaan voidaan liittää muodon polynomiin $(p_{0},p_{1},p_{2},\pisteet )$

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

summaus suoritetaan viimeiseen nollasta poikkeavaan arvoon asti . Samalla tavalla voidaan ottaa käyttöön useita muita graafiinvariantteja: $p_{i}$

$D(G)=\summa _{{i=0}}^{n}d_{i}(G)x^{i}=d_{0}(G)+d_{1}(G)x+d_ {2}(G)x^{2}+\pisteet +d_{n}(G)x^{n}$ , missä on i-asteen kärkien lukumäärä; $kaivaa)$
$E(G)=\summa _{{i=0}}^{{\epsilon (G)}}e_{i}(G)x^{i}=e_{0}(G)+e_{1} (G)x+e_{2}(G)x^{2}+\pisteet +e_{{\epsilon }}(G)x^{{\epsilon }}$ , missä on reunattomien i-vertex-aligraafien lukumäärä; $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}+\pisteet +f_{{\varphi }}(G)x^{{\varphi }}$ , missä on täydellisten i-vertex-aligraafien (i-klikkien) lukumäärä; $kuva)$
$H(G)=\summa _{{i=1}}^{{\eta (G)))h_{i}(G)x^{i}=h_{1}(G)x+h_{2 }(G)x^{2}+\pisteet +h_{{\eta }}(G)x^{{\eta }}$ , missä on yhdistetyn graafin eri supistusten lukumäärä i-klikkiä kohti; $h_{i}(G)$ $G$
$K(G)=\summa _{{i=1}}^{n}k_{i}(G)x^{i}=k_{1}(G)x+k_{2}(G)x^ {2}+\pisteet +k_{n}(G)x^{n}$ , missä on i-pisteistä yhdistettyjen komponenttien lukumäärä; $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}}+\pisteet +y_{n}(G)x^{n}$ , missä on kaavion i-väritysten lukumäärä (oikeat värit täsmälleen i-väreillä). $y_{i}(G)$

Kahdesta tai useammasta parametrista riippuvia graafiinvarianttien järjestelmiä voidaan kirjoittaa polynomeina useisiin muodollisiin muuttujiin. Esimerkiksi: $x,y,z,\pisteet$

$A(G)=\summa _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , missä on niiden graafin aligraafien lukumäärä, joilla on kärkipisteitä ja kulmia; $\alpha _{{ij}}(G)$ $G$ $i$ $j$
$B(G)=\summa _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , missä on niiden i-vertex-aligraafien lukumäärä, joille neulojen määrä (reunat, jotka yhdistävät osagraafin kärjet muihin graafin kärkipisteisiin) on yhtä suuri kuin ; $\beta _{{ik}}(G)$ $k$
$S(G)=\summa _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , missä on i-vertex-alagraafien määrä reunoilla ja neuloilla (invarianttien yleistys ja ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polynomi tatta .

Invarianttien yhteensattuma on välttämätön , mutta ei riittävä ehto isomorfismin esiintymiselle [1]

Täydellinen invariantti

Invariantin sanotaan olevan täydellinen , jos graafiinvarianttien yhteensattuma on välttämätön ja riittävä isomorfismin muodostamiseksi. Esimerkiksi jokainen arvoista ja on täydellinen invariantti graafille, jossa on kiinteä määrä pisteitä . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Laskennan monimutkaisuus

Invariantit eroavat laskennan monimutkaisuudesta. Invariantit , , ja lasketaan triviaalisti, kun taas invarianttien , , , , ja niistä riippuvien laskeminen voi olla laskennallisesti melko vaikeaa . On olemassa todennäköisyysalgoritmeja tiettyjen "vaikeasti laskettavien" invarianttien arvojen määrittämiseksi, mutta tällaisten algoritmien käyttö ei ole aina sallittua. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

Tällä hetkellä polynomiajassa laskettavissa olevaa täydellistä graafiinvarianttia ei tunneta, mutta sitä ei ole todistettu olevan olemassa. Sitä yritettiin löytää toistuvasti XX-luvun 60-80-luvuilla , mutta ne eivät onnistuneet.

Sovellukset tietokonekemiassa

Tietokonekemiassa käytetään monia invariantteja ( topologisia indeksejä ) useiden yleisten ja erityisten ongelmien ratkaisemiseen [2] . Näihin tehtäviin kuuluvat: ennalta määrättyjen ominaisuuksien omaavien aineiden haku (haku "rakenne-ominaisuus", "rakenne-farmakologinen aktiivisuus" -tyyppiset riippuvuudet), rakennetietojen ensisijainen suodatus tietyn tyyppisten molekyylikaavioiden ei-toistuvaa luomista varten, ja useita muita. Usein topologisten indeksien ohella (riippuen vain molekyylin rakenteesta) käytetään myös tietoa yhdisteen kemiallisesta koostumuksesta [3] .

Katso myös

Muistiinpanot

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov Graafiteorian perusteet]. - M .: Nauka, 1986. - 384 s. - ISBN 978-5-9502-0057-1 .
↑ Topologian ja graafiteorian kemialliset sovellukset = Chemical Applications of Topology and Graph Theory / Toim. R. King. - M .: Mir, 1987. - 560 s.
↑ M. I. Trofimov, E. A. Smolensky, Proceedings of the Sciences. Chemical series , 2005, s. 2166-2176.