Graafi invariant

**Graafi invariant** on graafi struktuuri iseloomustava atribuudi arvuline väärtus või niisuguste väärtuste korrastatud kogum, mis ei sõltu graafi tippude märgistatusest ega selle graafilisest kujutisest. Mängib olulist osa graafide isomorfismi tuvastamisel.

Graafi **fundamentaalne invariant** on tema struktuur''' kui diskreetse objekti elementide kooslus (organiseeritus) selle *elementide seostatuskorra* näol.
Struktuur kui niisugune ise on esitatav graafina **G**, kus isomorfsed graafid omavad ühesugust struktuuri. 
Struktuuri peamisteks karakteristikuteks on selle sümmeetria''' omadused, mis avalduvad *ühesuguste elementide (st tippude, tipupaaride)* näol mida rühmateooria aspektist *orbiitideks (sh transitiivsuspiirkondadeks, ekvivalentsusklassideks, positsioonideks jm) * nimetatakse.

Tipupaarid on eristatavad graafi seosmaatriksi astendamise teel. Korrutada algne seosmaatriks E^1 iseendaga, kus E^1\cdot E^1= E^2 ning E^{n-1}\cdot E^1= E^n  kusjuures iga astme n korral fikseerida erinevate binaarmärkide e^n_{i,j} arv p maatriksis  E^n, mis reeglina suureneb.
Tipupaariorbiitide basil korrastatud korrutis  E^n on isomorfsete graafide täielik invariant . 

Graafi invariandid jagunevad *globaalseteks* (graafi tervikut iseloomustavateks) ja *lokaalseteks* (näiteks, üksikuid tippe ja tipupaare iseloomustavateks). 

## Invariantide lihtsamaid näiteid
* Tippude arv n(G)=|A| või servade arv m(G)=|V| või mõlemad koos.
* Graafi diameeter \mathrm{diam}(G) on lühima tee pikkus (kaugus) kahe omavahel kõige kaugema tipu vahel.
* Sidusate komponentide arv \kappa(G).
* Tippude minimaalne arv mille eemaldamine on tarvilik mittesidusa graafi saamiseks.
* Servade minimaalne arv mille eemaldamine on tarvilik mittesidusa graafi saamiseks.
* Seosmaatriksi determinant.
* Seosmaatriksi *karakteristlik [[polünoom]]*.
* Graafi orbiidid.
* Hadwigeri arv \eta(G).
* Kromaatiline arv \chi(G).
* Wieneri indeks — suurus w=\sum_{\forall i, j} d(v_i, v_j), kus d(v_i, v_j) on tippudevaheline väikseim kaugus v_i и v_j.
* Randichi indeks — suurus r=\sum_{(v_i, v_j) \in V} \frac{1}{\sqrt{d(v_i) d(v_j)}}.
* Graafi spekter, mis saadakse seosmaatriksi alusel.

## Invariantide arendusi
Invariandina võib käsitleda mitte vaid üht konkreetset arvu vaid ka nende korteeži kujul (p_0, p_1, p_2, \dots), nagu selleks on:
* Tippude valentsuste (astakute) vektor s(G)=(d(v_1), d(v_2), \dots, d(v_n)).
* Polünoom P(x) = \sum_{i \ge 0} p_i x^i = p_0 + p_1 x + p_2 x^2 + \dots,;
* 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, kus d_i(G) on tippude arv valentsusega i.
Kahest või rohkemast parameetrist sõltuvaid invariantide süsteeme võib esitada formaalsete muutujate polünoomidena x, y, z, \dots, nagu:
* A(G)=\sum_{i,j \ge 0} \alpha_{ij}(G) x^i y^j, kus \alpha_{ij}(G) on graafi G alamgraafide arv, mis omavad i tippu ja j serva;
* B(G) = \sum_{i,k \ge 0} \beta_{ik}(G) x^i z^k, kus \beta_{ik}(G) on i tipuliste alamgraafide hulk, kus *nõelte* (st alamgraafi tippe graafi teiste tippudega siduvate servade) arv võrdub k.

Selliseid invariante on arendatud hulgi, nende kokkulangemine on tarvilik kuid paraku mitte piisav tingimus isomorfismi olemasoluks.

## Täielik invariant
Invariant on **täielik** kui nende kokkulangevus on tarvilik ja piisav isomorfismi tuvastamiseks. Näiteks, igaüks väärtustest \mu_{min}(G) ja \mu_{max}(G) osutub fikseeritud tippude arvuga n graafi täielikuks invariandiks.

Täielike invariantidena töötavad järgmised moodustised:
* *Kolmkuup koodid*, mis kujutavad endast ülipikki kahendsüsteemis jadasid (http://www.math.fau.edu/locke/isotest. ). Paraku ei sisalda need mingit teavet graafi struktuuri kohta.
* *Suurimad summad*, mis kujutavad endast pikki arvude jadasid (http://web.me.com/blazej.podsiadlo/poudis/Graph_Isomorphism.html). Paraku ei sisalda needki mingit teavet graafi struktuuri kohta kuid võimaldavad *mõõta sarnasust* graafide vahel.
* *[[Graafi struktuur|Semiootilised mudelid]]* on rajatud tipupaaride süvaidentifitseerimisele ning esitavad graafi struktuuri orbiitide ja isomorfismi täpsusega .

## Algoritmilisest keerukusest
Invariante eristatakse nende algoritmilise keerukuse alusel. Invariandid n(G), m(G), s(G) ja \kappa(G) saadakse triviaalselt, samal ajal kui niisuguste invariantide nagu \varphi(G), \epsilon(G), \chi(G), \eta(G), \mu_{min}(G), \mu_{max}(G) puhul see nii ei ole.

Käesoleva aja ametlikust, XX sajandist pärit seisukohast, polünomiaalset täielikku invarianti ei tunnustata, kuigi pole tõestatud et neid ei esine. Samal ajal on näidatud, et semiootilise mudeli algoritmiline keerukus saab sõltuda vaid tippude arvust.

## Vaata ka

Graafi kanooniline esitus

Graafide identifitseerimine

## Viited


## Kirjandust
* Harary, F. 1972 *Graph Theory*. Addison-Wesley ISBN 0201027879.
* Зыков, А. А. 1987 *Основы теории графов*. Наука, Москва.
* Dharwadker, A., Pirzada, B. 2011. *Graph Theory*, Amazon Books, 2011. ISBN 9781466254998