Graafide süsteem

Graafide süsteem on graafide hulk, mille elementide vahel on fikseeritud seosed. Graafe on süstematiseeritud erinevatest aspektidest. Tavaliselt on selleks mingi kindel struktuurne omadus, nagu planaarsus, regulaarsus, transitiivsus jne. 

Palju tööd on tehtud graafide loendamise alal nende tippude ja servade arvu järgi . Paraku ei ole need siiski veel süsteemid, sest neis ei ole fikseeritud vahetud seosed elementide (st graafide) vahel. Need seosed on leitud hilisemate uuringute käigus .

Olgu |V|-tipuliste graafide süsteemi mitteisomorfsete graafide arv p, sh sidusate arv p* ja märgistatute arv p**. Süsteemi graafid jagunevad servade arvu järgi m nivooks. Seoste arv graafide süsteemis q ja orbiitide arv q*.

Graafide süsteeme tippude arvu |V| järgi:
 Kolmetipulised: p = 4, p* = 2, p** = 8, m = 4, q = 3, q* = 6.
 Neljatipulised: p = 11, p* = 6, p** = 64, m = 7, q = 14, q* = 28.
 Viietipulised: p = 34, p* = 21, p** =1024, m = 11, q = 72, q* = 144.
 Kuuetipulised: p = 156, p* = 112, p** = 32768, m = 16, q = 572, q* = 1144.
 Seitsmetipulised: p = 1044, p* = 853, p** = 2097152, m = 22, q =?

Nivoode arv m vastab täisgraafi servade arvule pluss üks, mis tähendab tühigraafi (st 0 servaga graafi) olemasolu. Graafide arv p, kui: |V| = 8 – 12 344, kui |V| = 9 – 276 668, kui |V| = 10 – 12 005 168, kui |V| = 11 – 1 018 997 864 jne. Need aga ei moodusta süsteeme, sest seosed ei ole veel tuvastatud.

Graafide süsteemi atribuutika 
Graafide süsteemi moodustamine toimub graafide identifitseerimise baasil.
Igal graafil  on oma suurimad alamgraafid , mis saadakse serva  eemaldamisel  ja oma väikseimad ülemgraafid , mis saadakse serva lisamisel. Graafi alamgraafide arv võrdub servade arvuga ja ülemgraafide arv "mitteservade" arvuga. Saadud graafe nimetagem koos naabergraafideks . Nii on |V|-tipuliste graafide süsteemis iga nivoo seotud oma alumise ja ülemise naabernivooga.

Graafi tippude hulk jaguneb orbiitideks (st teatud tüüpi ekvivalentsusklassideks, transitiivsuspiirkondadeks). Nende raames jaguneb tipupaaride hulk omaette orbiitideks . Iga tipupaari orbiidi raames saadud naabergraafid on isomorfsed ja moodustavad isomorfismiklassi. Graafide süsteemi iga nivoo koosneb aga mitteisomorfsetest graafidest, st erinevaid isomorfismiklasse esindavatest graafidest, ehk struktuuridest.

Seega graafi igale tipupaari orbiidile (binaarorbiidile) vastab üks naaberstruktuur. Need vastavused kujutavad endast seoseid  ehk morfisme  naabernivoodel asuvate struktuuride (st isomorfismiklasse esindavate graafide) vahel. Seoste (morfismide)  fikseerimine graafide vahel muudab |V|-tipuliste graafide kogumi graafide süsteemiks .

Graafide süsteemi üldised omadused 

 Graafide süsteem  on kujutatav hariliku graafina (täpsemini, võrena).
 Kui nivoode arv m süsteemis on paarisarv (näiteks |V|=6 ja |V|=7 puhul), siis on võre bilateraaalselt sümmeetriline seda poolitava telje suhtes, mis lahutab graafid  nende täienditest .
 Kui nivoode arv m süsteemis on paaritu arv (näiteks |V|=4, |V|=5, |V|=8 ja |V|=9 puhul), siis on poolitavaks teljeks nivoo millel asuvad nii graafid  ja täiendid  kui ka isetäienduvad struktuurid.
 Morfism  on pööratav, graafi igal naaberstruktuuril  on "pöördorbiit", millele rakendatud "pöördmorfism"  taastab lähtegraafi .
 Süsteem  on otseselt seotud rekonstruktsiooniprobleemiga.

Tõenäosuslikud omadused 
 Juhuslikkus süsteemis  avaldub naaberstruktuuride valiku, st elementaarsete struktuurimuutuste näol. Tõenäosus on seotud graafi struktuuri sisemise mitmekesisuse, st orbiitidega.
 Suhe , kus n on binaarorbiidi indeks,  selle võimsus ja card vastavate tipupaaride arv struktuuris, määrab morfismi tõenäosuse struktuurilt  selle naaberstruktuurile .
 Morfismi tõenäosuse kõrval on süsteemis määratletav ka ülemineku tõenäosus  lähtestruktuurilt  mitte-naaberstruktuurile .
 Süsteemi üleminekutõenäosused  moodustavad statsionaarse markovi ahela.
 Struktuuri olekutõenäosus  süsteemis  iseloomustab selle olekut teiste struktuuride seas struktuurinivool. See avaldub kujul: , kus n on antud struktuuri (graafi) binaarorbiidi indeks,  on naaber ülemstruktuuri olekutõenäosus ja  selle morfismi tõenäosus.
 Struktuurinivool olevate struktuuride olekutõenäosuste summa võrdub ühega, .
 Struktuuri ja selle täiendi olekutõenäosused on võrdsed, .
 Olekutõenäosused  on ratsionaalarvud, kus selle väikseimad ühisnimetajad on otseselt seotud süsteemi astakuga |V|.
  jaotus struktuurinivool on parempoolse asümmeetriaga ja läheneb logaritmilisele normaaljaotusele

Algebralisi omadusi 
Morfismidel on süsteemis  oluline roll. Nii mõnigi algebraline struktuur iseloomustab selle süsteemi mõnda fragmenti või aspekti. Lihtsalt tõestatavad on järgmised propositsioonid.
 Süsteemi morfismide klass F moodustab kompositsiooni F&F mõttes aditiivse rühma .
 Süsteemi struktuuride klass GS koos morfismide klassiga F moodustab kategooria .

Rakendusi 
Esineb reaalseid süsteeme mille toimimist on võimalik kujutada selle struktuuri järkjärgulise muutumise näol ajas. Kui süsteemi  struktuure käsitleda reaalse süsteemi seisunditena  ajahetkel , siis kujutab suktsessioon , endast morfismide , kui sisendmõjutuste, poolt genereeritud dünaamilist või evolutsioonilist nähtust. Sellisel viisil on ülesehitatud elegantne kuid abstraktne ontogeneesimudel.

Niisugust lähenemist on rakendatud loodusliku koosluse evolutsiooni ehk tsönogeneesi uurimisel, kus selle seisundid olid esitatud graafidena .

Kokkuvõte 
Selliseid graafide süsteeme on praegu võimalik moodustada vaid algoritmilisel teel, täpsemini, semiootilise modelleerimise teel . Ei ole usutav, et keegi oleks üritanud seda teha kombinatoorika või algebra baasil, sest seal puudub vastav atribuutika. Ametlikult tuntakse vaid |V|-tipuliste graafide kogumeid, mitte süsteeme. Esimese, kuni kuuetipuliste graafide kogumi esitas Frank Harary 1969. aastal. 2004. aastal välja antud mahukas "Graafiatlases" on jõutud kuni seotsmetipuliste graafide diagrammide ja parameetrite kogumi esitamiseni. Küll aga on see teos tähelepanuväärne oma mahu (üle 10 000 graafi), graafide klassifitseerimise ja parameetrite aspektist .

Vaata ka 
 Graafide identifitseerimine
 Semiotic modelling of the graph systems (PDF)

Viited

Välislingid 
 Identification and systemization of the graphs (pdf)

Matemaatika
Graafiteooria