Graafi struktuur

Graafi struktuur on graafi tippude ja tipupaaride omadus olla invariantselt seostatud, st organiseeritud mingil kindlal viisil. Graafi struktuur on isomorfsete graafide klassi täielik invariant.
Selgitusi.
Mõiste struktuur ümber valitseb segadus. Ühest küljest on see muutunud mingiks iga asja kohta käivaks ähmaseks omadussõnaks. Teisest küljest on see koosluse kindel karakteristik, küllaltki rangelt määratletud kategooria, st struktuur kui niisugune . Kolmandaks, on neid kes peavad õigeks rääkida vaid konkreetse objekti struktuurist, näiteks asutuse struktuur, kivimi struktuur, bioloogiline struktuur jne. Esimesed ja kolmandad ei tunnista struktuuri kui niisuguse defineerimist.
Graafi struktuurist räägitakse ka kui selle mingitest spetsiifilistest omadustest. Näiteks, graafi "algebralise struktuuri" all mõeldakse selle teatud algebralisi omadusi.
Rangelt võttes nimetatakse "struktuuriks" süsteemi abstraktsiooni, selle "skeletti", kus elemendid ja nendevahelised seosed on minetanud oma empiirilised tähendused ja vaatluse all on peamiselt nende organiseeritus ja sümmeetria omadused ("positsioonid"). Struktuur ise ongi kujutatav graafina ning seotud invariantsuse ja isomorfismiga. Graaf ise on paljuaspektiline objekt. Struktuuri kui niisugust uurib struktuurisemiootika.
"Struktuuri", "süsteemi", "invariandi" ja "sümmeetriaklassi" ehk "positsiooni" mõisted on lihtsalt ja piltlikult selgitatavad Rubiku kuubiku põhjal.
Kommentaarid Rubiku kuubiku kohta:
Nii on ka struktuuri üldine tähendus kujutatav graafidel.
Graafi struktuuri tuvastamine.
Graafi esitamiseks on kasutatud mitmesuguseid lokaalseid (tippe puudutavaid) ja globaalseid (graafitervikut puudutavaid) invariante. Niisugust lähenemist nimetatakse graafi kanooniliseks esitamiseks (inglise: "graph canonization") . Paraku ei sisalda seni teada olevad kanoonilised esitused teavet graafi struktuuri kohta. Graafi esitamisel tema automorfismide rühma põhjal tekib keerukama struktuuri puhul palju küsitavusi.
Graafi formula_1 struktuur formula_2 on identifitseeritav atribuut, formula_3. Identifikaatoriteks on tipupaaride formula_4 ümbruste ühisosi formula_5 kujutavate binaargraafide formula_6 invariandid .
Vastav algoritm formula_7 tuvastab: a) iga "mittenaabertippude paari" jaoks nendevahelise kauguse formula_8; b) iga "naabertippude paari" jaoks selle kuuluvuse vöösse suurusega formula_9; c) mõlemal juhul ka vastavat binaargraafi moodustavate tippude arv formula_10 ja servade arv formula_11.
Saadud invariandinelikute formula_12 ehk binaarmärkide korrastatud (dekomponeeritud) süsteem kujutab endast graafi struktuuri esitavat (kirjeldavat) semiootilist mudelit formula_13.
Graafi struktuuri uurimine tähendab selle mudeli formula_13 uurimist. Erinevate struktuuride arv võrdub mitteisomorfsete graafide arvuga. Struktuuride ekvivalentsuse tuvastamine kujutab endast vastavate mudelite ekvivalentsuse lihtsat fikseerimist.
Kommentaarid semiootiliste mudelite kohta:
Tegemist on graafide identifitseerimisega. Binaarmärke on kasulik täpsustada seosmaatriksit formula_18 korrutades (astendades) seda teatud astmeni formula_19. Seda tehes suurenevad nii selle elementide väärtused kui ka erinevate väärtuste arv. Suurenemine toimub vaid teatud astmeni formula_10, pärast seda see lakkab. Need väärtused kujutavad endast binaarmärke, mis tuvastavad tipupaari positsioone, st "binaarpositsioone". Nimetagem neid binaarmärke "produktiivseteks binaarmärkideks".
Põhimõte, et graafi struktuuri tuvastamine toimub "tipupaaride süvaidentifitseerimise printsiibil" saadava täieliku invariandi näol jääb kehtima .
Graafi struktuuri omadusi.
Semiootiline mudel formula_13 esitab selle klassi graafide ühist struktuuri. Graafide isomorfismi tuvastamine ei tähenda veel struktuuri tuvastamist, see kujutab endast vaid nende ekvivalentsuse kindlaksmääramist.
Struktuuri olulisemaid omadusi on sümmeetria. "Sümmeetria" on graafi tippude ja tipupaaride omadus jaotuda "orbiitideks", st "ekvivalentsusklassideks ehk positsioonideks". Sümmeetriaomadused, st "orbiidid (positsioonid)" on semiootilises mudelis äratuntavad kui binaarmärkide ekvivalentsusklassid. Äratuntavad on nii tipu- kui ka tipupaari orbiidid (positsioonid), sh viimase puhul serva- ja "mitteserva"' orbiidid. See lihtne moodus asendab ja katab nende tavapärast käsitlemist automorfismirühmade "AutG" abil .
Orbiitidel on oluline rolli graafi struktuuri uurimisel. On fikseeritud seaduspärasusi "sümmeetriaomaduste" ja "tugevregulaarsuse" vahel . Sümmeetriatunnuste (graafi orbiitide arvu ja nende võimsuste) baasil on välja töötatud "sümmeetriaomaduste klassifikatsioon". Esitatakse moodus sümmeetria mõõtmiseks. Ka asümmeetria on sümmeetriaomadus.
Igale tipupaari orbiidile (positsioonile) vastab üks "positsioonistruktuur". Selle moodustavad orbiiti kuuluvad tipupaarid ning see kujutab endast vahendit struktuuri nö varjatud külgede uurimiseks. Näiteks, on selgunud, et Folkmani graafi üheks positsioonistruktuuriks on Peterseni graaf, jne. "Varjatud külgi" on veel teisigi.