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 distância-regular fortemente regular
simétrico (arco-transitivo) t-transitivo, t ≥ 2 .

(se conectado)
transitivo nos vértices e nas arestas aresta-transitivo e regular aresta-transitivo
vértice-transitivo regular
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:
  • 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:

    • (Esta é uma reafirmação trivial da exigência para os graus de vértices).

    • (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 . 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 . Para os auto-pares triviais, a equação reduz-se para o grau igual a k).
  • O grafo tem exatamente três autovalores:
    • cuja multiplicidade é 1
    • cuja multiplicidade é
    • cuja multiplicidade é
  • Grafos fortemente regulares para os quais são chamados grafos de conferência devido a sua conexão com matrizes de conferência simétricas. Seus parâmetros se reduzem a.
  • Grafos fortemente regulares para os quais 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]