Avtomorfizem grafa

Iz Wikipedije, proste enciklopedije

Avtomorfízem gráfa je v teoriji grafov oblika simetrije pri kateri se graf preslika vase in pri čemer se med njegovimi točkami ohranjajo enake povezave.

Formalno je avtomorfizem grafa G = (V, E) takšna permutacija σ množice točk V, da par točk (u, v) tvori povezavo, če in samo če tudi par (σ(u), σ(v)) tvori povezavo. To pomeni izomorfizem grafa iz G nase. Avtomorfizmi se lahko na ta način definirajo tako za usmerjene grafe kot tudi za neusmerjene grafe. Kompozitum dveh avtomorfizmov je nov avtomorfizem in množica avtomorfizmov danega grafa pod operacijo kompozituma tvori grupo, grupo avtomorfizmov grafa. V obratni smeri se po Fruchtovem izreku lahko vse grupe predstavijo kot grupa avtomorfizmov povezanega grafa in to kubičnega grafa.[1][2]

Računska kompleksnost[uredi | uredi kodo]

Konstruiranje grupe avtomorfizmov je (glede na njeno računsko kompleksnost) vsaj tako težko kot reševanje problema izomorfizma grafov, pri čemer se določa ali dva dana grafa odgovarjata preslikavi po točkah in preslikavi po povezavah. Grafa G in H sta izomorfna, če in samo če ima nepovezani graf, ki ga tvori disjunktna unija grafov G in H, avtomorfizem pri katerem se obe komponenti zamenjata.[3] Dejansko je štetje avtomorfizmov v polinomskem času enakovredno izomorfizmu grafov.[4]

Risba Petersenovega grafa prikazuje podgrupo njegovih simetrij, izomorfnih diedrski grupi D5, graf pa ima dodatne simetrije, ki jih risba ne prikazuje. Ker je ta graf simetričen, so na primer vse njegove povezave enakovredne.

Problem avtomorfizma grafa je problem testiranja ali ima dani graf netrivialni avtomorfizem. Pripada razredu NP računske kompleksnosti. Podobno kot problem izomorfizma grafov ni znano ali zanj obstaja algoritem v polinomskem času ali je NP-polni problem.[5] Obstaja algoritem v polinomskem času za reševanje problema avtomorfizma grafa za grafe katerih stopnja točk je omejena s konstanto.[3] Problem avtomorfizma grafa ima polinomski čas glede na redukcijo mnogih na enega proti problemu izomorfizma grafov, obratna redukcija pa ni znana.[4][6][7] Na drugi strani je znana računska težavnost kadar so avtomorfizmi omejeni na določen način. Na primer določevanje obstoja avtomorfizma brez negibnih točk (avtomorfizma pri čemer nobena točka ni fiksirana) je NP-polni problem, problem štetja takšnih avtomorfizmov pa je #P-poln.[5][7]

Algoritmi, programje in uporabe[uredi | uredi kodo]

Čeprav za splošni problem avtomorfizma grafa algoritmi za najslabši polinomski čas niso znani, je iskanje grupe avtomorfizmov (in izpis nepreobilne množice generatorjev) za mnoge velike grafe, ki se pojavljajo pri uporabah, dokaj enostavno. Za to nalogo je na razpolago več odprtokodnih programskih orodij, na primer: NAUTY,[8] BLISS[9] in SAUCY.[10][11] SAUCY in BLISS sta še posebej učinkovita za redke grafe. SAUCY lahko na primer sprocesira nekatere grafe z milijon točkami v nekaj sekundah. BLISS in NAUTY lahko tudi izvedeta kanonično označevanje, SAUCY pa je trenutno optimiziran za reševanje avtomorfizmov grafov. Pomembno opažanje je, da se lahko za graf na n točkah grupa avtomorfizmov navede z ne več kot n-1 generatorji, zgoraj omenjeni programski paketi pa jamčijo zadovoljivost te meje kot stranski učinek svojih algoritmov (minimalne množice generatorjev je težje najti in v praksi niso posebej uporabne). Razvidno je tudi, da je celotna podpora (to je število premaknjenih točk) vseh generatorjev omejena z linearno funkcijo n, ki je pomembna pri analizi izvajanja teh algoritmov. Vendar to še ni docela določeno.

Med praktične uporabe avtomorfizmov grafov spadajo risanje grafov in druge vizualizacijske naloge, reševanje struktuiranih primerov Booleove zadovoljivosti, ki izhajajo v kontekstu formalne verifikacije in logistike. Molekularna simetrija lahko napove ali pojasni kemične značilnosti.

Prikaz simetrij[uredi | uredi kodo]

Zgled najmanjšega asimetričnega grafa.

Več raziskovalcev vizualizacije grafov je raziskalo algoritme za risanje grafov na tak način, da avtomorfizmi grafa postanejo vidni kot simetrije risbe. To se lahko naredi ali z uporabo metode, ki ni narejena okrog simetrij, vendar samodejno generira simetrične risbe kadar je mogoče,[12][13] ali z eksplicitno identifikacijo simetrij in z njihovo pomočjo vodenjem postavitve točk v risbi.[14] Vedno ni možno sočasno prikazati vseh simetrij grafa, zato je treba izbrati katere simetrije se prikažejo in katere se pri vizualizaciji izpustijo.

Družine grafov definirane po svojih avtomorfizmih[uredi | uredi kodo]

Več družin grafov je definiranih z značilnostjo določenih tipov avtomorfizmov:

  • asimetrični graf je neusmerjeni graf le s trivialnim avtomorfizmom.
  • po točkah prehodni graf je neusmerjeni graf v katerem se lahko vsaka točka z avtomorfizmom preslika v katerokoli drugo točko.
  • po povezavah prehodni graf je neusmerjeni graf v katerem se lahko vsaka povezava z avtomorfizmom preslika v katerokoli drugo povezavo.
  • simetrični graf je graf v katerem se lahko vsak par sosednjih točk z avtomorfizmom preslika v katerikoli drug par točk.
  • po razdaljah prehodni graf je graf v katerem se lahko vsak par točk z avtomorfizmom preslika v drug par točk, ki je oddaljen za enako razdaljo.
  • polsimetrični graf je graf, ki je povezavnoprehoden ni pa točkovnoprehoden..
  • polprehodni graf je graf, ki je točkovno in povezavnoprehoden ni pa simetričen.
  • poševnosimetrični graf je usmerjeni graf skupaj s permutacijo σ na točkah, ki preslikavajo povezave na povezave, pri čemer zamenjujejo smer vsake povezave. Poleg tega mora σ biti involucija.

Vključitev sorodnosti med temi družinami prikazuje naslednja razpredelnica:

Skelet dodekaedra
Skelet dodekaedra
Šrikhandov graf
Šrikhandov graf
Paleyjev graf
Paleyjev graf
razdaljnoprehodni razdaljnoregularni krepkoregularni
graf F26A
graf F26A
Naurujski graf
Naurujski graf
simetrični (ločnoprehodni) t-prehodni, t ≥ 2
(če povezan)
Holtov graf
Holtov graf
Folkmanov graf
Folkmanov graf
polni dvodelni graf K3,5
polni dvodelni graf K3,5
točkovno in povezavnoprehodni povezavnoprehodni in regularni povezavnoprehodni
Skelet prisekanega tetraedra
Skelet prisekanega tetraedra
Fruchtov graf
Fruchtov graf
točkovnoprehodni regularni
Skelet tristrane prizme
Skelet tristrane prizme
Cayleyjev graf

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  1. ↑ Frucht (1938).
  2. ↑ Frucht (1949).
  3. ↑ 3,0 3,1 Luks (1982).
  4. ↑ 4,0 4,1 Mathon (1979).
  5. ↑ 5,0 5,1 Lubiw (1981).
  6. ↑ Köbler; Schöning; Torán (1993).
  7. ↑ 7,0 7,1 Torán (2004).
  8. ↑ McKay (1981).
  9. ↑ Junttila; Kaski (2007).
  10. ↑ Darga; Sakallah; Markov (2008).
  11. ↑ Katebi; Sakallah; Markov (2010).
  12. ↑ Di Battista; Tamassia; Tollis (1992).
  13. ↑ Eades; Lin (2000).
  14. ↑ Hong (2002).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]

Pridobljeno iz »https://sl.wikipedia.org/w/index.php?title=Avtomorfizem_grafa&oldid=6060518«