En el campo matemático de la teoría de grafos , el gráfico de Desargues es un grafo cúbico transitivo a la distancia con 20 vértices y 30 aristas. [1] Lleva el nombre de Girard Desargues , surge de varias construcciones combinatorias diferentes, tiene un alto nivel de simetría, es el único cubo parcial cúbico no plano conocido y se ha aplicado en bases de datos químicas.
Gráfico de desargues | |
---|---|
Lleva el nombre de | Gérard Desargues |
Vértices | 20 |
Bordes | 30 |
Radio | 5 |
Diámetro | 5 |
Circunferencia | 6 |
Automorfismos | 240 (S 5 × Z / 2 Z ) |
Número cromático | 2 |
Índice cromático | 3 |
Género | 2 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Cúbico Distancia-regular Hamiltoniano Bipartito Simétrico |
Tabla de gráficos y parámetros |
El nombre "gráfico de Desargues" también se ha utilizado para referirse a un gráfico de diez vértices, el complemento del gráfico de Petersen , que también se puede formar como la mitad bipartita del gráfico de Desargues de 20 vértices. [2]
Construcciones
Hay varias formas diferentes de construir el gráfico de Desargues:
- Es el gráfico de Petersen generalizado G (10, 3). Para formar el gráfico de Desargues de esta manera, conecta diez de los vértices en un decágono regular y conecta los otros diez vértices en una estrella de diez puntas que conecta pares de vértices a una distancia de tres en un segundo decágono. El gráfico de Desargues consta de los 20 bordes de estos dos polígonos junto con 10 bordes adicionales que conectan los puntos de un decágono con los puntos correspondientes del otro.
- Es el gráfico de Levi de la configuración de Desargues . Esta configuración consta de diez puntos y diez líneas que describen dos triángulos de perspectiva , su centro de perspectiva y su eje de perspectiva. El gráfico de Desargues tiene un vértice para cada punto, un vértice para cada línea y un borde para cada par de punto-línea incidente. El teorema de Desargues , que lleva el nombre del matemático francés del siglo XVII Gérard Desargues , describe un conjunto de puntos y líneas que forman esta configuración, y la configuración y el gráfico toman su nombre de ella.
- Es la cubierta doble bipartita del gráfico de Petersen , formada al reemplazar cada vértice del gráfico de Petersen por un par de vértices y cada borde del gráfico de Petersen por un par de bordes cruzados.
- Es el gráfico de Kneser bipartito H 5,2 . Sus vértices se pueden etiquetar por los diez subconjuntos de dos elementos y los diez subconjuntos de tres elementos de un conjunto de cinco elementos, con un borde que conecta dos vértices cuando uno de los conjuntos correspondientes es un subconjunto del otro. De manera equivalente, el gráfico de Desargues es el subgráfico inducido del hipercubo de 5 dimensiones determinado por los vértices de peso 2 y peso 3.
- El gráfico de Desargues es hamiltoniano y se puede construir a partir de la notación LCF : [5, −5,9, −9] 5 . Como Erdős conjeturó que para k positivo, el subgrafo del hipercubo 2k + unidimensional inducido por los vértices de peso k y k + 1 es hamiltoniano, la hamiltonicidad del gráfico de Desargues no es ninguna sorpresa. (También se deduce de la conjetura más fuerte de Lovász que, excepto por unos pocos contraejemplos conocidos, todos los gráficos transitivos de vértice tienen ciclos hamiltonianos).
Propiedades algebraicas
El gráfico de Desargues es un gráfico simétrico : tiene simetrías que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. Su grupo de simetría tiene orden 240 y es isomorfo al producto de un grupo simétrico en 5 puntos con un grupo de orden 2.
Se puede interpretar esta representación del producto del grupo de simetría en términos de las construcciones del gráfico de Desargues: el grupo simétrico en cinco puntos es el grupo de simetría de la configuración de Desargues, y el subgrupo de orden 2 intercambia los roles de los vértices que representan puntos. de la configuración de Desargues y los vértices que representan líneas. Alternativamente, en términos del gráfico de Kneser bipartito, el grupo simétrico en cinco puntos actúa por separado en los subconjuntos de dos y tres elementos de los cinco puntos, y la complementación de subconjuntos forma un grupo de orden dos que transforma un tipo de subconjunto en el otro. El grupo simétrico en cinco puntos es también el grupo de simetría del gráfico de Petersen, y el subgrupo de orden 2 intercambia los vértices dentro de cada par de vértices formados en la construcción de doble cobertura.
El gráfico de Petersen generalizado G ( n , k ) es transitivo al vértice si y solo si n = 10 y k = 2 o si k 2 ≡ ± 1 (mod n ) y es transitivo al borde solo en los siete casos siguientes: ( n , k ) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). [3] Por lo tanto, el gráfico de Desargues es uno de los siete gráficos de Petersen generalizados simétricos. Entre estos siete gráficos se encuentran el gráfico cúbico G (4, 1), el gráfico de Petersen G (5, 2), el gráfico de Möbius-Kantor G (8, 3), el gráfico dodecaédrico G (10, 2) y el gráfico de Nauru G (12, 5).
El polinomio característico del gráfico de Desargues es
Por lo tanto, el gráfico de Desargues es un gráfico integral : su espectro consta completamente de números enteros.
Aplicaciones
En química , el gráfico de Desargues se conoce como gráfico de Desargues-Levi ; se utiliza para organizar sistemas de estereoisómeros de compuestos de 5 ligandos . En esta aplicación, los treinta bordes del gráfico corresponden a pseudorotaciones de los ligandos. [4] [5]
Otras propiedades
El gráfico de Desargues tiene un número de cruce rectilíneo 6, y es el gráfico cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Es el único cubo parcial cúbico no plano conocido . [6]
El gráfico de Desargues tiene número cromático 2, índice cromático 3, radio 5, diámetro 5 y circunferencia 6. También es un gráfico hamiltoniano de 3 vértices y 3 de aristas . Tiene un grosor de libro 3 y un número de cola 2. [7]
Todos los cúbicos gráficos distancia regular son conocidos. [8] El gráfico de Desargues es uno de los 13 gráficos de este tipo.
El gráfico de Desargues se puede incrustar como un mapa regular dual auto- Petrie en la variedad no orientable del género 6, con caras decagonales.
Galería
Desargues el gráfico coloreado para resaltar varios ciclos.
El índice cromático del gráfico de Desargues es 3.
El número cromático del gráfico de Desargues es 2.
Referencias
- ^ Weisstein, Eric W. "Desargues Graph" . MathWorld .
- ^ Kagno, IN (1947), "Gráficos de Desargues y Pappus y sus grupos", American Journal of Mathematics , The Johns Hopkins University Press, 69 (4): 859–863, doi : 10.2307 / 2371806 , JSTOR 2371806.
- ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society , 70 (02): 211-218, doi : 10.1017 / S0305004100049811.
- ^ Balaban, AT; Fǎrcaşiu, D .; Bǎnicǎ, R. (1966), "Gráficos de múltiples desplazamientos 1, 2 en iones de carbonio y sistemas relacionados", Rev. Roum. Chim. , 11 : 1205
- ^ Mislow, Kurt (1970), "Papel de la pseudorrotación en la estereoquímica de las reacciones de desplazamiento nucleofílico", Acc. Chem. Res. , 3 (10): 321–331, doi : 10.1021 / ar50034a001
- ^ Klavžar, Sandi; Lipovec, Alenka (2003), "Cubos parciales como gráficos de subdivisión y gráficos de Petersen generalizados", Matemáticas discretas , 263 : 157-165, doi : 10.1016 / S0012-365X (02) 00575-7
- ^ Wolz, Jessica, Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Brouwer, AE ; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.