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 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 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. Grafos de Moore foram nomeados por 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. 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.