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 ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 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 n g ( m − n + 1 ) {\displaystyle {\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

O Grafo de Petersen como um grafo de Moore. Qualquer árvore de busca em largura tem d(d-1)i vértices no seu nível i.

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 ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 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 ∑ i = 0 k − 1 ( d − 1 ) i . {\displaystyle 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 ∑ i = 0 k − 1 ( d − 1 ) i = 1 + ( d − 1 ) k − 1 + d ∑ i = 0 k − 2 ( d − 1 ) i . {\displaystyle 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 {\displaystyle K_{n}} com n > 2. (distância 1, cintura 3, grau n-1, ordem n)
  • Os ciclos impares C 2 n + 1 {\displaystyle 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 2 n {\displaystyle C_{2n}} , os grafos bipartidos completos K n , n {\displaystyle 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.

Ver também

  • Polígonos Generalizados (página em inglês)
  • Grafo Tutte-Coxeter (página em inglês)
  • O Problema Distância-Grau para grafos e digrafos (página em inglês)
  • Tabela de Grafos Distância-Grau (página em inglês)

Referências

  • Bollobás, Béla (1998), «Chap.VIII.3», Modern graph theory, Graduate Texts in Mathematics, 184, Springer-Verlag .
  • Bannai, E.; Ito, T. (1973), «Cópia arquivada», Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics, 20: 191–208, MR 0323615, consultado em 20 de fevereiro de 2015, cópia arquivada em 24 de abril de 2012 
  • Damerell, R. M. (1973), «On Moore graphs», Mathematical Proceedings of the Cambridge Philosophical Society, 74: 227–236, MR 0318004, doi:10.1017/S0305004100048015 
  • Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), «On a problem of graph theory» (PDF), Studia Sci. Math. Hungar., 1: 215–235 .
  • Hoffman, Alan J.; Singleton, Robert R. (1960), «Moore graphs with diameter 2 and 3», IBM Journal of Research and Development, 5 (4): 497–504, MR 0140437, doi:10.1147/rd.45.0497 
  • Singleton, Robert R. (1968), «There is no irregular Moore graph», American Mathematical Monthly, 75 (1): 42–43, MR 0225679, doi:10.2307/2315106 
  • Azarija, Jernej; Klavžar, Sandi (2014), «Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles», Journal of Graph Theory, doi:10.1002/jgt.21837 

Ligações externas

Notas

  • Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Moore graph».