Graafi invariant: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
PResümee puudub |
täiendatud |
||
4. rida:
Struktuur kui niisugune ise on esitatav graafina '''G''', kus [[isomorfism|isomorfsed graafid]] omavad ühesugust struktuuri.
Struktuuri peamisteks karakteristikuteks on selle [['''graafi sümmeetria|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 seosmaatriks]]i astendamise teel. Korrutada algne seosmaatriks <math>E^1</math> iseendaga, kus <math>E^1\cdot E^1= E^2</math> ning <math>E^{n-1}\cdot E^1= E^n</math> kusjuures iga astme <math>n</math> korral fikseerida erinevate binaarmärkide <math>e^n_{i,j}</math> arv <math>p</math> maatriksis <math> E^n</math>, mis reeglina suureneb.
Tipupaariorbiitide basil korrastatud korrutis <math> E^n</math> on isomorfsete graafide täielik [[invariant]] <ref> John-Tagore Tevet. (2014). ''Semiotic modeling of the structure''. ISBN 9871503367456. Amazon Books </ref>.
Graafi [[invariant|invariandid]] jagunevad ''globaalseteks'' (graafi tervikut iseloomustavateks) ja ''lokaalseteks'' (näiteks, üksikuid tippe ja tipupaare iseloomustavateks).
39. rida ⟶ 42. rida:
* ''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 [[struktuur]]i [[graafi orbiit|orbiitide]] ja [[isomorfism]]i täpsusega <ref>
== Algoritmilisest keerukusest ==
| |||