Graafi kanooniline esitus

Allikas: Vikipeedia

Graafi kanooniline esitus (inglise: graph canonization) on graafi esitus mingil kaudsel, mitmesuguseid invariante kasutaval viisil – soovitavalt isomorfismi täpsusega.

Kanoonilise esituse probleemi püstitas Lazlo Babai [1] 1977. aastal.

Frank Harary[2] järgi on kanooniline esitus võimalik globaalinvariantide (polünoomid, spektrid jt) täieliku süsteemi baasil. A. Zõkov[3] on arvamusel, et see on lahendatav graafi tihedust, tsükleid, klikke jne iseloomustavate lokaalsete invariantide baasil. S. Locke[4] leiab, et isomorfismi testimiseks sobivad hästi kahendsüsteemis esitatud ülipikad 3-kuup-koodid. Kanooniliste vormide otsingud on jätkuvalt aktuaalsed[5]. Paraku ei sisalda niisugused esitused teavet graafi struktuuri ega selle sümmeetriaomaduste kohta.

Graafi semiootiline mudel aga kujutab endast niisugust kanoonilist esitist mis esitab nii graafi struktuuri kui ka selle sümmeetria omadusi.

Viited[muuda | redigeeri lähteteksti]

  1. L. Babai. 1983. Canonical labelling of graphs. – Proc. 15th ACM Symposium on Theory Computing 171–183.
  2. F. Harary. 1972. Graph Theory. Addison-Wesley. ISBN 0201027879
  3. A. Зыков. 1987. Основы теории графов. Наука.
  4. http//:www.math.fau.edu/locke/isotest
  5. Y. Gurevich. From Invariants to Canonization. – The Bull. of Euro. Assoc. for Comp. Sci., No. 63, 1997