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 .
Formalmente, un automorfismo de un grafo es una permutación p de sus vértices con la propiedad de que dos vértices cualesquiera u y v son adyacentes si y solo si p ( u ) y p ( v ) son adyacentes. La aplicación de identidad de un grafo es siempre un automorfismo y se denomina automorfismo trivial del grafo. Un grafo asimétrico es un grafo para el cual no existen otros automorfismos.
Nótese que el término "gráfico asimétrico" no es una negación del término " gráfico simétrico ", ya que este último se refiere a una condición más fuerte que poseer simetrías no triviales.
Los grafos asimétricos no triviales más pequeños tienen 6 vértices. [1] Los grafos asimétricos regulares más pequeños tienen diez vértices; existen grafos asimétricos de 10 vértices que son 4-regulares y 5-regulares . [2] [3] Uno de los cinco grafos cúbicos asimétricos más pequeños [4] es el grafo de Frucht de doce vértices descubierto en 1939. [5] Según una versión reforzada del teorema de Frucht , hay infinitos grafos cúbicos asimétricos.
La clase de grafos asimétricos está cerrada bajo complementos : un grafo G es asimétrico si y sólo si su complemento es. [1] Cualquier grafo asimétrico de n vértices puede hacerse simétrico añadiendo y quitando un total de como máximo n /2 + o( n ) aristas. [1]
La proporción de grafos en n vértices con un automorfismo no trivial tiende a cero a medida que n crece, lo que se expresa informalmente como " casi todos los grafos finitos son asimétricos". En contraste, nuevamente de manera informal, "casi todos los grafos infinitos tienen simetrías no triviales". Más específicamente, los grafos aleatorios infinitos numerables en el modelo de Erdős–Rényi son, con probabilidad 1 , isomorfos al grafo de Rado altamente simétrico . [1]
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] A diferencia de la situación de los grafos, casi todos los árboles son simétricos. En particular, si se elige un árbol de manera uniforme al azar entre todos los árboles en n nodos etiquetados, entonces, con una probabilidad que tiende a 1 a medida que n aumenta, el árbol contendrá unas dos hojas adyacentes al mismo nodo y tendrá simetrías que intercambien estas dos hojas. [1]
