4.5 Dagens virkemidler
4.5.4 Forurensningsloven og plan- og
Um grafoG, simples, n ˜ao completo, n ˜ao nulo e n ˜ao dirigido, diz-se fortemente regular se for regular e se, dado um qualquer par de v ´ertices v, w ∈ V (G), o n ´umero de v ´ertices adjacentes simultaneamente a v ew depende, unicamente, do facto de v e w serem ou n ˜ao adjacentes. Assim, seG tiver ordem n, se for regular com ordem k, se cada par de v ´ertices adjacentes emGtiverav ´ertices vizinhos e cada par de v ´ertices n ˜ao adjacentes em
Gtivercv ´ertices vizinhos, dizemos queG ´e um grafo fortemente regular com par ˆametros
(n, k, a, c). A figura 3.2.1 mostra tr ˆes exemplos de grafos fortemente regulares.
(a) O ciclo de ordem 4 ´e fortemente regular com par ˆametros (4, 2, 0, 2).
(b) O grafo octaedral ´e fortemente regular com par ˆametros (6, 4, 2, 4).
(c) O grafo de Clebsch ´e fortemente regular com par ˆametros (16, 5, 0, 2).
Figura 3.2.1: Tr ˆes exemplos de grafos fortemente regulares.
Note-se que um conjunto de par ˆametros n ˜ao define, em geral, um ´unico grafo fortemente regular. Por exemplo, conhecem-se pelo menos 105 grafos fortemente regulares, n ˜ao
isomorfos, com o conjunto de par ˆametros(36, 14, 4, 6). Na Figura 3.2.2 podemos observar o grafo linha do grafo completo bipartidoK4,4e o grafo de Shrikhande, que s ˜ao dois grafos
fortemente regulares n ˜ao isomorfos que partilham o conjunto de par ˆametros(16, 6, 2, 2).
(a) Grafo linha de K4,4. (b) Grafo de Shrikhande.
Figura 3.2.2: Dois grafos fortemente regulares n ˜ao isomorfos com o conjunto de par ˆametros(16, 6, 2, 2).
Observac¸ ˜ao 3.2.1. Note-se que a entrada(Ar)ij da matriz de adjac ˆenciaAde um grafo
fortemente regular corresponde ao n ´umero de passeios de comprimentorentre os v ´ertices
iej (ver [29, Lemma 8.1.2]). Ent ˜ao a entrada(A2)ij corresponde ao n ´umero do passeios
de comprimento 2entre os v ´ertices i e j, mas como G ´e regular, este n ´umero depende apenas do facto deiejserem iguais ou distintos e, neste caso, se s ˜ao adjacentes ou n ˜ao. Assim, ´e poss´ıvel escreverA2como
A2 = kIn+ aA + c(Jn− A − In),
o que ´e equivalente a
A2+ (c − a)A + (c − k)In = cJn. (3.1)
tar,Gtamb ´em ´e um grafo fortemente regular com par ˆametros(n, ¯k, ¯a, ¯c), com ¯ k = n − k − 1, (3.2) ¯ a = n − 2 − 2k + c, (3.3) ¯ c = n − 2k + a. (3.4)
Neste ponto, note-se que enquanto (3.2) e (3.4) produzem sempre valores positivos, o mesmo n ˜ao est ´a garantido em (3.3).
Um grafo fortemente regular G diz-se primitivo se tanto G como o seu complementar
G forem conexos. O lema seguinte mostra que existe apenas uma classe de grafos fortemente regulares n ˜ao primitivos.
Lema 3.2.1. [29, Lema 10.1.1] Seja G um um grafo fortemente regular com par ˆametros
(n, k, a, c). Ent ˜ao as condic¸ ˜oes seguintes s ˜ao equivalentes:
(i) Gn ˜ao ´e conexo;
(ii) c = 0;
(iii) a = k − 1;
(iv) G ´e isomorfo amKk+1, para algumm > 1.
Observac¸ ˜ao 3.2.2. SeGfor um grafo fortemente regular com par ˆametros (n, k, a, c) co- nexo, isto ´e, sec 6= 0, ent ˜aodiam(G) = 2.
Os par ˆametros(n, k, a, c)de um grafo fortemente regular n ˜ao s ˜ao independentes entre si, estando relacionados atrav ´es da igualdade (3.5) da Proposic¸ ˜ao 3.2.1, que se apresenta em seguida. Este resultado aparece em toda a bibliografia sobre grafos fortemente regulares e a sua demonstrac¸ ˜ao ´e feita por simples contagem do n ´umero de arestas entre os vizinhos e os n ˜ao vizinhos de um v ´ertice fixo de um grafo fortemente regular. Por ´em, vamos apresentar uma demonstrac¸ ˜ao alternativa deste resultado utilizando somente ferramentas alg ´ebricas apresentadas no Cap´ıtulo 2.
Proposic¸ ˜ao 3.2.1. SejaGum grafo fortemente regular com par ˆametros(n, k, a, c)e matriz de adjac ˆenciaA. Ent ˜ao:
Demonstrac¸ ˜ao. ComoG ´e fortemente regular temos, pela Observac¸ ˜ao 3.2.1, que
A2 = kIn+ aA + c(Jn− A − In). (3.6)
SejaVn a ´algebra de Jordan euclidiana definida no Exemplo 2.3.1. SejaVn0 a sub ´algebra
de Vn gerada porIn e pelas pot ˆencias naturais de A. Na Secc¸ ˜ao 4.1 vamos demonstrar
queVn0 ´e uma ´algebra de Jordan euclidiana com dimens ˜ao e caracter´ıstica3. Admitindo a prova deste facto, podemos concluir que existe um ´unico sistema de Jordan associado aA
deVn0,S = {E0, E1, E2}cujos idempotentes satisfazem as propriedades:
(i) E0 = 1 nJn; (ii) 2 X i=0 Ei= In; (iii) AEi = λiEi; (iv) A = 2 X i=0 λiEi;
onde os λi,i ∈ {0, 1, 2} s ˜ao os valores pr ´oprios da matriz A. Como as pot ˆencias deA
podem ser escritas `a custa da decomposic¸ ˜ao espetral deA, temos pela propriedade(iv),
Am =
2
X
i=0
λmi Ei,
para qualquer inteirom ≥ 1, ent ˜ao a igualdade (3.6) pode ser escrita como
2 X i=0 λ2iEi= k 2 X i=0 Ei+ a 2 X i=0 λiEi+ c nE0− 2 X i=0 λiEi− 2 X i=0 Ei ! . (3.7)
Igualando os termos emE0 em ambos os membros da igualdade (3.7) obtemos:
λ20E0= kE0+ aλ0E0+ c(nE0− λ0E0− E0),
pelo que temos
Finalmente, como pela propriedade(i)temos queλ0= k, substituindo em (3.8) e fazendo
elementares manipulac¸ ˜oes alg ´ebricas obtemos a igualdade (3.5), pelo que a proposic¸ ˜ao fica demonstrada.
Um dos problemas no estudo dos grafos fortemente regulares ´e encontrar conjuntos de valores admiss´ıveis para os par ˆametros e, depois, tentar construir grafos que respeitem tais par ˆametros. A equac¸ ˜ao (3.5) ´e um exemplo de uma condic¸ ˜ao de admissibilidade que os par ˆametros de qualquer grafo fortemente regular t ˆem que obedecer.
SejaAa matriz de adjac ˆencia de um grafo fortemente regularGcom par ˆametros(n, k, a, c). Uma propriedade interessante `acerca dos grafos fortemente regulares ´e que os valores pr ´oprios de A, assim como as respetivas multiplicidades, podem ser escritos exclusiva- mente `a custa dos par ˆametros de G. De facto, os valores pr ´oprios de A s ˜ao a pr ´opria regularidadeke aindaθeτ dados por
θ = a − c +p(a − c) 2+ 4(k − c) 2 (3.9) τ = a − c −p(a − c) 2+ 4(k − c) 2 . (3.10)
Quanto `as multiplicidades, temos que a multiplicidade dek ´e1e as deθeτ s ˜aomθ emτ,
respetivamente, dadas por
mθ = 1 2 n − 1 − 2k + (n − 1)(a − c) p(a − c)2+ 4(k − c) ! (3.11) mτ = 1 2 n − 1 + 2k + (n − 1)(a − c) p(a − c)2+ 4(k − c) ! . (3.12)
Note-se que as f ´ormulas (3.11) e (3.12) constituem, por si pr ´oprias, condic¸ ˜oes de admis- sibilidade para conjuntos de par ˆametros de grafos fortemente regulares. Dado qualquer conjunto de par ˆametros(n, k, a, c), o c ´alculo demθ emτ tem que originar valores inteiros
e, caso contr ´ario, n ˜ao pode existir um grafo fortemente regular com esses par ˆametros. Por esta raz ˜ao, as condic¸ ˜oes (3.11) e (3.12) s ˜ao normalmente designadas por condic¸ ˜oes de integralidade.
O resultado que se segue mostra que apenas existe um tipo de grafos conexos regulares que ´e fortemente regular e ´e uma extens ˜ao do resultado em [29, Lema 10.2.1], j ´a que este apenas cont ´em a afirmac¸ ˜ao rec´ıproca do resultado seguinte.
Teorema 3.2.1. SejaGum grafo conexo e regular. Ent ˜aoG ´e fortemente regular se e s ´o seGtem exatamente tr ˆes valores pr ´oprios distintos.
Demonstrac¸ ˜ao. SejaGum grafo conexo e regular com regularidadekeAa respectiva ma- triz de adjac ˆencia. Suponhamos queG ´e fortemente regular com par ˆametros (n, k, a, c). Um valor pr ´oprio deA ´ek com vetor pr ´oprio associado,j = (1, 1, . . . , 1), j ´a que Aj = kj. Seja λ um outro valor pr ´oprio de A com λ 6= k e v um vetor pr ´oprio associado a λ. O vetorv ´e tal quev>j = 0(ver [29, Lemma 8.4.1]) e, portanto, J v = 0. Ent ˜ao, aplicando
v `a igualdade (3.1) da Observac¸ ˜ao 3.2.1 conclu´ımos que λtem que ser raiz da equac¸ ˜ao quadr ´atica
λ2+ (c − a)λ + c − k = 0, (3.13) pelo queAtem, no m ´aximo, tr ˆes valores pr ´oprios. ComoG ´e fortemente regular e conexo, a an ´alise das ra´ızes de (3.13) permite-nos concluir que G tem exatamente tr ˆes valores pr ´oprios distintos
Reciprocamente, suponhamos queAtem exatamente tr ˆes valores pr ´oprios distintos. Para al ´em dek, sejamλ1eλ2os outros valores pr ´oprios deA, distintos dek. Ent ˜ao
B = A2− (λ1+ λ2)A + λ1λ2In (3.14)
´e uma matriz tal queBv = 0, para cada vetor pr ´opriov deAexcetuando o vectorj.
Por outro lado, como
1
(k − λ1)(k − λ2)
Bj = j,
onde (k−λ B
1)(k−λ2) ´e o projetor ortogonal associado ao valor pr ´opriok, e comoG ´e conexo,
temos que
1
(k − λ1)(k − λ2)
B = 1
nJn. (3.15)
Substituindo (3.15) em (3.14), ´e poss´ıvel escreverA2como combinac¸ ˜ao linear deIn,Jne
Ae, portanto,G ´e fortemente regular.
Existem v ´arias fam´ılias interessantes de grafos fortemente regulares, algumas das quais ser ˜ao apresentadas na pr ´oxima subsecc¸ ˜ao.