Simetrični graf

Simetrični graf (ali ločnoprehodni graf) G je v teoriji grafov graf pri katerem za dana dva para sosednjih točk u₁—v₁ in u₂—v₂ obstaja takšen avtomorfizem:

${\displaystyle f:V(G)\to V(G)\!\,,}$

Petersenov graf je (kubični) simetrični graf. Vsak par sosednjih točk se lahko preslika v drugega z avtomorfizmom, ker se lahko vsak obroč s petimi točkami preslika v drugega.

da velja:^[1]

${\displaystyle f(u_{1})=u_{2}\,{\text{ in }}\,f(v_{1})=v_{2}\!\,.}$

Graf je simetričen, če njegova grupa avtomorfizmov deluje prehodno nad urejenimi pari sosednjih točk – nad povezavami kot, če bi imele smer).^[2] Takšen graf se včasih imenuje tudi 1-ločnoprehodni graf^[2] ali zastavnoprehodni graf.^[3]

Po definiciji, kjer se ne upošteva u₁ in u₂, mora biti simetrični graf brez izoliranih točk tudi točkovnoprehoden.^[1] Ker zgornja definicija preslikuje eno povezavo v drugo, mor simetrični graf biti tudi povezavnoprehoden. Vendar točkovnoprehoden graf ni nujno simetričen, saj se lahko a—b preslika v c—d, ne pa v d—c. Polsimetrični grafi so na primer povezavnoprehodni in regularni, niso pa točkovnoprehodni.

Vsak povezani simetrični graf mora biti tako točkovno kot tudi povezavnoprehoden. Obratno tudi velja za grafe z liho stopnjo.^[3] Vendar za vsako stopnjo obstaja povezani graf, ki je točkovno in povezavno prehoden, ni pa simetričen.^[4] Takšni grafi se imenujejo polprehodni grafi.^[5] Najmanjši povezani polprehodni graf je Holtov graf s stopnjo 4 in 27-imi točkami.^[1][6] Nekateri avtorji rabijo izraz »simetrični graf« za grafe, ki so točkovno in povezavnoprehodni in ne ločnoprehodni. Takšna definicija bi vključevala polprehodne grafe, ki jih zgornja definicija izključuje.

V razdaljnoprehodnem grafu se namesto urejenih parov sosednjih točk (točki, ki sta narazen za razdaljo 1) v definiciji rabita dva para točk, ki sta narazen za enako razdaljo. Takšni grafi so avtomatično simetrični po definiciji.^[1]

t-lok je zaporedje takšnih t+1 točk, da sta dve zaporedni točki v zaporedju sosednji in s ponovljenimi točkami narazen za več kot 2 koraka. t-prehodni graf je graf v katerem grupa avtomorfizmov deluje prehodno nad t-loki, ne pa nad (t+1)-loki. Ker so 1-loki preprosto povezave, mora vsak simetrični graf stopnje 3 ali več biti t-prehoden za poljubni t, vrednost t pa se lahko uporabi za nadaljnjo klasifikacijo simetričnih grafov. Kocka je na primer 2-prehodna.^[1]

Zgledi

S kombinacijo pogoja simetričnosti in omejitve, da so grafi kubični (vse točke imajo stopnjo 3), se dobi dokaj strog pogoj in takšni grafi so dovolj redki za njihov izpis. Fosterjev popis in njegove razširitve dajo takšne sezname.^[7] Fosterjev popis je v 1930-ih začel sestavljati Ronald Martin Foster kot uslužbenec Bellovih laboratorijev^[8]. Leta 1988 (ko je bil Foster star 92 let^[1]) je bil tedanji popis (z vsemi kubičnimi simetričnimi grafi z do 512 točkami) izdan v knjižni obliki.^[9] Prvih trinajst vnosov v seznamu so kubični simetrični grafi z do 30-imi točkami^[10][11] (deset od njih je tudi razdaljnoprehodnih (RP); izjeme so naznačene, k-LP – »k-ločnoprehoden«):

točke	premer	notranji obseg	graf	opombe
4	1	3	polni graf K4 (tetraedrski graf)	RP, 2-LP
6	2	4	polni dvodelni graf K3,3	RP, 3-LP
8	3	4	kockin graf	RP, 2-LP
10	2	5	Petersenov graf	RP, 3-LP
14	3	6	Heawoodov graf	RP, 4-LP
16	4	6	Möbius-Kantorjev graf	2-LP
18	4	6	Paposov graf	RP, 3-LP
20	5	5	dodekaedrski graf	RP, 2-LP
20	5	6	Desarguesov graf	RP, 3-LP
24	4	6	Naurujski graf (posplošeni Petersenov graf GP(12,5))	2-LP
26	5	6	F26A[11]	1-LP
28	4	7	Coxetrov graf	RP, 3-LP
30	4	8	Tutte-Coxetrov graf	RP, 5-LP

Drugi dobro znani kubični simetrični grafi so: Dyckov graf, Fosterjev graf in Biggs-Smithov graf. Deset razdaljnoprehodnih grafov navedenih v razpredelnici skupaj s Fosterjevim grafom in Biggs-Smithovim grafom predstavlja množico edinih kubičnih razdaljnoprehodnih grafov.

Nekubični simetrični grafi so: ciklični grafi (stopnje 2), polni grafi (stopnje 4 ali več na 5-ih ali več točkah), hiperkockin graf (stopnje 4 ali več na 16-ih ali več točkah), platonska in arhimedska grafa: oktaedrski, ikozaedrski, kubooktaedrski in ikozidodekaedrski graf. Radojev graf predstavlja primer simetričnega grafa z neskončno mnogo točkami in neskončno stopnjo.

Značilnosti

Točkovna povezanost simetričnega grafa je vedno enaka stopnji d.^[3] Pri točkovnoprehodnih grafih pa je točkovna povezanost omejena z 2(d+1)/3.^[2]

t-prehodni graf stopnje 3 ali več ima notranji obseg vsaj 2(t–1). Ne obstajajo pa končni t-prehodni grafi stopnje 3 ali več za t ≥ 8. V primeru stopnje točno enake 3 (kubični simetrični grafi) ni nobenega za t ≥ 6.

Glej tudi

• algebrska teorija grafov
• galerija poimenovanih grafov
• regularna preslikava