En la matematika kampo de grafeteorio, aŭtomorfismo de grafeo estas formo de simetrio en kiu la grafeo estas mapita sur si mem konservante la rand-vertican konekteblecon.
#000001
Formale, aŭtomorfismo de grafeo G
V, E) estas permutaĵo σ de la verticaro V, tia ke la paro de verdglacioj ( u, v) formas randon se kaj nur se la paro (σ ( u), σ ( v) ankaŭ formas randon.
Tio estas, ĝi estas grafeizomorfio de G ĝis si mem.
Aŭtomorfismoj povas esti difinitaj laŭ tiu maniero kaj por direktitaj grafeoj kaj por senplanaj grafeoj.
La kunmetaĵo de du aŭtomorfismoj estas alia aŭtomorfismo, kaj la aro de aŭtomorfismoj de antaŭfiksita grafeo, sub la kunmetaĵoperacio, formas grupon, la aŭtomorfismogrupon de la grafeo.
En la kontraŭa direkto, de la teoremo de Frucht, ĉiuj grupoj povas esti reprezentitaj kiel la aŭtomorfismogrupo de ligita grafeo - efektive, de kuba grafeo.
#000002
2 Algoritmoj, softvaro kaj aplikoj
4 Grafeofamilioj difinite memstare aŭtomorfismoj
#000003
Konstrui la aŭtomorfismogrupon estas almenaŭ same malfacila (laŭ ĝia komputadokomplekseco) kiel solvado de la grafean izomorfioproblemo, determinante ĉu du antaŭfiksitaj grafeoj korespondas vertico-por-verticon kaj rando-por-randon.
Por, G kaj H estas izomorfa se kaj nur se la nekohera grafeo formita per la disan union de grafeoj G kaj H havas aŭtomorfismon kiu interŝanĝas la du komponentojn.
#000004
La grafea aŭtomorfismoproblemo estas la problemo de testado ĉu grafeo havas nesensignifan aŭtomorfismon.
Ĝi apartenas al la klaso NP de komputadokomplekseco.
Simila al la grafea izomorfioproblemo, estas nekonate ĉu ĝi havas polinomtempan algoritmon aŭ ĝi estas Np-kompleta.
Ekzistas polinomtempa algoritmo por solvado de la grafean aŭtomorfismoproblemo por grafeoj kie verticgradoj estas saltitaj per konstanto (Luks 1982).
Estas konata ke la grafea aŭtomorfismoproblemo estas polinomtempa kvanto-unu reduktebla al la grafea izomorfioproblemo, sed la inversa redukto estas nekonataj.
#000005
Dum neniuj plej malbonkazaj polinomtempaj algoritmoj estas konataj pro la generalo Graph Automorphism-problemo, trovi la aŭtomorfismogrupon (kaj elprinti iredundant-aron de generatoroj) por multaj grandaj grafeoj ekesti en aplikoj estas sufiĉe facilaj.
Pluraj malfermfontaj softvarilo-estas haveblaj por tiu tasko, inkluzive de NAUTW, [8]
IMPERTINENTA kaj FELIĈAĴO estas precipe efika por malabundaj grafeoj, ekz., Saucy prilaboras kelkajn grafeojn kun milionoj da verdglacioj en nuraj sekundoj.
Tamen, FELIĈAĴO kaj NAUTW ankaŭ povas produkti Canonical Labeling, dum Saucy estas nuntempe optimumigita por solvado de Graph Automorphism.
Grava observado estas ke por grafeo sur n verdglacioj, la aŭtomorfismogrupo povas esti precizigita per ne pli ol n generatoroj, kaj ĉi-supraj programarpakaĵoj estas garantiitaj por kontentigi tion ligitan kiel kromefiko de siaj algoritmoj (minimumaj aroj de generatoroj estas pli malfacilaj trovi kaj ne estas precipe utilaj en praktiko).
Ankaŭ ŝajnas ke la totala subteno (t.e., la nombro da verdglacioj moviĝis) de ĉiuj generatoroj estas limigita per lineara funkcio de n, kiu estas grava en rultempa analizo de tiuj algoritmoj.
Tamen, tio ne estis establita por fakto, en marto 2012.
#000006
Praktikaj aplikoj de Graph Automorphism inkluzivas grafeodesegnaĵon kaj aliajn bildigtaskojn, solvante strukturitajn kazojn de Boolean Satisfiability ekestanta en la kunteksto de Formala konfirmo kaj Loĝistiko.
Molekula simetrio povas antaŭdiri aŭ klarigi kemiajn trajtojn.
#000007
Pluraj grafeas tirantajn esploristojn esploris algoritmojn por desegnaĵografoj laŭ tia maniero ke la aŭtomorfismoj de la grafeo iĝas videblaj kiel simetrioj de la desegnaĵo.
Tio povas esti farita aŭ uzante metodon kiu ne estas dizajnita ĉirkaŭ simetrioj, sed tio aŭtomate generas simetriajn desegnaĵojn kiam eble, [12] aŭ eksplicite identigante simetriojn kaj uzante ilin por gvidi verticallokigon en la desegnaĵo.
Estas ne ĉiam eble elmontri ĉiujn simetriojn de la grafeo samtempe, tiel ke povas esti necese elekti kiujn simetriojn por montri kaj kiu foriri nebildigita.
#000008
Pluraj familioj de grafeoj estas difinitaj havante certajn specojn de aŭtomorfismoj:
#000009
Inkludrilatoj inter tiuj familioj estas indikitaj per la sekva tablo:
#000011