Invariáns gráf

A gráfelméletben a gráfinvariáns valamilyen általában numerikus érték vagy értékek rendezett halmaza ( hash függvény )gráf szerkezetét jellemzi , és nem függ a csúcsok megjelölésének módjától vagy a gráf grafikus ábrázolásától . Fontos szerepet játszik a gráfok izomorfizmusának ellenőrzésében, valamint a számítógépes kémiai feladatokban . $G=\langle A,V\rangle$

Példák invariánsokra

A grafikon invariánsai a következők:

A gráf átmérője a legtávolabbi csúcsok párja közötti legrövidebb út (távolság) hossza. $\mathrm {diam} (G)$
Colin de Verdière invariánsa .
A Wiener-index az az érték , ahol a csúcsok és a csúcsok közötti minimális távolság . $w=\sum _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i},v_{j})$ $v_{i}$ $v_{j}$
A Randic index az érték . $r=\sum _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) ) }}$
A Hosoya index a gráf élillesztéseinek száma plusz egy.
A szomszédsági mátrix mini- és maxi kódja , amelyet úgy kapunk, hogy a szomszédsági mátrix bináris értékeit egy sorba írjuk, majd a kapott bináris számot decimális alakra konvertáljuk. A minikód a sorok és oszlopok olyan sorrendjének felel meg, amelyben a kapott érték a lehető legkisebb; maxi-kód - illetve a maximum. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
A csúcsok minimális száma, amelyet el kell távolítani, hogy szétválasztott gráfot kapjunk .
Az élek minimális száma, amelyet el kell távolítani, hogy szétválasztott gráfot kapjunk.
Az élek lefedéséhez szükséges csúcsok minimális száma .
A csúcsok lefedéséhez szükséges minimális élek száma.
A gráf nemsűrűsége egy maximális (a befogadáshoz képest) él nélküli részgráf csúcsainak száma (a páronkénti nem szomszédos csúcsok legnagyobb száma). Könnyen belátható, hogy és . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
A gráf kerülete a minimális ciklus éleinek száma.
Szomszédsági mátrix meghatározó .
A gráf sűrűsége azoknak a csúcsoknak a száma, amelyeknél a maximális befogadási klikk . $\varphi (G)$
Csúcsfokozatok növekvő vagy csökkenő vektora – ha a gráf izomorfizmusának meghatározására numerációs algoritmusokat használunk, az egybeeső fokozatú csúcsokat feltételezetten izomorf csúcspárokként választjuk ki, ami segít csökkenteni a felsorolás bonyolultságát. Ennek az invariánsnak a használata k-homogén gráfokhoz nem csökkenti a felsorolás számítási bonyolultságát, mivel egy ilyen gráf minden csúcsának foka azonos: . $s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))$ $s(G)=(k,k,\pontok ,k)$
Egy gráf szomszédsági mátrixának (gráfspektrum) sajátértékeinek növekvő vagy csökkenő vektora . Maga a szomszédsági mátrix nem invariáns, mivel amikor a csúcsok számozása megváltozik, sorok és oszlopok permutációján megy keresztül.
A csúcsok száma és az ívek/élek száma . $n(G)=|A|$ $m(G)=|V|$
A gráf összekapcsolt összetevőinek száma . $\kappa (G)$
Hadwiger szám . $\eta (G)$
A szomszédsági mátrix karakterisztikus polinomja .
Kromatikus szám . $\chi (G)$

Invariánsként nem a fenti számok egyikét tekinthetjük, hanem azok sorszámát ( superindexét ) az alakban , amely viszont társítható az alak polinomjához. $(p_{0},p_{1},p_{2},\pontok)$

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

az összegzés az utolsó nem nulla értékig történik . Hasonló módon számos további gráfinvariáns is bevezethető: $p_{i}$

$D(G)=\összeg _{{i=0}}^{n}d_{i}(G)x^{i}=d_{0}(G)+d_{1}(G)x+d_ {2}(G)x^{2}+\pontok +d_{n}(G)x^{n}$ , ahol az i fokú csúcsok száma; $d_{i}(G)$
$E(G)=\összeg _{{i=0}}^{{\epsilon (G)}}e_{i}(G)x^{i}=e_{0}(G)+e_{1} (G)x+e_{2}(G)x^{2}+\pontok +e_{{\epsilon }}(G)x^{{\epsilon }}$ , ahol az él nélküli i-csúcs részgráfok száma; $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}+\pontok +f_{{\varphi }}(G)x^{{\varphi }}$ , ahol a teljes i-csúcs részgráfok (i-klikk) száma; $ábra)$
$H(G)=\összeg _{{i=1}}^{{\eta (G)))h_{i}(G)x^{i}=h_{1}(G)x+h_{2 }(G)x^{2}+\pontok +h_{{\eta }}(G)x^{{\eta }}$ , ahol az összekapcsolt gráf különböző összehúzódásainak száma i-klikkenként; $h_{i}(G)$ $G$
$K(G)=\összeg _{{i=1}}^{n}k_{i}(G)x^{i}=k_{1}(G)x+k_{2}(G)x^ {2}+\pontok +k_{n}(G)x^{n}$ , ahol az i csúcsokból összekötött komponensek száma; $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}}+\pontok +y_{n}(G)x^{n}$ , ahol a grafikon i-színezéseinek száma (a helyes színezés pontosan i szín használatával). $y_{i}(G)$

A két vagy több paramétertől függő gráfinvariánsok rendszerei több formális változóban polinomként írhatók fel. Például: $x,y,z,\pontok$

$A(G)=\sum _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , ahol a gráf azon részgráfjainak száma, amelyeknek csúcsai és élei vannak; $\alpha _{{ij}}(G)$ $G$ $én$ $j$
$B(G)=\sum _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , ahol azoknak az i-csúcs részgráfoknak a száma, amelyeknél a tűk (az részgráf csúcsait a gráf többi csúcsával összekötő élek) száma egyenlő ; $\beta _{{ik}}(G)$ $k$
$S(G)=\sum _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , ahol az élekkel és tűkkel rendelkező i-csúcs részgráfok száma (az invariánsok általánosítása és ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polinom Tatta .

Az invariánsok egybeesése szükséges , de nem elégséges feltétele az izomorfizmus jelenlétének [1]

Teljes invariáns

Egy invariánst akkor mondunk teljesnek , ha a gráfinvariánsok egybeesése szükséges és elégséges az izomorfizmus megállapításához. Például a és az értékek mindegyike teljes invariáns egy rögzített számú csúcsot tartalmazó gráfhoz . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

A számítás összetettsége

Az invariánsok a számítás bonyolultságában különböznek egymástól. A , , és invariánsokat triviálisan számítjuk, míg a , , , , és a tőlük függő invariánsok számítása meglehetősen nehézkes lehet . Vannak valószínűségi algoritmusok az adott "nehezen kiszámítható" invariánsok értékének meghatározására, de az ilyen algoritmusok használata nem mindig megengedett. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

Jelenleg egy teljes, polinomiális időben kiszámítható gráfinvariáns nem ismert, de nem bizonyított, hogy nem létezik. A XX. század 60-as és 80-as éveiben többször is megkísérelték megtalálni , de nem jártak sikerrel.

Alkalmazások a számítógépes kémiában

Számos invariánst ( topológiai indexet ) használnak a számítógépes kémiában számos általános és speciális probléma megoldására [2] . E feladatok közé tartozik: előre meghatározott tulajdonságokkal rendelkező anyagok keresése ("szerkezet-tulajdonság", "szerkezet-farmakológiai aktivitás" típusú függőségek keresése), szerkezeti információk elsődleges szűrése adott típusú molekulagráfok nem ismétlődő generálásához, ill. számos másik. Gyakran a topológiai indexek mellett (csak a molekula szerkezetétől függően) a vegyület kémiai összetételére vonatkozó információkat is felhasználnak [3] .

Lásd még

Jegyzetek

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov A gráfelmélet alapjai]. — M .: Nauka, 1986. — 384 p. - ISBN 978-5-9502-0057-1 .
↑ A topológia és gráfelmélet kémiai alkalmazásai = Chemical Applications of Topology and Graph Theory / Szerk. R. King. — M .: Mir, 1987. — 560 p.
↑ M. I. Trofimov, E. A. Szmolenszkij, Proceedings of the Sciences Akadémia. Chemical sorozat , 2005, 2166-2176.