Saltar para o conteúdo

Grafo de Desargues

Origem: Wikipédia, a enciclopédia livre.
Grafo de Desargues


O grafo de Desargues
Nomeado em honra a Girard Desargues
vértices 20
arestas 30
Raio 5
Diâmetro 5
Cintura 6
Automorfismos 240 (S5× Z/2Z)
Número cromático 2
Índice cromático 3
Propriedades Cúbico
Hamiltoniano
simétrico
distância-regular
Bipartido

No campo da matemática da teoria dos grafos o grafo de Desargues é um grafo cúbico, distância-transitivo com 20 vértices e 30 arestas.[1] É nomeado em honra a Girard Desargues, surge a partir de diferentes construções combinatória, tem um elevado nível de simetria, é o único conhecido cubo parcial cúbico não-planar , e tem sido aplicado em bases de dados químicos.

O nome "grafo de Desargues" também tem sido usado para se referir ao complemento do grafo de Petersen[2].

Construções

[editar | editar código-fonte]

Existem várias maneiras diferentes de construir o grafo de Desargues:

  • É o grafo de Petersen generalizado G(10, 3). Para formar o grafo de Desargues desta forma, conecte dez dos vértices em um decágono regular, e conecte os outros dez vértices em uma estrela de dez pontas que conecta os pares de vértices a uma distância três em um segundo decágono. O grafo de Desargue consiste das 20 arestas destes dois polígonos juntamente com 10 arestas adicionais de pontos de conexão de um decágono para os pontos correspondentes do outro.
  • É o grafo de Levi da configuração de Desargues. Esta configuração é composta por dez pontos e dez linhas descrevendo dois triângulos em perspectiva, seu centro de perspectiva, e seu eixo de perspectiva. O grafo de Desargues tem um vértice para cada ponto, um vértice para cada linha, e uma aresta para cada par de linhas de ponto incidente. O teorema de Desargues, nomeado em honra ao matemático francês do século 17 Girard Desargues, descreve um conjunto de pontos e linhas que formam essa configuração, e a configuração e o grafo devem seu nome a ela.
  • É a cobertura bipartida dupla do grafo de Petersen, formada pela substituição de cada vértice do grafo de Petersen por um par de vértices e cada aresta do grafo de Petersen por um par de arestas cruzadas.
  • É o grafo de Kneser bipartido H5,2. Seus vértices podem ser rotulados pelos dez subconjuntos de dois elementos e os dez subconjuntos de três elementos de um conjunto de cinco elementos, com uma aresta conectando dois vértices quando um dos conjuntos correspondentes é um subconjunto do outro.
  • O grafo de Desargues é Hamiltoniano e pode ser construído pela notação LCF: [5,−5,9,−9]5

Propriedades algébricas

[editar | editar código-fonte]

O grafo de Desargues é um grafo simétrico: tem simetrias que levam qualquer vértice para qualquer outro vértice e qualquer aresta para qualquer outra aresta. Seu grupo de simetria tem ordem 240, e é isomórfico ao o produto de um grupo simétrico em 5 pontos, com um grupo de ordem 2.

Pode-se interpretar esta representação de produtos do grupo de simetria em termos de construções do grafo de Desargues: o grupo simétrico em cinco pontos é o grupo de simetria da configuração de Desargues, e o subgrupo de ordem-2 troca os papéis dos vértices que representam pontos da configuração de Desargues e os vértices que representam as linhas. Como alternativa, em termos do grafo bipartido de Kneser, o grupo simétrico em cinco pontos de age em separado sobre os subconjuntos de cinco pontos de dois elementos e de três elementos, e a complementação dos subconjuntos formam um grupo de ordem dois que transforma um tipo de subconjunto em outro. O grupo simétrico em cinco pontos é também o grupo de simetria do grafo de Petersen, e o subgrupo de ordem-2 troca os vértices dentro de cada par de vértices formados na construção da dupla cobertura.

O grafo de Petersen generalizado G(nk) é vértice-transitivo se e somente se n = 10 e k = 2 ou se k2 ≡ ±1 (mod n) e é aresta-transitivo somente nos seguintes sete casos: (nk) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5).[3] Assim, o grafo de Desargues é um dos apenas sete grafos de Petersen generalizados simétricos. Entre estes sete grafos estão o grafo cúbico G(4, 1), o grafo de Petersen G(5, 2), o grafo de Möbius–Kantor G(8, 3), o grafo dodecaédrico G(10, 2) e o grafo de Nauru G(12, 5).

O polinômio característico do grafo de Desargues é:

Portanto o grafo de Desargues é um grafo integral: seu espectro consiste inteiramente de inteiros.

Em química, o grafo de Desargues é conhecido como o grafo de Desargues-Levi; é utilizado para organizar sistemas de estereoisômeros de compostos 5-ligantes. Nesta aplicação, as trinta arestas do grafo correspondem a pseudorotações dos ligantes[4][5].

Outras propriedades

[editar | editar código-fonte]

O grafo de Desargues tem um número de cruzamento retilíneo 6, e é o menor grafo cúbico com este número de cruzamento (sequência A110507 na OEIS). É o único conhecido cúbico não planar cubo parcial[6] .

O grafo de Desargues tem um número cromático 2, índice cromático 3, raio 5, diâmetro 5 e cintura 6. É também um grafo hamiltoniano, 3-vértice-conectado, e 3-aresta-conectado.

Todos os grafos distância-regular cúbicos são conhecidos.[7] O grafo de Desargues é um destes 13 grafos.

Referências

  1. Weisstein, Eric W. «Desargues Graph». MathWorld (em inglês) 
  2. KAGNO, I. N. (1947). «Desargues' and Pappus' graphs and their groups». American Journal of Mathematics. 69 (4). The Johns Hopkins University Press. pp. 859–863. doi:10.2307/2371806 
  3. FRUCHT, R.; GRAVER, J. E.; WATKINS, M. E. (1971). «The groups of the generalized Petersen graphs». Proceedings of the Cambridge Philosophical Society. 70. pp. 211–218. doi:10.1017/S0305004100049811 .
  4. Balaban, A. T.; FǎRCAşIU, D.; BǎNICǎ, R. (1966). «Graphs of multiple 1, 2-shifts in carbonium ions and related systems». Rev. Roum. Chim. 11. 1205 páginas 
  5. MISLOW, Kurt (1970). «Role of pseudorotation in the stereochemistry of nucleophilic displacement reactions». Acc. Chem. Res. 3 (10). pp. 321–331. doi:10.1021/ar50034a001 
  6. KLAVŽAR, Sandi; LIPOVEC, Alenka (2003). «Partial cubes as subdivision graphs and as generalized Petersen graphs». Discrete Mathematics. 263. pp. 157–165. doi:10.1016/S0012-365X(02)00575-7 
  7. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.