Cintura (teoria dos grafos)

comprimento do ciclo mais curto contido num grafo

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 é livre de triângulos.

GaiolasEditar

Um grafo cúbico (todos os vértices tem grau três) de cintura   que é tão pequeno quanto possível, é conhecido como uma gaiola-  (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 grafosEditar

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] Uma prova construtiva desse teorema foi dada por Lovász em 1968.[6]

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çõesEditar

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 (2001). Grafos. Teoria, Modelos Algoritmos. São Paulo: Edgard Blücher. p. 25. ISBN 85-212-0292-X 
  3. «Girth -- Wolfram MathWorld» 
  4. Brouwer, Andries E., Cages . 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 
  6. Lovász, L. (1 de março de 1968). «On chromatic number of finite set-systems». Acta Mathematica Academiae Scientiarum Hungarica (em inglês). 19 (1): 59–67. ISSN 1588-2632. doi:10.1007/BF01894680