Grafo de Moore
# Grafo de Moore

Em Teoria dos Grafos, um Grafo de Moore é um Grafo regular de grau d e distância k o qual o número de vértices é igual ao limitante superior
    $1+d\sum _{i=0}^{k-1}(d-1)^{i}.$
Uma definição equivalente de um grafo de Moore é que ele é um grafo de distância k com cintura 2k + 1. Uma outra definição equivalente de um grafo de Moore G é que ele tem cintura g = 2k+1 e precisamente ${\frac {n}{g}}(m-n+1)$ ciclos de comprimento g, onde n,m é o número de vértices e arestas, respectivamentes, de G. Eles são de fatos extremos em relação ao número de ciclos cujo comprimento é a cintura do grafo. (Azarija & Klavžar 2014)
Grafos de Moore foram nomeados por Hoffman & Singleton (1960) em homenagem à Edward F. Moore, pessoa que botou em questão descrever e classificar esses grafos.
Além de ter o maior número possível de vértices para uma combinação dada de ângulo e diâmetro, Grafos de Moore tem o menor número possível de vértices para um grafo regular com dado ângulo e cintura. Isto é, qualquer e todo Grafo de Moore é uma jaula (Erdős, Rényi & Sós 1966). A fórmula para o número de vértices num grafo de Moore pode ser generalizada para permitir uma descrição de grafos de Moore tanto com cintura par quanto impar, e, novamente, esses grafos são jaulas.

## Limitando vértices por grau e distância

Seja G um grafo de grau máximo d e distância k, e considere a árvore foramada por busca em largura começando de qualquer vértice v. Essa árvore tem um vértice no nível 0 (o próprio v) e, no máximo, d vértices no nível 1 (os vizinhos de v). No próximo nível, temos no máximo d(d-1) vértices: cada vizinho de v usa um de seus adjacentes para conectar ao v e então só pode ter no máximo d-1 vizinhos no nível 2. Em geral, um argumento semelhante mostra quem em qualquer nível 1 ≤ i ≤ k, só pode haver no máximo d(d-1)$^i$ vértices. Então, o número total de vértices pode ser:
    $1+d\sum _{i=0}^{k-1}(d-1)^{i}.$
Hoffman & Singleton (1960) originalmente definiu um grafo de Moore como um grafo em que esse limite no número de vértices é alcançado exatamente. Então, qualquer grafo de Moore tem o maior número de vértices possíveis entre todos os grafos de máximo grau d e máxima distância k.
Depois, Singleton (1968) mostrou que grafos de Moore podem ser equivalentemente definidos como tendo distância k e cintura 2k+1; Esses dois requerimentos combinaram para forçar o grafo à ser regular de nível d para algum d e para satisfazer a fórmula de contar vértices.

## Grafos de Moore como Jaulas

Em vez de limitar superiormente o número de vértices em um grafo em termos de seu máximo grau e diâmetro, podemos calcular por métodos semelhantes um limite inferior no número de vértices em termos de seu grau mínimo e sua cintura (Erdős, Rényi & Sós 1966). Suponha que G tenha mínimo grau d e cintura 2k+1. Escolha arbitráriamente um vértice inicial v e considere a árvore de busca em largura com raiz em v. Esta árvore tem que ter pelo menos um vértice no nível 0 (o próprio v) e pelo menos d vértices no nível 1. No nível 2 (para k > 1), temos que ter pelo menos d(d-1) vértices, porque cada vértice no nível 1 tem pelo menos d-1 adjacências sobrando para preencher, e não existem dois vértices no nível 1 adjacentes um ao outro ou para um vértice em comum no nível 2 porque isso criaria um ciclo menor do que a cintura suposta.
Em geral, um argumento semelhante mostra que em qualquer nível 1 ≤ i ≤ k, temos que ter pelo menos d(d-1)$^i$ vertices. Então, o número total de vértices tem que ser pelo menos:
    $1+d\sum _{i=0}^{k-1}(d-1)^{i}.$
Em um grafo de Moore, este limite no número de vértices é atigindo exatamente. Cada grafo de Moore tem cintura exatamente 2k+1: não tem vértices suficientes para ter cintura maior, e um ciclo menor causaria a existência de muitos poucos vértices nos primeiros k níveis da árvore de busca em largura. Então, qualquer grafo de Moore tem o mínimo número de vértices entre todos os grafos de grau mínimo d, distância k: É uma jaula.
Para cintura par 2k, um pode semelhantemente montar uma árvore de busca em largura começando do ponto do meio de uma aresta única. O limitante resultante no número mínimo de vértices em um grafo de tal cintura com mínimo grau d é
    $2\sum _{i=0}^{k-1}(d-1)^{i}=1+(d-1)^{k-1}+d\sum _{i=0}^{k-2}(d-1)^{i}.$
(O lado direito da fórmula conta o número de vértices em uma árvore de busca em largura começando por um único vértice, considerando a possibilidade de quem um vértice no último nível da árvore pode ser adjacente à d vértices no nível anterior.) Então, os grafos de Moore são às vezes definidos como incluindo os grafos que atingem esse limite, e qualquer um desses grafos deve ser uma jaula.

## Exemplos

O Teorema Hoffman–Singleton diz que qualquer grafo de Moore com cintura 5 tem que ter grau 2, 3, 7, ou 57. Os grafos de Moore são:
* Os grafos completos $K_{n}$ com n > 2. (distância 1, cintura 3, grau n-1, ordem n)
* Os ciclos impares $C_{2n+1}$. (distância n, cintura 2n+1, grau 2, ordem 2n+1)
* O Grafo de Petersen. (distância 2, cintura 5, grau 3, ordem 10)
* O Grafo de Hoffman-Singleton. (distância 2, cintura 5, grau 7, ordem 50)
* Um grafo hipotético de distância 2, cintura 5, grau 57 e ordem 3250. Não se sabe ainda se tal grafo existe.
Ao contrário de todos os outros grafos de Moore, Higman provou que o grafo de Moore desconhecido não pode ser vértice-transitivo.
Se a definição generalizada de grafos de moore que permite grafos de cintura par é usada, os grafos de Moore de cintura par correspondem à grafos de incidência de (possivelmente corrompidos) Polígonos Generalizados. Alguns exemplos são os ciclos pares $C_{2n}$, os grafos bipartidos completos $K_{n,n}$ com cintura 4, o Grafo de Heawood com grau 3 e cintura 6, e o grafo Tutte–Coxeter com grau 3 e cintura 8. Mais generalizadamente, é conhecido (Bannai & Ito 1973; Damerell 1973) que, além dos grafos listados acima, todos os grafos de Moore tem que ter cintura 5, 6, 8 ou 12. O caso par de cintura também segue do teorema Feit-Higman sobre possíveis valores de n para um n-gono generalizado.