Grafo fortemente regular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo fortemente regular
Paley13.svg
O Grafo Paley de ordem 13, um grafo fortemente regular com parâmetros gfr(13,6,2,3).
Famílias de grafos definidos por seus automorfismos
distância-transitivo \rightarrow distância-regular \leftarrow fortemente regular
\downarrow
simétrico (arco-transitivo) \leftarrow t-transitivo, t ≥ 2 .
\downarrow
(se conectado)
transitivo nos vértices e nas arestas \rightarrow aresta-transitivo e regular \rightarrow aresta-transitivo
\downarrow \downarrow
vértice-transitivo \rightarrow regular
\uparrow
grafo de Cayley anti-simétrico assimétrico

Na teoria dos grafos, uma disciplina dentro da matemática, um grafo fortemente regular é definido como se segue. Seja G = (V,E) um grafo regular com v vértices e grau k. G é dito ser fortemente regular se houver também inteiros λ e μ tais que:

Um grafo deste tipo é dito às vezes ser um gfr(v,k,λ,μ).

Alguns autores excluem grafos que satisfazem a definição trivial, ou seja, os grafos que são a união disjunta de um ou mais grafos completos de tamanho igual, e os seus complementares, os grafos de Turan.

Um grafo fortemente regular é um grafo distância-regular com diâmetro 2, mas somente se μ não é zero.

Propriedades[editar | editar código-fonte]

  • Os quatro parãmetros em um grs(v,k,λ,μ) não são independentes, como é fácil mostrar que:
(v-k-1)\mu = k(k-\lambda-1)
  • Seja I denotando a matriz identidade (de ordem v) e faça-se J denotar a matriz cujas entradas são todas iguais a 1. A matriz de adjacência A de um grafo fortemente regular satisfaz as seguintes propriedades:
    • A\times J = kJ
      (Esta é uma reafirmação trivial da exigência para os graus de vértices).
    • {A}^{2} + (\mu-\lambda){A} + (\mu-k){I} = \mu {J}
      (O primeiro termo indica o número de caminhos de 2-passos de cada vértice para todos os vértices. Para os pares de vértices diretamente ligados por uma aresta, a equação reduz-se o número de tais caminhos em 2 passos sendo igual a \lambda. Para os pares de vértices não directamente ligados por uma aresta, a equação reduz-se ao número de tais caminhos em 2 passos sendo igual a \mu. Para os auto-pares triviais, a equação reduz-se para o grau igual a k).
  • O grafo tem exatamente três autovalores:
    • k cuja multiplicidade é 1
    • \frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] cuja multiplicidade é \frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
    • \frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] cuja multiplicidade é \frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
  • Grafos fortemente regulares para os quais 2k+(v-1)(\lambda-\mu) = 0 são chamados grafos de conferência devido a sua conexão com matrizes de conferência simétricas. Seus parâmetros se reduzem asrg\left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right).
  • Grafos fortemente regulares para os quais 2k+(v-1)(\lambda-\mu) \ne 0 tem autovalores inteiros com multiplicidades desiguais.
  • O complemento de um gfr(v,k,λ,μ) também é fortemente regular. É um gfr(v, v−k−1, v−2−2k+μ, v−2k+λ)

Exemplos[editar | editar código-fonte]

Bibliografia[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]