Graafide identifitseerimine

Graafide identifitseerimine tähendab graafide eristamist, äratundmist või tuvastamist neist tuletatud invariantide põhjal mitmesuguste koodide, vektorite, polünoomide, spektrite jt. näol. Seda nimetatakse ka kanoniseerimiseks .
Graafi identifitseerimine tipupaaride baasil.
Graafi formula_1 põhiline omadus on tema struktuur, organiseeritus, mis rajaneb elementidevahelistele suhetele. Struktuur ise on kujutatav graafina formula_1 kusjuures "isomorfsed graafid omavad ühesugust struktuuri". Struktuuri põhilisteks karakteristikuteks on tema sümmeetriaomadused, mis avalduvad sarnaste elementide (tippude ja tipupaaride) näol, mida rühmateooria aspektist nimetatakse graafi orbiitideks (või transitiivsuspiirkondadeks, ekvivalentsusklassideks).
Graafi elementaarosised on tipupaarid (mitte tipud) ja selle elementaarsed sümmeetriaosised on tipupaariorbiidid formula_3. Tipupaare (st tipupaaride vahelisi suhteid) on püütud identifitseerida nende "ümbruste ühisosa iseloomustavate invariantide abil" struktuurimudeli formula_4 näol .
Efektiivsemaks on osutunud "graafi seosmaatriksi astendamine (korrutamine iseendaga)". Kui algses seosmaatriksis formula_5 on vaid kaks tipupaaride ekvivalentsusklassi: servad ja mitteservad, siis algse maatriksi korrutamisel iseendaga formula_6 suureneb klasside arv formula_7, mis toimub teatud astmeni formula_8, formula_9 ja siis seiskub .
Seega, iga astme formula_10 korral suureneb tipupaare iseloomustavate astmeelementide formula_11 erinevate väärtuste arv formula_7. Moodustada nende erinevate väärtuste jada formula_13 … formula_14 . 
Kui astme formula_15 korral erinevate väärtuste arv formula_7 enam ei suurene, siis peatada korrutamine ja moodustada väärtuste jada formula_17 baasil igale reale formula_18 vastav väärtuste sagedusvektor formula_19.
Järjestada (transponeerida) saadud maatriksastme formula_8 read formula_18 ja veerud formula_22 leksikograafiliselt vastavalt nende sagedusvektoritele formula_19. Saame korrastatud maatriksastme formula_24.
Salvestada maatriksaste formula_8 ja selle korrastatud maatriksaste formula_24.
Nii struktuurimudel formula_4 kui ka maatriksaste formula_24 on võrdväärsed, teineteist täiendavad graafide identifitseerimise atribuudid. Kuigi formula_4 eristab ja esitab tippudevahelisi suhteid küllaltki täpselt, võivad need osutuda vahest mittetäielikeks invariantideks. formula_30 elemendid on küll täielikud invariandid, kuid ei erista omavahel graafi servi ega nende puudumist.
Orbiitide (positsiooniklasside) põhiomadused.
1. Kui graafi formula_1 "tipud" formula_32 formula_33 kuuluvad samasse positsiooni (orbiiti) formula_34 "siis on alamgraafid" formula_35 formula_36 formula_37 formula_36 formula_33 "isomorfsed", st omavad ühesugust struktuuri.
2. Kui graafi formula_1 "servad" formula_41 formula_33 kuuluvad samasse positsiooni (orbiiti) formula_3 "siis on alamgraafid" formula_44 formula_36 formula_46 formula_36 formula_33 "isomorfsed", st omavad ühesugust struktuuri.
3. Kui graafi formula_1 "mitteservad" formula_50 formula_33 formula_33 kuuluvad samasse positsiooni (orbiiti) formula_3 "siis on ülemgraafid" formula_54 formula_36 formula_56 formula_36 formula_33 "isomorfsed", st omavad ühesugust struktuuri.
4. Tipupaari-orbiitide formula_3 baasil saadud isomorfsed alamgraafid kujutavad endast graafi formula_1 "naaber-alamstruktuuri" ja/või "naaber-ülemstruktuuri", mida üldistatult lihtsalt naaberstruktuuriks formula_61 nimetame.
5. Iga naaberstruktuur formula_61 omab nö reversiivset orbiiti formula_63 millele rakendatud servaoperatsioon "taastab lähtestruktuuri" formula_1. Seda struktuuridevahelist seost nimetame mofisdmiks.
6. Kõikide "n" tipuliste naaberstruktuuride "jadade parv" tühistruktuuri ja täisstruktuuri vahel moodustab "n-tipuliste graafide süsteemi". Selle süsteemi graafe võime omakorda kujutada tippudena ja nendevahelisi naabrusi ehk morfisme servadena.
Näiteks: neljatipuliste graafide süsteem kujutab endast 11 elemendilist võre millel on 14 serva; viietipuliste süsteem koosneb 34 struktuurist ja 72 morfismist nende vahel; kuuetipuliste süsteem koosneb 156 struktuurist ja 572 morfismist nende vahel, jne. Kõik see on seotud üleminekutõenäosuste ja ka Ulami hüpoteesiga serva-eralduste aspektist.
7. Graaf, mis koosneb orbiiti formula_3 kuuluvatest servadest nimetatakse "orbiitgraafiks" formula_66.
Orbiitgraafide omadusi.
1. Orbiitgraaf formula_66on tippudest, servadest ja "mitteservadest" sümmeetriline, st omab ühte tipu-, ühr serva- ja ühte "mitteserva" orbiiti.
2. Orbiitgraafid on graafi formula_1 lõikumatud osised (alamgraafid).
3. Mõned orbiitgraafid formula_66 võivad olla "isomorfsed oma lähtegraafiga" formula_1 (näiteks, kuubi üks orbiitgraafidest on kuup)..
4. Erinevate graafide orbiitgraafid formula_66 võivad olla "isomorfsed või kattuda".
5. Orbiitgraaf omab oma orbiitgraafi mis kujutab endast "teist järku orbiitgraafi", neid järkusi võib olla rohkemgi.
6. Kõrgemat järku orbiitgraafid võivad olla isomorfsed või kattuda oma alamat järku orbiitgraafiga või ka lähtegraafiga formula_1. Nende moodustumine on koonduv protsess.
Orbiitgraahid avavad lähtegraafi "varjatud külgi". Näiteks Folkmani graafi üks orbiitgraaf on Peterseni graaf. Orbiitgraafid "avavad erinavate graafide ühesuguseid osiseid". Hüperkuup ja Möbius-Kantori graaf omavad ühesuguseid orbiitgraafe, jne. Orbiitgraafid on olulised vahendid graafi struktuuri ja sümmaatriaomaduste tuvastamisel.
Tulemuste tähendusest.
Graafi "täielikku identifikaatorit" või -"invarianti", st identifikaatorit mis eristab graafi selle isomorfismi ja sümmeetriaomaduste täpsusega on otsitud aastakümneid, kuid need ei ole andnud soovitud tulemusi ning huvi nende vastu on raugenud. Lahendusi on püütud leida ka graafi kanoonilise esituse pinnal. Paraku ei sisalda niisugused esitused teavet graafi struktuuri ega selle sümmeetriaomaduste kohta.
Graafe osutus võimalikuks identifitseerida ja esitada nende elementaarsete sümmeetriaomaduste tuvastamise teel saadud struktuurimudeli 
formula_4või graafi seosmaatriksi astendamise formula_24 näol, mis tuvastavad graafi struktuuri isomorfismi täpsusega. Graafide identifitseerimine on struktuurisemiootika üks põhiprobleeme.
Maksimaalne arv formula_7 ühesuguste väärtustega astmeelemendid formula_11 moodustavad tipupaaride "ekvivalentsusklassi", mida rühmateooria aspektist graafi "orbbiidiks" või "transitiivsuspiirkonnaks" nimetatakse. Sagedusvektorite formula_19 baasil korrastatud maatriksaste formula_24 tuvastab ka tipuorbiidid. Struktuurses aspektist nimetatakse orbiite "positsiooniklassideks" ehk "positsioonideks".
Rühmateoreetilisest aspektist on graafi struktuuri ja sümmeetriaomadusi teadaolevalt varem uurinud tipuorbiitide tasemel vaid B. Weisfeiler .
Oluline on, et "rühmateoreetilise ja maatriksastme lähenemiste teel saadud tulemused langevad kokku". Selline graafide identifitseerimise viis viib isomorfismiprobleemi ja Ulami hüpoteesi selgitamiseni ning on seotud graafide süsteemide moodustamisega.