Grafos notáveis e casos de borda em programação competitiva

Abstract

Este trabalho analisa casos de borda em problemas de grafos no contexto da programação competitiva, integrando fundamentação teórica, geração automatizada de instâncias e discussão de situações extremas que afetam implementações. Inicialmente, apresenta-se uma revisão de conceitos de programação competitiva, teoria dos grafos e geração de casos de teste, seguida da formalização de grafos notáveis recorrentes em competições. Na etapa prática, foram implementados geradores com a biblioteca Testlib para construir instâncias representativas e extremas dessas estruturas. Em seguida, problemas de programação competitiva foram analisados para identificar situações que comprometem a correção e a robustez das implementações, especialmente em cenários de conectividade atípica, limites de entrada e padrões estruturais específicos, com exemplificação dos geradores em cada problema selecionado. A discussão sugere que falhas recorrentes estão associadas, em grande parte, a hipóteses implícitas sobre a entrada e que a construção sistemática de casos de teste favorece a robustez das soluções. Como contribuição, o trabalho oferece um referencial teórico-prático para apoiar o desenvolvimento e a verificação de implementações em problemas de grafos.