Simetrični graf

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
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.

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

da velja:[1]

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 u1 in u2, 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 ab preslika v cd, ne pa v dc. 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[uredi | uredi kodo]

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[uredi | uredi kodo]

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[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]