Cintura (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em teoria dos grafos a cintura ou girth de um grafo é o comprimento do mais curto ciclo contido no grafo[1] [2] . Se o grafo não contém ciclos (isto é, um grafo acíclico), a sua cintura é definida como infinita[3] . Por exemplo, um 4-ciclo (quadrado), tem cintura 4. Uma grade tem cintura 4, igualmente, e uma malha triangular tem cintura 3. Um grafo com cintura >3 é triângulo-livre.

Gaiolas[editar | editar código-fonte]

Um grafo cúbico (todos os vértices tem grau três) de cintura g que é tão pequeno quanto possível, é conhecido como uma gaiola-g (ou como uma (3,g)-gaiola). O grafo de Petersen é o único gaiola-5 (esse é o menor grafo cúbico de cintura 5), o grafo de Heawood é o único gaiola-6, o grafo de McGee é o único gaiola-7 e o gaiola oito de Tutte é o único gaiola-8[4] . Podem existir várias gaiolas para uma cintura dada. Por exemplo, há três gaiolas-10 não-isomórficas, cada uma com 70 vértices: a gaiola-10 de Balaban, o grafo de Harries e o grafo de Harries-Wong.

Cintura e coloração de grafos[editar | editar código-fonte]

Para quaisquer inteiros positivos g e χ, existe um grafo com cintura de pelo menos g e número cromático, de pelo menos χ; por exemplo, o grafo de Grötzsch é livre de triângulo e tem número cromático 4, e repetindo a construção de Mycielskian usada para formar o grafo de Grötzsch produz grafos livres de triângulos de arbitrariamente grande número cromático. Paul Erdős foi o primeiro a provar o resultado geral, usando o método probabilístico[5] .

Mais precisamente, ele mostrou que um grafo aleatório em n vértices, formado por escolha independentemente se é necessário incluir cada aresta com probabilidade n(1 − g)/g, tem, com probabilidade tendendo a 1 a medida que n vai para o infinito, no máximo n/2 ciclos de comprimento g ou menos, mas não tem nenhum conjunto independente de tamanho n/2k. Portanto, a remoção de um vértice de cada ciclo curto deixa um pequeno grafo com cintura superior a g, em que cada classe de cor de uma coloração deve ser pequena e que, portanto, exige, pelo menos k cores em qualquer coloração.

Generalizações[editar | editar código-fonte]

A cintura ímpar e a cintura par de um grafo são o comprimento do ciclo ímpar mais curto e o ciclo par mais curto respectivamente. Pensada como o menor comprimento de um ciclo não-trivial, a cintura admite generalizações naturais como a 1-sístole ou maiores sístoles em geometria sistólica.

Referências

  1. R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. BOAVENTURA NETTO, Paulo Oswaldo. Grafos: Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher, 2001. ISBN 85-212-0292-X.
  3. Girth -- Wolfram MathWorld.
  4. Brouwer, Andries E., Cages, http://www.win.tue.nl/~aeb/drg/graphs/ . Suplemento eletrônico ao livro Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag)
  5. Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics 11: 34–38