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:

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.

$f:V(G)\to V(G)\!\,,$

da velja:

$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). Takšen graf se včasih imenuje tudi 1-ločnoprehodni graf ali zastavnoprehodni graf.

Po definiciji, kjer se ne upošteva u₁ in u₂, mora biti simetrični graf brez izoliranih točk tudi točkovnoprehoden. 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. Vendar za vsako stopnjo obstaja povezani graf, ki je točkovno in povezavno prehoden, ni pa simetričen. Takšni grafi se imenujejo polprehodni grafi. Najmanjši povezani polprehodni graf je Holtov graf s stopnjo 4 in 27-imi točkami. 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.

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.

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. Fosterjev popis je v 1930-ih začel sestavljati Ronald Martin Foster kot uslužbenec Bellovih laboratorijev. Leta 1988 (ko je bil Foster star 92 let) je bil tedanji popis (z vsemi kubičnimi simetričnimi grafi z do 512 točkami) izdan v knjižni obliki. Prvih trinajst vnosov v seznamu so kubični simetrični grafi z do 30-imi točkami (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	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. Pri točkovnoprehodnih grafih pa je točkovna povezanost omejena z 2(d+1)/3.

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

Viri

• Babai, László (1996), »Automorphism groups, isomorphism, reconstruction«, v Graham, Ronald Lewis; Grötschel, Martin; Lovász, László (ur.), Handbook of Combinatorics, Elsevier, COBISS 4105817, ISBN 0-444-88002-X, arhivirano iz prvotnega spletišča dne 11. junija 2010, pridobljeno 9. julija 2016
• Biggs, Norman Linstead (1993), Algebraic Graph Theory (2. izd.), Cambridge: Cambridge University Press, str. 118–140, COBISS 6409817, ISBN 0-521-45897-8
• Bouwer, Izak Zurk (1970), »Vertex and Edge Transitive, But Not 1-Transitive Graphs«, Canadian Mathematical Bulletin, 13: 231–237
• Conder, Marston; Dobcsanyi, Peter (2002), »Trivalent symmetric graphs on up to 768 vertices«, J. Combin. Math. Combin. Comput, 20: 41–63
• Foster, Ronald Martin (1932), »Geometrical Circuits of Electrical Networks«, Transactions of the American Institute of Electrical Engineers, 51: 309–317
• Foster, Ronald Martin; Bouwer, Izak Zurk; Chernoff, William W.; Monson, B.; Star, Z. (1988), The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs, ISBN 0-919611-19-2
• Godsil, Christopher David; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer, COBISS 10598233, ISBN 0-387-95220-9
• Gross, Jonathan Light; Yellen, Jay Edward (2004), Handbook of Graph Theory, CRC Press, COBISS 12822361, ISBN 1-58488-090-2
• Holt, Derek F. (1981), »A graph which is edge transitive but not arc transitive«, Journal of Graph Theory, 5 (2): 201–204, doi:10.1002/jgt.3190050210

Zunanje povezave

• Cubic symmetric graphs (The Foster Census) Arhivirano 2008-10-04 na Wayback Machine.. Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
• Conder, Marston (Avgust 2006), Trivalent (cubic) symmetric graphs on up to 2048 vertices (v angleščini), pridobljeno 20. avgusta 2009
• Weisstein, Eric Wolfgang. »Symmetric Graph«. MathWorld.