Graficul invariant

Un grafic invariant în teoria graficelor este o valoare numerică de obicei sau un set ordonat de valori ( funcția hash ) , care caracterizeaza structura graficului si nu depinde de metoda de marcare a varfurilor sau de reprezentarea grafica a graficului . Joacă un rol important în verificarea izomorfismului graficelor , precum și în problemele de chimie computerizată . $G=\langul A,V\rangle$

Exemple de invariante

Invarianții graficului includ:

Diametrul graficului este lungimea celei mai scurte căi (distanță) dintre perechea celor mai îndepărtate vârfuri. $\mathrm {diam} (G)$
Invariant al lui Colin de Verdière .
Indicele Wiener este valoarea , unde este distanța minimă dintre vârfuri și . $w=\sum _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i},v_{j})$ $v_{i}$ $v_{j}$
Indicele Randic este valoarea . $r=\sum _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) )}}$
Indicele Hosoya este numărul de potriviri de margine din grafic plus unu.
Mini- și maxi-cod al matricei de adiacență, obținut prin scrierea valorilor binare ale matricei de adiacență într-o linie, urmată de conversia numărului binar rezultat în formă zecimală. Mini-codul corespunde unei astfel de ordine de rânduri și coloane, în care valoarea rezultată este cea mai mică posibilă; maxi-code - respectiv, maximul. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
Numărul minim de vârfuri care trebuie eliminate pentru a obține un grafic deconectat .
Numărul minim de muchii care trebuie eliminate pentru a obține un grafic deconectat.
Numărul minim de vârfuri necesare pentru a acoperi marginile.
Numărul minim de muchii necesare pentru a acoperi vârfurile.
Nedensitatea unui graf este numărul de vârfuri ale unui subgraf fără margini maxim (în raport cu includerea) (cel mai mare număr de vârfuri neadiacente în perechi). Este ușor să vezi că și . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
Circumferința graficului este numărul de muchii din ciclul minim.
Determinantul matricei adiacentei .
Densitatea graficului este numărul de vârfuri cu clica maximă de incluziune . $\varphi (G)$
Un vector ascendent sau descendent de grade de vârfuri - atunci când se utilizează algoritmi de enumerare pentru determinarea izomorfismului grafic, vârfurile cu grade coincidente sunt selectate ca perechi presupus izomorfe de vârfuri, ceea ce ajută la reducerea complexității enumerarii. Utilizarea acestui invariant pentru grafuri k-omogene nu reduce complexitatea de calcul a enumerarii, deoarece gradele tuturor nodurilor unui astfel de graf sunt aceleasi: . $s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))$ $s(G)=(k,k,\puncte,k)$
Un vector ascendent sau descendent de valori proprii ale matricei de adiacență a unui grafic (spectrul graficului). Matricea de adiacență în sine nu este o invariantă, deoarece atunci când numerotarea vârfurilor se modifică, suferă o permutare a rândurilor și coloanelor.
Numărul de vârfuri și numărul de arce/muchii . $n(G)=|A|$ $m(G)=|V|$
Numărul de componente conectate ale graficului . $\kappa (G)$
numărul Hadwiger . $\eta (G)$
Polinomul caracteristic al matricei de adiacentă.
Număr cromatic . $\chi (G)$

Ca invariant, se poate considera nu unul dintre numerele de mai sus, ci tupla lor (superindex) de forma , care, la rândul său, poate fi asociat cu un polinom de forma $(p_{0},p_{1},p_{2},\puncte)$

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

însumarea se efectuează până la ultima valoare diferită de zero . Într-un mod similar, mai pot fi introduși câțiva invarianți grafici: $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}$ , unde este numărul de vârfuri de gradul i; $săpa)$
$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 }}$ , unde este numărul de subgrafe i-vertex fără margini; $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 }}$ , unde este numărul de subgrafe complete i-vertex (i-clicuri); $Fig)$
$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 }}$ , unde este numărul de contracții diferite ale grafului conectat pe i-clică; $bună 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}$ , unde este numărul de componente conectate de la i vârfuri; $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}$ , unde este numărul de i-colorări ale graficului (colorări corecte folosind exact i culori). $y_{i}(G)$

Sistemele de invarianți grafici care depind de doi sau mai mulți parametri pot fi scrise ca polinoame în mai multe variabile formale. De exemplu: $x,y,z,\puncte$

$A(G)=\sum _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , unde este numărul de subgrafe ale graficului care au vârfuri și muchii; $\alpha _{{ij}}(G)$ $G$ $i$ $j$
$B(G)=\sum _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , unde este numărul de subgrafe i-vertex pentru care numărul de ace (marginile care leagă vârfurile subgrafului cu restul vârfurilor grafului) este egal cu ; $\beta _{{ik}}(G)$ $k$
$S(G)=\sum _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , unde este numărul de subgrafe i-vertex cu muchii și ace (generalizarea invarianților și ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polinom Tatta .

Coincidența invarianților este o condiție necesară , dar nu suficientă pentru prezența unui izomorfism [1]

Invariant complet

Se spune că un invariant este complet dacă coincidența invarianților graficului este necesară și suficientă pentru a stabili un izomorfism. De exemplu, fiecare dintre valorile și este un invariant complet pentru un grafic cu un număr fix de vârfuri . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Complexitatea calculului

Invarianții diferă în complexitatea calculului. Invarianții , , și sunt calculate trivial, în timp ce calculul invarianților , , , , și a celor care depind de ei poate fi destul de dificil din punct de vedere computațional . Există algoritmi probabilistici pentru determinarea valorilor invarianților „greu de calculat” dați, dar utilizarea unor astfel de algoritmi nu este întotdeauna permisă. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

În prezent, un invariant grafic complet calculat în timp polinomial este necunoscut, dar nu s-a dovedit că nu există. Încercările de a-l găsi au fost făcute în mod repetat în anii 60 - 80 ai secolului XX , dar nu au avut succes.

Aplicații în chimia computerizată

Mulți invarianți ( indici topologici ) sunt utilizați în chimia computerizată pentru a rezolva o gamă largă de probleme generale și speciale [2] . Aceste sarcini includ: căutarea de substanțe cu proprietăți predeterminate (căutarea dependențelor de tip „structură-proprietate”, „structură-activitate farmacologică”), filtrarea primară a informațiilor structurale pentru generarea nerepetitivă de grafice moleculare de un anumit tip și o serie de altele. Adesea, alături de indici topologici (în funcție doar de structura moleculei), se folosesc informații și despre compoziția chimică a compusului [3] .

Vezi și

Note

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov Fundamentele teoriei grafurilor]. — M .: Nauka, 1986. — 384 p. - ISBN 978-5-9502-0057-1 .
↑ Chemical Applications of Topology and Graph Theory = Chemical Applications of Topology and Graph Theory / Ed. R. Regele. — M .: Mir, 1987. — 560 p.
↑ M. I. Trofimov, E. A. Smolensky, Proceedings of the Academy of Sciences. Seria chimică , 2005, p. 2166-2176.