Avtomorfizem grafa
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
urediKonstruiranje 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]
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Č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
urediVeč 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
urediVeč 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:
Glej tudi
urediSklici
uredi- ↑ Frucht (1938).
- ↑ Frucht (1949).
- ↑ 3,0 3,1 Luks (1982).
- ↑ 4,0 4,1 Mathon (1979).
- ↑ 5,0 5,1 Lubiw (1981).
- ↑ Köbler; Schöning; Torán (1993).
- ↑ 7,0 7,1 Torán (2004).
- ↑ McKay (1981).
- ↑ Junttila; Kaski (2007).
- ↑ Darga; Sakallah; Markov (2008).
- ↑ Katebi; Sakallah; Markov (2010).
- ↑ Di Battista; Tamassia; Tollis (1992).
- ↑ Eades; Lin (2000).
- ↑ Hong (2002).
Viri
uredi- Darga, Paul; Sakallah, Karem; Markov, Igor L. (Junij 2008), »Faster Symmetry Discovery using Sparsity of Symmetries« (PDF), Proceedings of the 45th Design Automation Conference (v angleščini): 149–154, doi:10.1145/1391469.1391509, ISBN 978-1-60558-115-6, arhivirano iz prvotnega spletišča (PDF) dne 26. januarja 2021, pridobljeno 10. julija 2019.
- Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), »Area requirement and symmetry display of planar upward drawings«, Discrete and Computational Geometry, 7 (1): 381–401, doi:10.1007/BF02187850
- Eades, Peter; Lin, Xuemin (2000), »Spring algorithms and symmetry«, Theoretical Computer Science, 240 (2): 379–405, doi:10.1016/S0304-3975(99)00239-X
- Frucht, Robert (1938), »Herstellung von Graphen mit vorgegebener abstrakter Gruppe«, Compositio Mathematica (v nemščini), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804
- Frucht, Robert (1949), »Graphs of degree three with a given abstract group«, Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987, arhivirano iz prvotnega spletišča dne 6. julija 2011, pridobljeno 10. julija 2019
- Hong, Seok-Hee (2002), »Drawing graphs symmetrically in three dimensions«, Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, zv. 2265, Springer-Verlag, str. 106–108, doi:10.1007/3-540-45848-4_16, ISBN 978-3-540-43309-5
- Junttila, Tommi; Kaski, Petteri (2007), »Engineering an efficient canonical labeling tool for large and sparse graphs« (PDF), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX07) (v angleščini).
- Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (Julij 2010), »Symmetry and Satisfiability: An Update« (PDF), Proc. Satisfiability Symposium (SAT) (v angleščini).
- Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287
- Lubiw, Anna (1981), »Some NP-complete problems similar to graph isomorphism«, SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600
- Luks, Eugene Michael (1982), »Isomorphism of graphs of bounded valence can be tested in polynomial time«, Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5
- Mathon, R. (1979), »A note on the graph isomorphism counting problem«, Information Processing Letters, 8: 131–132, doi:10.1016/0020-0190(79)90004-8
- McKay, Brendan (1981), »Practical Graph Isomorphism« (PDF), Congressus Numerantium (v angleščini), 30: 45–87, pridobljeno 14. aprila 2011.
- Torán, Jacobo (2004), »On the hardness of graph isomorphism« (PDF), SIAM Journal on Computing, 33 (5): 1093–1108, doi:10.1137/S009753970241096X, arhivirano iz prvotnega spletišča (PDF) dne 20. novembra 2008, pridobljeno 10. julija 2019
- Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1