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:
Factos rápidos
Grafo fortemente regular |
![Thumb](//upload.wikimedia.org/wikipedia/commons/thumb/0/05/Paley13.svg/240px-Paley13.svg.png)
O Grafo Paley de ordem 13, um grafo fortemente regular com parâmetros gfr(13,6,2,3). |
Fechar
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.
- Os quatro parãmetros em um grs(v,k,λ,μ) não são independentes, como é fácil mostrar que:
![{\displaystyle (v-k-1)\mu =k(k-\lambda -1)}](//wikimedia.org/api/rest_v1/media/math/render/svg/f8c99bd2a24a9b4a667eb225d34e9aaac1a59160)
- 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:
![{\displaystyle A\times J=kJ}](//wikimedia.org/api/rest_v1/media/math/render/svg/5efe9b783cf60e891770b48c69f221525ec59a52)
(Esta é uma reafirmação trivial da exigência para os graus de vértices).
![{\displaystyle {A}^{2}+(\mu -\lambda ){A}+(\mu -k){I}=\mu {J}}](//wikimedia.org/api/rest_v1/media/math/render/svg/da88ebfb1408cdb531ba159dbbe3d9b9aaa6ea8c)
(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 é ![{\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}](//wikimedia.org/api/rest_v1/media/math/render/svg/bbc8e9b9ead0ab886e5b0a9b462a154538d4f273)
cuja multiplicidade é ![{\displaystyle {\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}](//wikimedia.org/api/rest_v1/media/math/render/svg/10c4e7c6833df4ca6e1613efb30a7f10d594d563)
- 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+λ)
- O grafo de Shrikhande é um gfr(16,6,2,2) que não é um grafo distância-transitivo.
- O ciclo de comprimento 5 é um gfr(5,2,0,1).
- O grafo de Petersen é um gfr(10,3,0,1).
- Os grafos de Chang são gfr(28,12,6,4).
- O grafo de Hoffman–Singleton é um gfr(50,7,0,1).
- O grafo de Higman–Sims é um gfr(100,22,0,4).
- Os grafos de Paley de ordem q são gfr(q, (q − 1)/2, (q − 5)/4, (q − 1)/4.
- O grafo de rook quadrado n × n é um gfr(n2, 2n − 2, n − 2, 2).
- O grafo de Brouwer–Haemers é um gfr(81,20,1,6).
- O grafo de Schläfli é um gfr(27,16,10,8).