Girth (teoria dos grafos)

Na teoria dos grafos, o girth de um grafo não direcionado é o comprimento de um ciclo mais curto contido no grafo. Se o grafo não contiver nenhum ciclo (ou seja, for uma floresta), sua circunferência será definida como infinita. Por exemplo, um 4-cycle (quadrado) tem perímetro 4. Uma grade também tem perímetro 4 e uma malha triangular tem perímetro 3. Um gráfico com perímetro quatro ou mais é livre de triângulos.

Gaiolas

Um gráfico cúbico (todos os vértices têm grau três) de circunferência g que é o menor possível é conhecido como g-cage (ou como (3,g)-gaiola). O grafo de Petersen é o único 5-cage (é o menor gráfico cúbico de circunferência 5), o gráfico de Heawood é o único 6-cage, o gráfico de McGee é o único 7-cage e o Tutte eight cage é o único 8-cage jaula. Pode haver várias gaiolas para uma determinada circunferência. Por exemplo, existem três gaiolas de 10 não isomórficas, cada uma com 70 vértices: a gaiola de 10 Balaban, o grafo de Harries e o grafo de Harries-Wong.

• 

  O gráfico de Petersen tem uma circunferência de 5

• 

  O gráfico de Heawood tem uma circunferência de 6

• 

  O gráfico McGee tem uma circunferência de 7

• 

  O gráfico Tutte–Coxeter (Tutte oito gaiola) tem uma circunferência de 8

Circunferência e coloração do gráfico

Para quaisquer inteiros positivos g e χ, existe um gráfico com circunferência de pelo menos g e número cromático de pelo menos χ; por exemplo, o grafo de Grötzsch é livre de triângulos e tem número cromático 4, e repetir a construção Mycielskiana usada para formar o grafo de Grötzsch produz grafos sem triângulos de número cromático arbitrariamente grande. Paul Erdős foi o primeiro a provar o resultado geral, usando o método probabilístico. Mais precisamente, ele mostrou que um grafo aleatório em n vértices, formado pela escolha independente de incluir cada aresta com probabilidade n^(1–g)/g, tem, com probabilidade tendendo para 1 quando n vai para o infinito, no máximo n⁄2 ciclos de comprimento g ou menos, mas não tem conjunto independente de tamanho n⁄2k . Portanto, remover um vértice de cada ciclo curto deixa um grafo menor com perímetro maior que g, no qual cada classe de cor de uma coloração deve ser pequeno e que, portanto, requer pelo menos k cores em qualquer coloração.

Gráficos explícitos, embora grandes, com alto perímetro e número cromático podem ser construídos como certos gráficos de Cayley de grupos lineares sobre corpos finitos. Esses notáveis gráficos de Ramanujan também têm um grande coeficiente de expansão.

Conceitos relacionados

A circunferência ímpar e a circunferência par de um gráfico são os comprimentos de um ciclo ímpar mais curto e do ciclo par mais curto, respectivamente.

A circunferência de um gráfico é o comprimento do ciclo mais longo (simples), em vez do mais curto.

Considerado o menor comprimento de um ciclo não trivial, o perímetro admite generalizações naturais como a 1-sístole ou sístoles superiores na geometria sistólica.

Girth é o conceito dual para conectividade de aresta, no sentido de que a circunferência de um grafo planar é a conectividade de aresta de seu grafo dual e vice-versa. Esses conceitos são unificados na teoria dos matróides pelo perímetro de um matróide, o tamanho do menor conjunto dependente no matróide. Para um matróide gráfico, o perímetro do matróide é igual ao perímetro do grafo subjacente, enquanto para um matróide co-gráfico é igual à conectividade de borda.

Computação

O girth de um grafo não direcionado pode ser computado executando uma busca de largura em primeiro lugar de cada nó, com complexidade O(nm)O(nm)} Onde? nNão. é o número de vértices do grafo e mNão. é o número de bordas. Uma otimização prática é limitar a profundidade do BFS a uma profundidade que depende do comprimento do menor ciclo descoberto até agora. Algoritmos melhores são conhecidos no caso em que a circunferência é uniforme e quando o gráfico é planar. Em termos de limites inferiores, computar a circunferência de um gráfico é pelo menos tão difícil quanto resolver o problema de encontrar triângulo no gráfico.