Banca de DEFESA: SAULO ANTONIO DE LIMA MATOS

Uma banca de DEFESA de DOUTORADO foi cadastrada pelo programa.
DISCENTE : SAULO ANTONIO DE LIMA MATOS
DATA : 03/10/2023
HORA: 10:00
LOCAL: https://conferenciaweb.rnp.br/sala/defesa-doutorado-saulomatos
TÍTULO:

Invariantes e estruturas de vizinhanças para 1-fatorações de grafos completos

PALAVRAS-CHAVES:

1-Fatorações, Teoria dos Grafos, Isomorfismo, Invariantes, Coloração de arestas, Vizinhanças, Torneios \textit{round-robin}

PÁGINAS: 65
RESUMO:

Uma 1-fatoração é uma partição do conjunto de arestas de um grafo em emparelhamentos perfeitos. O conceito de 1-fatoração é de grande interesse devido às suas aplicações na modelagem de torneios esportivos. Duas 1-fatorações são ditas isomorfas (pertencem a mesma classe de isomorfismo) se existir uma bijeção entre seus conjuntos de vértices que transforme uma na outra. O espaço de busca de 1-fatorações não isomorfas é um grafo em que cada classe de isomorfismo é representada por um vértice e cada aresta que conecta os vértices $\mathcal{F}_a$ e $\mathcal{F}_b$ corresponde a um movimento em uma estrutura de vizinhança, que a partir de uma 1-fatoração isomorfa a $\mathcal{F}_a$ gera uma 1-fatoração isomorfa a $\mathcal{F}_b$. 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. Uma invariante é completa quando quaisquer duas 1-fatorações não isomorfas têm valores invariantes distintos. Essa tese analisa sete invariantes utilizadas para distinguir 1-fatorações não isomorfas de $K_{2n}$ (grafos completos com quantidade par de vértices). Considerando que as invariantes disponíveis na literatura não são completas, propomos duas novas invariantes, denominadas \textit{lantern profiles} e \textit{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 $K_{10}$ e $K_{12}$, bem como os conjuntos de 1-fatorações perfeitas não isomorfas de $K_{14}$ e $K_{16}$. Também consideramos aspectos algorítmicos e computacionais para explorar a vizinhança \textit{generalized partial team swap} (GPTS), uma estrutura de vizinhança para problemas de planejamento de tabelas de torneios \textit{round-robin} recentemente proposta na literatura. Nesse sentido, apresentamos um arcabouço para explorar a vizinhança GPTS. Além disso, é apresentada uma discussão sobre como esta estrutura de vizinhança aumenta a conectividade do espaço de busca definido por 1-fatorações não isomorfas de $K_{2n}$ (para $8 \le 2n \le 12$) quando comparada a outras estruturas de vizinhança.

MEMBROS DA BANCA:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2250653 - TIAGO DE OLIVEIRA JANUARIO
Externo ao Programa - 311515 - CELSO DA CRUZ CARNEIRO RIBEIRO - UFBAExterno à Instituição - VINICIUS FERNANDES DOS SANTOS - UFMG
Externo à Instituição - MARCIO COSTA SANTOS - UFMG
Externo à Instituição - SEBASTIÁN ALBERTO URRUTIA