Análise computacional do Teorema de Kuratowski
identificação de grafos planares e não planares através de implementação em Python
DOI:
https://doi.org/10.47385/tudoeciencia.2562.2025Palavras-chave:
Teorema de Kuratowski. Grafos planares. Teoria dos grafos. NetworkX. Planaridade.Resumo
O presente trabalho apresenta uma análise computacional do Teorema de Kuratowski, um dos resultados fundamentais da teoria dos grafos que caracteriza a planaridade de grafos através da presença ou ausência de subdivisões dos grafos completos K₅ e K₃,₃. Utilizando a biblioteca NetworkX em Python, foram implementados e analisados três casos de estudo: o grafo bipartido completo K₃,₃, o grafo completo K₅ e um grafo planar em grade 3x3. Os resultados confirmaram experimentalmente os postulados teóricos do teorema, demonstrando que K₃,₃ e K₅ são não planares, enquanto o grafo em grade 3x3 é planar. A implementação computacional permitiu verificar algoritmicamente a planaridade através do algoritmo de Kuratowski-Wagner, contribuindo para o entendimento prático deste importante teorema da matemática discreta. Este estudo evidencia a aplicabilidade computacional de conceitos teóricos fundamentais da teoria dos grafos e sua relevância em problemas práticos de desenho de circuitos e redes.
Downloads
Referências
BOLLOBÁS, B. Modern graph theory. New York: Springer-Verlag, 1998. (Graduate Texts in Mathematics, v. 184).
BONDY, J. A.; MURTY, U. S. R. Graph theory. London: Springer, 2008. (Graduate Texts in Mathematics, v. 244).
BOYER, J. M.; MYRVOLD, W. J. On the cutting edge: simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, v. 8, n. 3, p. 241-273, 2004.
CORMEN, T. H. et al. Introduction to algorithms. 3. ed. Cambridge: MIT Press, 2009.
DIESTEL, R. Graph theory. 5. ed. Berlin: Springer, 2017. (Graduate Texts in Mathematics, v. 173).
GROSS, J. L.; TUCKER, T. W. Topological graph theory. New York: Wiley-Interscience, 1987.
HAGBERG, A. A.; SCHULT, D. A.; SWART, P. J. Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference, p. 11-15, 2008.
HARARY, F. Graph theory. Reading: Addison-Wesley, 1969.
HOPCROFT, J.; TARJAN, R. Efficient planarity testing. Journal of the ACM, v. 21, n. 4, p. 549-568, 1974.
KURATOWSKI, K. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, v. 15, p. 271-283, 1930.
MACLANE, S. A structural characterization of planar combinatorial graphs. Duke Mathematical Journal, v. 3, n. 3, p. 460-472, 1937.
MEHLHORN, K.; MUTZEL, P. On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica, v. 16, n. 2, p. 233-242, 1996.
ORE, O. Theory of graphs. Providence: American Mathematical Society, 1962.
PREPARATA, F. P.; SHAMOS, M. I. Computational geometry: an introduction. New York: Springer-Verlag, 1985.
WAGNER, K. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, v. 114, p. 570-590, 1937.
WEST, D. B. Introduction to graph theory. 2. ed. Upper Saddle River: Prentice Hall, 2001.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Tudo é Ciência: Congresso Brasileiro de Ciências e Saberes Multidisciplinares
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
