Diferenças entre edições de "Cintura (teoria dos grafos)"

9 bytes adicionados ,  12h40min de 29 de dezembro de 2020
m
traduzindo nome/parâmetro, ajustes gerais nas citações, outros ajustes usando script
(O link "método probabilístico" remetia à página genérica sobre a teoria das probabilidades. Esse link foi corrigido, encaminhando agora para uma página (apenas em inglês) que lista facto demonstrações probabilísticas de teoremas não probabilísticos.)
m (traduzindo nome/parâmetro, ajustes gerais nas citações, outros ajustes usando script)
 
Em [[teoria dos grafos]] a '''cintura''' ou '''girth''' de um grafo é o comprimento do mais curto [[Grafo ciclo|ciclo]] contido no grafo.<ref>R. Diestel, ''Graph Theory'', p.8. 3rd Edition, Springer-Verlag, 2005</ref><ref>{{citar livro|autor=BOAVENTURA NETTO, Paulo Oswaldo|titulo=Grafos|subtitulo=Teoria, Modelos Algoritmos|ano=2001|local=São Paulo|pagina=25|editora=Edgard Blücher|idisbn=ISBN 85-212-0292-X}}</ref>. Se o grafo não contém ciclos (isto é, um grafo acíclico), a sua cintura é definida como [[infinito|infinita]].<ref>{{citar web|url=http://mathworld.wolfram.com/Girth.html|titulo=Girth -- Wolfram MathWorld}}</ref>. 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 é [[Grafos sem triangulos|livre de triângulos]].
 
== Gaiolas ==
Um [[grafo cúbico]] (todos os vértices tem grau três) de cintura <math>g</math> que é tão pequeno quanto possível, é conhecido como uma [[gaiola (teoria dos grafos)|gaiola]]-<math>g</math> (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.<ref>{{citation|firstprimeiro =Andries E.|lastúltimo =Brouwer|authorlinkautorlink =Andries Brouwer|url=http://www.win.tue.nl/~aeb/drg/graphs/|titletítulo=Cages}}. Suplemento eletrônico ao livro ''Distance-Regular Graphs'' (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag)</ref>. 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]].
 
<gallery>
 
== Cintura e coloração de grafos ==
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 [[:en:List_of_probabilistic_proofs_of_non-probabilistic_theorems|método probabilístico]].<ref>{{citation | lastúltimo = Erdős | firstprimeiro = Paul | authorlinkautorlink = Paul Erdős | journal periódico= Canadian Journal of Mathematics | pages páginas= 34–38 | title título= Graph theory and probability | volume = 11 | year ano= 1959}}</ref>. Uma [[prova construtiva]] desse teorema foi dada por [[László Lovász|Lovász]] em 1968.<ref>{{Citar periódico|ultimo=Lovász|primeiro=L.|data=1968-03-01|titulo=On chromatic number of finite set-systems|url=https://doi.org/10.1007/BF01894680|jornal=Acta Mathematica Academiae Scientiarum Hungarica|lingua=en|volume=19|numero=1|paginas=59–67|doi=10.1007/BF01894680|issn=1588-2632}}</ref>.
 
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''<sup>(1&nbsp;−&nbsp;''g'')/''g''</sup>, 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 (teoria dos grafos)|conjunto independente]] de tamanho ''n''/2''k''. 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.
10 259

edições