Grafo simètric
En el camp matemàtic de la teoria de grafos, un grafo G és simètric si, donat qualsevol parell de parells de vèrtiços adjacents o1—v1 i o2—v2 de G, existix un automorfisme
- f: V(G) → V(G)
tal que
- f(o1) = o2 and f(v1) = v2.[1]
En atres paraules, un grafo és simètric si el seu grup automórfico actua transitivamente sobre parells ordenats de vèrtiços adjacents (és dir, sobre les vores considerades com tenint una direcció).[2] Este grafo es denomina a voltes també 1-arc-transitivo.[2][3]
Per definició (ignorant o1 i o2), un grafo simètric sense vèrtiços aïllats també deu ser vèrtiç transitivo.[1] Ya que la definició anterior mapea una vora a l'atre, una grafo simètric també deu ser aresta transitivo. No obstant, un grafo aresta transitivo no és necessàriament simètric, ya que a—b pot mapear a c—d, pero no a d—c. Els grafos semi-simètrics, per eixemple, són aresta transitivos i regulars, pero no vèrtiç transitivos.
Cada grafo simètric conectat deu per lo tant ser al mateix temps vèrtiç transitivo i aresta transitivo, i lo contrari és cert per als grafos de grau impar.[3] No obstant, per als grafos de grau parell, existixen grafos conectats que són vèrtiç transitivos i aresta transitivos, pero no simètrics.[4] Tals grafos són cridats semi-transitivos.[5] el grafo semi-transitivo conectat més chicotet és el grafo de Holt, de grau 4 i en 27 vèrtiços.[1][6] Confusamente, alguns autors usen el terme "grafo simètric" parlant de grafos que són vèrtiç transitivos i aresta transitivos, pero no són arc transitivos. Una definició aixina inclouria els grafos semi-transitivos, que estan exclosos en virtut de la definició anterior.
Un grafo distancia-transitivo és aquell a on en lloc de considerar parells de vèrtiços adjacents (és dir, els vèrtiços separats per una aresta), la definició comprén dos parells de vèrtiços, cada u a la mateixa distància. Tals grafos són automàticament simètrics, per definició.[1]
Un t-arc és definit com una seqüència de t+1 vèrtiços, tal que dos vèrtiços consecutius qualssevol en la seqüència són adjacents, i qualsevol vèrtiç repetit està separat per lo manco 2 passos. Un grafo t-transitivo és un grafo tal que el grup automórfico actua transitivamente sobre t-arcs, pero no sobre (t+1)-arcs. Ya que 1-arcs són simplement arestes, cada grafo simètric de grau 3 o major deu ser t-transitivo per a alguna t, i el valor de t pot ser usat per a classificar els grafos simètrics. Per eixemple, la gaveta és 2-transitivo.[1]
Eixemples
La combinació de la condició de simetria en la restricció de que els grafos siguen cúbics (és dir, tots els vèrtiços tinguen grau 3) és molt restrictiva, i tals grafos són lo suficientment rars per a ser enumerats. El cens de Foster va incloure eixa llista.[7] El cens Foster va ser iniciat en 1930 per Ronald M. Foster mentres era amprat dels Laboratoris Bell,[8] i en 1988 (quan Foster tenia 92 anys[1]) el cens Foster actualisat (llistant tots els grafos simètrics cúbics de fins a 512 vèrtiços) va ser publicat en forma de llibre.[9] Els primers tretze elements de la llista són grafos simètrics cúbics de fins a 30 vèrtiços[10][11] (dèu d'ells són també distància-transitivos; les excepcions són com s'indica):
| Vèrtiços | Diàmetro | Cintura | Grafo | Notes |
|---|---|---|---|---|
| 4 | 1 | 3 | El grafo complet K4 | distància-transitivo, 2-transitivo |
| 6 | 2 | 4 | El grafo bipartito complet K3,3 | distància-transitivo, 3-transitivo |
| 8 | 3 | 4 | Els vèrtiços i les arestes del gaveta | distància-transitivo, 2-transitivo |
| 10 | 2 | 5 | El grafo de Petersen | distància-transitivo, 3-transitivo |
| 14 | 3 | 6 | El grafo de Heawood | distància-transitivo, 4-transitivo |
| 16 | 4 | 6 | El grafo de Möbius-Kantor | 2-transitivo |
| 18 | 4 | 6 | El grafo de Pape | distància-transitivo, 3-transitivo |
| 20 | 5 | 5 | Els vèrtiços i les arestes del dodecaedre | distància-transitivo, 2-transitivo |
| 20 | 5 | 6 | El grafo de Desargues | distància-transitivo, 3-transitivo |
| 24 | 4 | 6 | El grafo de Nauru (el grafo de Petersen generalisat G(12,5)) | 2-transitivo |
| 26 | 5 | 6 | El grafo F26A[11] | 1-transitivo |
| 28 | 4 | 7 | El grafo de Coxeter | distància-transitivo, 3-transitivo |
| 30 | 4 | 8 | El grafo de Tutte-Coxeter | distància-transitivo, 5-transitivo |
Atres grafos simètrics cúbics coneguts són el grafo de Dyck, el grafo de Foster i el grafo de Biggs–Smith. Els dèu grafos distancia-transitivos llistat dalt, junt en el grafo de Foster i el grafo de Biggs–Smith, són els únics grafos cúbics distància-transitivs.
Els grafos simètrics no cúbics inclouen cicles (de grau 2), grafos complets (de grau 4 o major quan tenen 5 o més vèrtiços), grafos hipercubos (de grau 4 o major quan tenen 16 o més vèrtiços), i els grafos formats pels vèrtiços i arestes del octaedre, icosaedre, cuboctaedro, and icosidodecaedro. El grafo de Rado és un eixemple de grafo simètric en vèrtiços infinits i grau infinit.
Vore també
Referències
- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 Biggs, Norman (1993). Algebraic Graph Theory, 2nd edició, Cambridge: Cambridge University Press, pp. 118–140. ISBN 0-521-45897-8.
- ↑ 2,0 2,1 (2001) Algebraic Graph Theory, Nova York: Springer, p. 59. ISBN 0-387-95220-9.
- ↑ 3,0 3,1 Babai (1996). Handbook of Combinatorics, Elsevier.
- ↑ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
- ↑ Gross, J.L. and Yellen, J. (2004). Handbook of Graph Theory, CRC Press, p. 491. ISBN 1-58488-090-2.
- ↑ (1981).«A grafo which is edge transitivo but not arc transitive».Journal of Graph Theory.5(2)
- 201–204.doi:10.1002/jgt.3190050210..
- ↑ Marston Conder, Trivalent symmetric grafos on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
- ↑ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
- ↑ "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
- ↑ Biggs, p. 148
- ↑ 11,0 11,1 Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.
Referències
- Este artícul conté una traducció derivada de «Grafo simétrico» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.