Processos k-Reversíveis em Grafos

Uma variedade de modelos para estudar a disseminação de opinião consideram os aspectos dos processos dinâmicos em grafos. Nesse trabalho, apresentamos os processos k-reversí­veis. Em tais processos, cada vértice do grafo possui um estado dentre dois estados possí­veis a cada instante de tempo discreto. A mudança de estado de cada vértice ocorre apenas se esse vértice possuir pelo menos k vizinhos com estado oposto ao seu próprio estado naquele passo de tempo.

 Ao longo dessa dissertação, estudamos os processos k-reversí­veis e suas relações com outros processos que operam com limiares. Apresentamos resultados conhecidos na literatura relacionados ao comprimento do transiente e do perí­odo nesses processos. Desenvolvemos uma ferramenta especí­fica para os processos reversí­veis, que foi essencial na obtenção de demonstrações alternativas para esses mesmos resultados e para a demonstração de alguns limites mais justos. Estudamos o problema de determinar se uma configuração inicial é uma configuração jardim-do-éden em processos k-reversí­veis. Para esse problema, obtemos resultados inéditos para a dificuldade do problema e também algoritmos polinomiais para o caso onde o grafo é uma árvore e para o caso dos processos 2-reversí­veis em grafosonde o grau máximo de um vértice é três.