Conjuntos separadores em grafos e suas aplicações

Descrição

A Teoria dos Grafos é a área da matemática que estuda as relações entre objetos, ou seja, é através desse ramo que abstraímos a ideia comum existente por trás de problemas como, por exemplo, gerenciar as fronteiras de regiões em mapas, estabelecer uma comunicação eficiente entre torres de rádio, determinar os elementos de uma população de pessoas para serem vacinados contra uma doença contagiosa, descobrir o trajeto mais curto para realizar diversas entregas, estudar o alcance de uma notícia através das relações de amizade em redes sociais como o Facebook, criar uma rede inteligente de conexão entre computadores, dentre vários outros exemplos. A ideia existente por trás de todas essas relações é formalizada através do que chamamos de grafos. Apesar dos muitos resultados existentes, a Teoria dos Grafos é uma área que ainda está em grande crescimento no meio científico, tendo assim muitos problemas em aberto a serem investigados. O presente Projeto de Pesquisa utiliza-se da metodologia de estudo teórico, no que tange conceitos primordiais da Teoria dos Grafos e demonstração do Teorema 1.3, apresentado em Alon et al. (1994). Nesta primeira etapa do projeto, objetiva-se compreender a obtenção do conjunto S. Para isso, estudaremos os conceitos primordiais da Teoria dos Grafos, serão demonstrados teoremas e será estudado a obtenção do conjunto S. Na sequência, a metodologia analítica será utilizada, objetivando a busca pela resposta da questão norteadora. Será feito uma analogia dos resultados com o estudos de epidemias.