En la teoría de grafos , una rama de las matemáticas, un grafo no dirigido se denomina grafo asimétrico si no tiene simetrías no triviales.
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
Formalmente, un automorfismo de un gráfico es una permutación p de sus vértices con la propiedad de que cualquier par de vértices u y v son adyacentes si y sólo si p ( u ) y p ( v ) son adyacentes. El mapeo de identidad de un gráfico sobre sí mismo es siempre un automorfismo, y se denomina automorfismo trivial del gráfico. Un gráfico asimétrico es un gráfico para el que no hay otros automorfismos.
Ejemplos de
Los gráficos asimétricos no triviales más pequeños tienen 6 vértices. [1] Las gráficas regulares asimétricas más pequeñas tienen diez vértices; existen grafos asimétricos de diez vértices que son 4-regulares y 5-regulares. [2] [3] Uno de los cinco gráficos cúbicos asimétricos más pequeños [4] es el gráfico de Frucht de doce vértices descubierto en 1939. [5] Según una versión reforzada del teorema de Frucht , hay infinitos gráficos cúbicos asimétricos.
Propiedades
La clase de grafos asimétricos se cierra bajo complementos : un grafo G es asimétrico si y solo si su complemento lo es. [1] Cualquier grafo asimétrico de n -vértices puede hacerse simétrico agregando y quitando un total de como máximo n / 2 + o ( n ) aristas. [1]
Gráficos aleatorios
La proporción de gráficos en n vértices con automorfismo no trivial tiende a cero a medida que n crece, lo que se expresa informalmente como " casi todos los gráficos finitos son asimétricos". En contraste, de nuevo informalmente, "casi todos los gráficos infinitos son simétricos". Más específicamente, los gráficos aleatorios infinitos contables en el modelo Erdős-Rényi son, con probabilidad 1, isomorfos al gráfico de Rado altamente simétrico . [1]
Árboles
El árbol asimétrico más pequeño tiene siete vértices: consta de tres caminos de longitudes 1, 2 y 3, vinculados en un punto final común. [6] En contraste con la situación de los gráficos, casi todos los árboles son simétricos. En particular, si un árbol se elige uniformemente al azar entre todos los árboles en n nodos etiquetados, entonces con probabilidad tendiendo a 1 a medida que n aumenta, el árbol contendrá unas dos hojas adyacentes al mismo nodo y tendrá simetrías intercambiando estas dos hojas. [1]
Referencias
- ^ a b c d e Erdős, P .; Rényi, A. (1963), "Asymmetric graphs" (PDF) , Acta Mathematica Hungarica , 14 (3): 295–315, doi : 10.1007 / BF01895716 , archivado desde el original (PDF) el 2017-07-06 , recuperado 2010-04-22.
- ^ Baron, G .; Imrich, W. (1969), "Asymmetrische reguläre Graphen", Acta Mathematica Academiae Scientiarum Hungaricae , 20 : 135-142, doi : 10.1007 / BF01894574 , MR 0238726.
- ^ Gewirtz, Allan; Hill, Anthony; Quintas, Louis V. (1969), "El número mínimo de puntos para grafos asimétricos regulares", Universidad Técnica Federico Santa María. Scientia , 138 : 103-111, MR 0266818.
- ^ Bussemaker, FC; Cobeljic, S .; Cvetkovic, DM; Seidel, JJ (1976), Investigación informática de gráficos cúbicos , informe EUT, 76-WSK-01, Departamento de Matemáticas y Ciencias de la Computación, Universidad Tecnológica de Eindhoven
- ^ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe". , Compositio Mathematica (en alemán), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804.
- ^ Quintas, Louis V. (1967), "Extrema concerniente a gráficos asimétricos", Journal of Combinatorial Theory , 3 (1): 57–82, doi : 10.1016 / S0021-9800 (67) 80018-8.