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 E1 iseendaga, kus E1⋅E1=E2 ning En−1⋅E1=En kusjuures iga astme n korral fikseerida erinevate binaarmärkide ei,jn arv p maatriksis En, mis reeglina suureneb. Tipupaariorbiitide basil korrastatud korrutis En 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

Invariantide arendusi

Invariandina võib käsitleda mitte vaid üht konkreetset arvu vaid ka nende korteeži kujul (p0,p1,p2,…), nagu selleks on:

Kahest või rohkemast parameetrist sõltuvaid invariantide süsteeme võib esitada formaalsete muutujate polünoomidena x,y,z,…, nagu:

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 μmin(G) ja μmax(G) osutub fikseeritud tippude arvuga n graafi täielikuks invariandiks.

Täielike invariantidena töötavad järgmised moodustised:

Algoritmilisest keerukusest

Invariante eristatakse nende algoritmilise keerukuse alusel. Invariandid n(G), m(G), s(G) ja κ(G) saadakse triviaalselt, samal ajal kui niisuguste invariantide nagu φ(G), ϵ(G), χ(G), η(G), μmin(G), μ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

Kirjandust