Grafos sem triangulos
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
- ↑ Boppana & Halldórsson ( 1992). pág. 184, com base na ideia de um algoritmo de coloração aproximado de Avi Wigderson.
- ↑ Erdős, Suen & Winkler (1995); Bohman (2008)
- ↑ Grötzsch ( 1959); Thomassen ( 1994).)
- ↑ see Erdős & Simonovits (1973).
- Sources
- Alon, N.; Ben-Shimon, S.; Krivelevich, M. (2008). «A note on regular Ramsey graphs». arXiv:0812.2386.
- Alon, N.; Yuster, R.; Zwick, U. (1994), «Finding and counting given length cycles», Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364.
- Andrásfai, B.; Erdős, P.; Sós, V. T. (1974), «On the connection between chromatic number, maximal clique and minimal degree of a graph», Discrete Mathematics, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2.
- Bohman, T. (2008). «The triangle-free process». arXiv:0806.4375.
- Boppana, Ravi; Halldórsson, Magnús M. (1992), «Approximating maximum independent sets by excluding subgraphs», BIT, 32 (2): 180–196, MR 1172185, doi:10.1007/BF01994876.
- Brandt, S.; Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem (PDF), consultado em 9 de agosto de 2014, arquivado do original (PDF) em 4 de fevereiro de 2012.
- Chiba, N.; Nishizeki, T. (1985), «Arboricity and subgraph listing algorithms», SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
- Chvátal, Vašek (1974), «The minimality of the Mycielski graph», Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics, 406, Springer-Verlag, pp. 243–246.
- Erdős, P.; Simonovits, M. (1973), «On a valence problem in extremal graph theory», Discrete Mathematics, 5 (4): 323–334, doi:10.1016/0012-365X(73)90126-X.
- Erdős, P.; Suen, S.; Winkler, P. (1995), «On the size of a random maximal graph», Random Structures and Algorithms, 6 (2–3): 309–318, doi:10.1002/rsa.3240060217.
- Gimbel, John; Thomassen, Carsten (2000), «Coloring triangle-free graphs with fixed size», Discrete Mathematics, 219 (1-3): 275–277, doi:10.1016/S0012-365X(00)00087-X.
- Grötzsch, H. (1959), «Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel», Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8: 109–120.
- Häggkvist, R. (1981), «Odd cycles of specified length in nonbipartite graphs», Graph Theory (Cambridge, 1981), pp. 89–99.
- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), «Median graphs and triangle-free graphs», SIAM Journal on Discrete Mathematics, 12 (1): 111–118, MR 1666073, doi:10.1137/S0895480197323494.
- Itai, A.; Rodeh, M. (1978), «Finding a minimum circuit in a graph», SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033.
- Jin, G. (1995), «Triangle-free four-chromatic graphs», Discrete Mathematics, 145 (1-3): 151–170, doi:10.1016/0012-365X(94)00063-O.
- Kim, J. H. (1995), «The Ramsey number has order of magnitude » 3 ed. , Random Structures and Algorithms, 7: 173–207, doi:10.1002/rsa.3240070302.
- Magniez, Frederic; Santha, Miklos; Szegedy, Mario (2003). «Quantum Algorithms for the Triangle Problem». arXiv:quant-ph/0310134.
- Mycielski, J. (1955), «Sur le coloriage des graphes», Colloq. Math., 3: 161–162.
- Nilli, A. (2000), «Triangle-free graphs with large chromatic numbers», Discrete Mathematics, 211 (1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.
- Shearer, J. B. (1983), «Note on the independence number of triangle-free graphs», Discrete Mathematics, 46 (1): 83–87, doi:10.1016/0012-365X(83)90273-X.
- Thomassen, C. (1994), «Grötzsch's 3-color theorem», Journal of Combinatorial Theory, Series B, 62 (2): 268–279, doi:10.1006/jctb.1994.1069.
- Belovs, Aleksandrs (2011). «Span Programs for Functions with Constant-Sized 1-certificates». arXiv:1105.4024.