Grafos sem triangulos

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

Na área de Teoria dos grafos da matemática, um grafo sem triângulos ou grafo livre de triângulos é um grafo não-direcionado no qual nenhum conjunto de três vértices forma um grafo triângulo de arestas. Grafos sem triângulos podem ser equivalententemente definidos como grafos com clique ≤ 2, grafos com cintura ≥ 4, grafos sem caminho induzido com três vértices, ou grafos localmente independentes.

Pelo Teorema de Turán, um grafo sem triângulos de n-vertíces com o número máximo de arestas é um grafo bipartido completo em que o número de vértices em cada lado da bipartição é o mais semelhante possível.

Problema de encontrar um triângulo[editar | editar código-fonte]

O Problema de encontrar um triângulo é o problema de determinar se um grafo possui ou não um triângulo. Quando o grafo contém um triângulo, normalmente,os algoritmos devem retornar como saída os três vértices que formam um triângulo no grafo.

É possível testar se um grafo de m-arestas não forma um triângulo em tempo O(m1.41).

Outra abordagem usada é encontrando o traço de A3, onde A é a matriz de adjacência do grafo. O traço é igual a zero se somente se o grafo não forma triângulos. Para grafos densos, usar um algoritmo simples que se baseia na multiplicação de matrizes é mais eficiente, visto que a complexidade de tempo é de O(n2.373), onde n é o número de vértices.

Como Imrich, Klavžar & Mulder (1999) mostrou, reconhecer um grafo sem triângulo é equivalente a reconhecer um grafo mediano em termos de complexidade; entretanto, o melhor algoritmo atual para o reconhecimento de grafos medianos usa detecção de triângulo em sua subrotina e não vice-versa.

A complexidade da árvore de decisão do problema, onde as consultas são feitas a um oráculo que guarda a matriz de adjacência do grafo, é Θ (n 2 ). No entanto, para algoritmos quânticos, o melhor limite inferior conhecido é Ω(n), mas devido à Belovs ( 2011), o algoritmo mais conhecido é O (n 1,29).

Número de Independência e Teoria de Ramsey[editar | editar código-fonte]

É fácil achar um conjunto independente de √n vertices em um grafo sem triângulo de n-vertíces: Ou há um vértice com mais de √n vizinhos (caso em que os vizinhos são um conjunto independente) ou todos os vértices tem menos de √n vizinhos (caso em que o máximo conjunto independente deve ter no mínimo √n vértices).[1] Esse limite pode ser reduzido um pouco mais: Para cada grafo sem triângulos, existe um conjunto independente de vértices, e em alguns grafos sem triângulos, cada conjunto independente tem vértices. Uma maneira de generalizar grafos sem triângulos em que todos os conjuntos independentes pequenos é usando o “processo de eliminar triângulos” [2] no qual um grafo máximo sem triângulos é formado adicionando repetidamente de forma aleatória arestas que não formam um triângulo. Com uma grande probabilidade, este processo gera um grafo com o número de independência . Com isso também é possível encontrar grafos regulares com as mesmas propriedades.

Esses resultados também podem ser interpretado como limitantes assintóticos no números de ramsey R(3,t) da formúla : se as arestas de um grafo completo em vértices são coloridos em vermelho e azul, então ou o grafo vermelho contém um triângulo ou, se não tiver triângulos, ele deve ter um conjunto independente de tamanho t correspondente ao clique do mesmo tamanho no grafo azul.

Coloração de grafos livres de triângulos[editar | editar código-fonte]

Muitas das pesquisas sobre grafos livres de triângulos são concentrados na coloração de grafos. Cada grafo bipartido (ou seja, cada 2-cores) é livre de triângulo, e o teorema de Grötzsch afirma que a cada grafo planar livre de triângulo pode ser 3-cores. [3] No entanto, os grafos sem triângulo não planos podem exigir muito mais do que três cores.

Mycielski (1955) definiu uma construção, agora chamada de Mycielskian, para a formação de um novo grafo livre de triângulos a partir de outro grafo livre de triângulos. Se um grafo tem número cromático k, seu Mycielskian tem como número cromático k + 1, logo, essa construção pode ser usada para mostrar que um grande número arbitrário de cores podem ser necessário para colorir um grafo livre de triângulos não-planar. Em particular, o grafo de Grötzsch, um grafo de 11 vértices formados a partir da aplicação repetida da construção de Mycielski, é um grafo livre de triângulos que não é possível colorí-lo usando no mínimo 4 cores e é o menor grafo com essa propriedade. Gimbel &Thomassen & (2000) e Nilli (2000) mostraram que o número de cores necessárias para colorir qualquer grafo livre de triângulos de m-arestas é :

e que existem grafos livre de triângulos que tem números cromáticos proporcionais a esse limite.

Também existem vários resultados relacionados a coloração de grau mínimo em grafos livre de triângulos. Andrásfai, Erdős & Sós (1974) provou que qualquer grafo livre de triângulos de n-vértices em que cada vértice tem mais de 2n/5 vizinhos deve ser bipartido. Isso é o melhor resultado possível desse tipo, como 5-ciclos requer três cores, mas tem exatamente 2n/5 vizinhos por vértice. Motivado por esse resultado, Erdős & Simonovits (1973) conjecturou que qualquer grafo livre de triângulo em que cada vértice tem pelo menos n/3 vizinhos pode ser colorido usando apenas 3 cores; entretanto, Häggkvist (1981) provou o contrário encontrando um contra-exemplo em que cada vértice do grafo de Grötzsch é substituido por um conjunto independente com um tamanho escolhido cuidadosamente. Jin (1995) mostrou que qualquer grafo livre de triângulos em que cada vértice tem mais 10n/29 vizinhos deve ser colorido com 3 cores; isso é o melhor resultado possível para esse tipo, pois o grafo de Häggkvist necessita de 4 cores e tem exatamente 10n/29 viznhos por vértice. Finalmente, Brandt & Thomassé (2006) provou que qualquer grafo livre de triângulos de n-vértices em que cada vértice tem mais de n/3 vizinhos deve ser 4-cores. Outros resultados para este tipo de grafos não é possível, visto que Hajnal[4] achou exemplos de grafos livre de triângulos com um grande número arbitrário de cores e grau mínimo (1/3 − ε)n para qualquer ε > 0.

Referências[editar | editar código-fonte]

Notes
Sources

External links[editar | editar código-fonte]