Graf invariantní

Invariantní graf v teorii grafů je nějaká obvykle číselná hodnota nebo uspořádaná množina hodnot ( hashovací funkce ) , která charakterizuje strukturu grafu a nezávisí na způsobu označení vrcholů ani na grafickém znázornění grafu . Hraje důležitou roli při kontrole izomorfismu grafů , stejně jako v problémech počítačové chemie . $G=\langle A,V\rangle$

Příklady invariantů

Mezi invarianty grafu patří:

Průměr grafu je délka nejkratší cesty (vzdálenosti) mezi dvojicí nejvzdálenějších vrcholů. $\mathrm {diam} (G)$
Invariant Colina de Verdière .
Wienerův index je hodnota , kde je minimální vzdálenost mezi vrcholy a . $w=\součet _{{\forall i,j}}d(v_{i},v_{j})$ $d(v_{i},v_{j})$ $v_{i}$ $v_{j}$
Randic index je hodnota . $r=\sum _{{(v_{i},v_{j})\in V)){\frac {1}({\sqrt {d(v_{i})d(v_{j)))) ) }}$
Hosoyův index je počet shod hran v grafu plus jedna.
Mini- a maxi-kód matice sousednosti, získaný zapsáním binárních hodnot matice sousednosti do řádku a následným převedením výsledného binárního čísla do desítkové formy. Minikód odpovídá takovému pořadí řádků a sloupců, ve kterém je výsledná hodnota co nejmenší; maxi-kód - respektive maximum. $\mu _{{min}}(G)$ $\mu _{{max}}(G)$
Minimální počet vrcholů, které musí být odstraněny, aby se získal rozpojený graf .
Minimální počet hran, které musí být odstraněny, aby se získal rozpojený graf.
Minimální počet vrcholů potřebných k pokrytí hran.
Minimální počet hran potřebných k pokrytí vrcholů.
Nehustota grafu je počet vrcholů maximálního (vzhledem k inkluzi) bezhranového podgrafu (největší počet po párech nesousedících vrcholů). Je snadné to vidět a . $\epsilon (G)$ $\varphi (G)=\epsilon (\overline {G})$ $\epsilon (G)=\varphi (\overline {G})$
Obvod grafu je počet hran v minimálním cyklu.
Determinant matice sousedství .
Hustota grafu je počet vrcholů s maximální inkluzní klikou . $\varphi (G)$
Vzestupný nebo sestupný vektor stupňů vrcholů — při použití výčtových algoritmů pro určování izomorfismu grafu jsou vrcholy se shodnými stupni vybrány jako domněle izomorfní páry vrcholů, což pomáhá snížit složitost výčtu. Použití tohoto invariantu pro k-homogenní grafy nesnižuje výpočetní složitost výčtu, protože stupně všech vrcholů takového grafu jsou stejné: . $s(G)=(d(v_{1}),d(v_{2}),\tečky ,d(v_{n}))$ $s(G)=(k,k,\tečky,k)$
Vzestupný nebo sestupný vektor vlastních hodnot matice sousednosti grafu (spektrum grafu). Matice sousedství sama o sobě není invariantní, protože když se změní číslování vrcholů, podstoupí permutaci řádků a sloupců.
Počet vrcholů a počet oblouků/hran . $n(G)=|A|$ $m(G)=|V|$
Počet připojených složek grafu . $\kappa (G)$
Hadwigerovo číslo . $\eta (G)$
Charakteristický polynom matice sousednosti.
Chromatické číslo . $\chi (G)$

Za invariant nelze považovat jedno z výše uvedených čísel, ale jejich n-tici (superindex) tvaru , který zase může být spojen s polynomem tvaru $(p_{0},p_{1},p_{2},\tečky)$

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

sčítání se provádí až do poslední nenulové hodnoty . Podobným způsobem lze zavést několik dalších invariantů grafu: $p_{i}$

$D(G)=\součet _{{i=0}}^{n}d_{i}(G)x^{i}=d_{0}(G)+d_{1}(G)x+d_ {2}(G)x^{2}+\tečky +d_{n}(G)x^{n}$ , kde je počet vrcholů stupně i; $kopat)$
$E(G)=\sum _{{i=0}}^{{\epsilon (G)}}e_{i}(G)x^{i}=e_{0}(G)+e_{1} (G)x+e_{2}(G)x^{2}+\tečky +e_{{\epsilon }}(G)x^{{\epsilon }}$ , kde je počet bezhranných i-vertexových podgrafů; $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}+\tečky +f_{{\varphi }}(G)x^{{\varphi }}$ , kde je počet úplných i-vertexových podgrafů (i-klik); $f_{i}(G)$
$H(G)=\součet _{{i=1}}^{{\eta (G)))h_{i}(G)x^{i}=h_{1}(G)x+h_{2 }(G)x^{2}+\tečky +h_{{\eta }}(G)x^{{\eta }}$ , kde je počet různých kontrakcí spojeného grafu na i-kliku; $h_{i}(G)$ $G$
$K(G)=\součet _{{i=1}}^{n}k_{i}(G)x^{i}=k_{1}(G)x+k_{2}(G)x^ {2}+\tečky +k_{n}(G)x^{n}$ , kde je počet spojených komponent z i vrcholů; $k_{i}(G)$
$Y(G)=\součet _{{i=\chi (G)}}^{n}y_{i}(G)x^{i}=y_{{\chi }}(G)x^{{ \chi }}+y_{{\chi +1}}(G)x^{{\chi +1}}+\tečky +y_{n}(G)x^{n}$ , kde je počet i-zabarvení grafu (správné vybarvení pomocí přesně i barev). $y_{i}(G)$

Systémy grafových invariantů závislých na dvou nebo více parametrech lze zapsat jako polynomy v několika formálních proměnných . $x,y,z,\tečky$

$A(G)=\součet _{{i,j\geq 0}}\alpha _{{ij}}(G)x^{i}y^{j}$ , kde je počet podgrafů grafu , které mají vrcholy a hrany; $\alpha _{{ij}}(G)$ $G$ $i$ $j$
$B(G)=\součet _{{i,k\geq 0}}\beta _{{ik}}(G)x^{i}z^{k}$ , kde je počet i-vrcholových podgrafů, pro které je počet jehel (hran spojujících vrcholy podgrafu se zbytkem vrcholů grafu) roven ; $\beta _{{ik}}(G)$ $k$
$S(G)=\součet _{{i,j,k\geq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , kde je počet i-vertexových podgrafů s hranami a jehlami (zobecnění invariantů a ); $s_{{ijk}}(G)$ $j$ $k$ $A(G)$ $B(G)$
Polynomiální Tatta .

Koincidence invariantů je nutnou , ale ne postačující podmínkou pro přítomnost izomorfismu [1]

Kompletní invariant

O invariantu se říká , že je úplný , pokud je koincidence grafových invariantů nezbytná a dostatečná k vytvoření izomorfismu. Například každá z hodnot a je úplným invariantem pro graf s pevným počtem vrcholů . $\mu _{{min}}(G)$ $\mu _{{max}}(G)$ $n$

Složitost výpočtu

Invarianty se liší složitostí výpočtu. Invarianty , , a se počítají triviálně, zatímco výpočet invariantů , , , , , a těch, které na nich závisejí, může být poměrně výpočetně obtížný . Existují pravděpodobnostní algoritmy pro určení hodnot daných „těžko vypočítatelných“ invariantů, ale použití takových algoritmů není vždy povoleno. $n(G)$ $m(G)$ $s(G)$ $\kappa (G)$ $\varphi (G)$ $\epsilon (G)$ $\chi (G)$ $\eta (G)$ $\mu _{{min}}(G)$ $\mu _{{max}}(G)$

V současné době není znám úplný grafový invariantní výpočet v polynomiálním čase, ale nebylo prokázáno, že neexistuje. Pokusy o jeho nalezení byly opakovaně prováděny v 60. - 80. letech 20. století , ale byly neúspěšné.

Aplikace v počítačové chemii

Mnoho invariantů ( topologické indexy ) se používá v počítačové chemii k řešení široké škály obecných a speciálních problémů [2] . Mezi tyto úkoly patří: vyhledávání látek s předem určenými vlastnostmi (hledání závislostí typu „struktura-vlastnost“, „struktura-farmakologická aktivita“), primární filtrování strukturních informací pro neopakovatelné generování molekulárních grafů daného typu a řada dalších. Často se spolu s topologickými indexy (v závislosti pouze na struktuře molekuly) používá také informace o chemickém složení sloučeniny [3] .

Viz také

Poznámky

↑ Zykov A. A. [www.bookshunt.ru/b5868_osnovi_teorii_grafov Základy teorie grafů]. — M .: Nauka, 1986. — 384 s. - ISBN 978-5-9502-0057-1 .
↑ Chemické aplikace topologie a teorie grafů = Chemical Applications of Topology and Graph Theory / Ed. R. Král. — M .: Mir, 1987. — 560 s.
↑ M. I. Trofimov, E. A. Smolensky, Sborník Akademie věd. Chemická řada , 2005, s. 2166-2176.