b'\n_START_ARTICLE_\nAvtomorfizem grafa\n_START_PARAGRAPH_\nAvtomorf\xc3\xadzem gr\xc3\xa1fa je v teoriji grafov oblika simetrije pri kateri se graf preslika vase in pri \xc4\x8demer se med njegovimi to\xc4\x8dkami ohranjajo enake povezave._NEWLINE_Formalno je avtomorfizem grafa G\xc2\xa0=\xc2\xa0(V,\xc2\xa0E) tak\xc5\xa1na permutacija \xcf\x83 mno\xc5\xbeice to\xc4\x8dk V, da par to\xc4\x8dk (u,\xc2\xa0v) tvori povezavo, \xc4\x8de in samo \xc4\x8de tudi par (\xcf\x83(u),\xc2\xa0\xcf\x83(v)) tvori povezavo. To pomeni izomorfizem grafa iz G nase. Avtomorfizmi se lahko na ta na\xc4\x8din definirajo tako za usmerjene grafe kot tudi za neusmerjene grafe. Kompozitum dveh avtomorfizmov je nov avtomorfizem in mno\xc5\xbeica 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\xc4\x8dnega grafa.\n_START_SECTION_\nRa\xc4\x8dunska kompleksnost\n_START_PARAGRAPH_\nKonstruiranje grupe avtomorfizmov je (glede na njeno ra\xc4\x8dunsko kompleksnost) vsaj tako te\xc5\xbeko kot re\xc5\xa1evanje problema izomorfizma grafov, pri \xc4\x8demer se dolo\xc4\x8da ali dva dana grafa odgovarjata preslikavi po to\xc4\x8dkah in preslikavi po povezavah. Grafa G in H sta izomorfna, \xc4\x8de in samo \xc4\x8de ima nepovezani graf, ki ga tvori disjunktna unija grafov G in H, avtomorfizem pri katerem se obe komponenti zamenjata. Dejansko je \xc5\xa1tetje avtomorfizmov v polinomskem \xc4\x8dasu enakovredno izomorfizmu grafov._NEWLINE_Problem avtomorfizma grafa je problem testiranja ali ima dani graf netrivialni avtomorfizem. Pripada razredu NP ra\xc4\x8dunske kompleksnosti. Podobno kot problem izomorfizma grafov ni znano ali zanj obstaja algoritem v polinomskem \xc4\x8dasu ali je NP-polni problem. Obstaja algoritem v polinomskem \xc4\x8dasu za re\xc5\xa1evanje problema avtomorfizma grafa za grafe katerih stopnja to\xc4\x8dk je omejena s konstanto. Problem avtomorfizma grafa ima polinomski \xc4\x8das glede na redukcijo mnogih na enega proti problemu izomorfizma grafov, obratna redukcija pa ni znana. Na drugi strani je znana ra\xc4\x8dunska te\xc5\xbeavnost kadar so avtomorfizmi omejeni na dolo\xc4\x8den na\xc4\x8din. Na primer dolo\xc4\x8devanje obstoja avtomorfizma brez negibnih to\xc4\x8dk (avtomorfizma pri \xc4\x8demer nobena to\xc4\x8dka ni fiksirana) je NP-polni problem, problem \xc5\xa1tetja tak\xc5\xa1nih avtomorfizmov pa je #P-poln.\n_START_SECTION_\nAlgoritmi, programje in uporabe\n_START_PARAGRAPH_\n\xc4\x8ceprav za splo\xc5\xa1ni problem avtomorfizma grafa algoritmi za najslab\xc5\xa1i polinomski \xc4\x8das niso znani, je iskanje grupe avtomorfizmov (in izpis nepreobilne mno\xc5\xbeice generatorjev) za mnoge velike grafe, ki se pojavljajo pri uporabah, dokaj enostavno. Za to nalogo je na razpolago ve\xc4\x8d odprtokodnih programskih orodij, na primer: NAUTY, BLISS in SAUCY. SAUCY in BLISS sta \xc5\xa1e posebej u\xc4\x8dinkovita za redke grafe. SAUCY lahko na primer sprocesira nekatere grafe z milijon to\xc4\x8dkami v nekaj sekundah. BLISS in NAUTY lahko tudi izvedeta kanoni\xc4\x8dno ozna\xc4\x8devanje, SAUCY pa je trenutno optimiziran za re\xc5\xa1evanje avtomorfizmov grafov. Pomembno opa\xc5\xbeanje je, da se lahko za graf na n to\xc4\x8dkah grupa avtomorfizmov navede z ne ve\xc4\x8d kot n-1 generatorji, zgoraj omenjeni programski paketi pa jam\xc4\x8dijo zadovoljivost te meje kot stranski u\xc4\x8dinek svojih algoritmov (minimalne mno\xc5\xbeice generatorjev je te\xc5\xbeje najti in v praksi niso posebej uporabne). Razvidno je tudi, da je celotna podpora (to je \xc5\xa1tevilo premaknjenih to\xc4\x8dk) vseh generatorjev omejena z linearno funkcijo n, ki je pomembna pri analizi izvajanja teh algoritmov. Vendar to \xc5\xa1e ni docela dolo\xc4\x8deno._NEWLINE_Med prakti\xc4\x8dne uporabe avtomorfizmov grafov spadajo risanje grafov in druge vizualizacijske naloge, re\xc5\xa1evanje struktuiranih primerov Booleove zadovoljivosti, ki izhajajo v kontekstu formalne verifikacije in logistike. Molekularna simetrija lahko napove ali pojasni kemi\xc4\x8dne zna\xc4\x8dilnosti.\n_START_SECTION_\nPrikaz simetrij\n_START_PARAGRAPH_\nVe\xc4\x8d raziskovalcev vizualizacije grafov je raziskalo algoritme za risanje grafov na tak na\xc4\x8din, 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\xc4\x8dne risbe kadar je mogo\xc4\x8de, ali z eksplicitno identifikacijo simetrij in z njihovo pomo\xc4\x8djo vodenjem postavitve to\xc4\x8dk v risbi. Vedno ni mo\xc5\xbeno so\xc4\x8dasno prikazati vseh simetrij grafa, zato je treba izbrati katere simetrije se prika\xc5\xbeejo in katere se pri vizualizaciji izpustijo.'