Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do LV Simpósio Brasileiro de Pesquisa Operacional

Uma 1-fatoração é uma partição do conjunto de arestas de um grafo em emparelhamentos perfeitos. Uma invariante de uma 1-fatoração é uma propriedade que depende apenas de sua estrutura, de modo que 1-fatorações isomorfas possuem valores de invariantes iguais. Assim sendo, 1-fatorações não isomorfas podem ou não ter valores de invariante diferentes. Uma invariante é completa quando quaisquer duas 1-fatorações não isomorfas têm valores invariantes distintos. Propomos duas invariantes para distinguir 1-fatorações não isomorfas de K2n (grafos completos com quantidade par de vértices), denominadas lantern profiles e even-size bichromatic chains. As invariantes são comparadas quanto aos seus tamanhos e complexidade computacional do seu cálculo. Além disso, realizamos experimentos computacionais para avaliar suas capacidades de distinguir 1-fatorações não isomorfas. Para tal, utilizamos os conjuntos de 1-fatorações não isomorfas de K10 e K12. Ademais, os experimentos avaliam a combinação de algumas invariantes.