Calendário de Eventos
|
Seminário PESC: Rafael Castro de Andrade (UFC)
Quinta-feira, 16 Novembro 2023, 10:00 - 12:00
Introdução às Árvores de Cristal
Prof. Rafael Castro de Andrade (UFC)
 |
Introdução às Árvores de Cristal
Prof. Rafael Castro de Andrade (UFC)
Moderador Prof. Nelson Maculan Filho
Dia 16/11 (quinta-feira), 10 horas, Sala H-319/11.
Transmissão ao vivo no Canal do PESC no Youtube.
|
Resumo:
O seminário trará o conceito de árvore de cristal, sua modelagem matemática e aplicações em problemas de otimização combinatória. Considere um grafo simples ponderado e não orientado G=(V,E), onde cada aresta e de E tem peso ce > 0, e uma árvore geradora Tk de G enraizada em um vértice k de V. Associe a cada nó v de Tk um potencial correspondendo ao multiconjunto ?(k,v)={ce | aresta e pertence ao caminho de k a v em Tk}. A raiz de Tk tem potencial vazio. Defina a operação de diferença simétrica ?(k,{u,v}) entre os multiconjuntos dos extremos de uma aresta {u,v} de E não pertencente a Tk como ?(k,{u,v}) = ?(k,v) ? ?(k,u) = ?(k,v) ?(k,u) U ?(k,u) ?(k,v), onde as operações de diferença simétrica, diferença e união de conjuntos tradicionais são estendidas para multiconjuntos. Diremos que os potenciais dos vértices u e v estão:
(i) em equilíbrio estável, se cuv >= ce, para toda aresta e no caminho de u a v em Tk; ou
(ii) em equilíbrio instável, se cuv ce para alguma aresta e no caminho d u a v em Tk e o elemento de maior valor em ?(k,{u,v}) é menor ou igual a cuv; ou
(iii) em não equilíbrio, caso contrário.
Uma árvore geradora Tk de G é dita de cristal quando todos seus vértices apresentarem equilíbrio estável ou instável. Mostramos que essa nova classe de árvores generaliza as árvores geradoras de custo mínimo (AGM) de um grafo, encaixando-as na definição de equilíbrio estável. Podemos mostrar que nem toda árvore de cristal é uma AGM e analisar diferenças em relação a outras classes de árvores, como as de caminho mínimo enraizada em algum nó. Além de mostrar alguns resultados teóricos, apresentaremos uma modelagem matemática que leva a uma definição algébrica para as mesmas. A interseção de sistemas de árvores de cristal fornece um sistema linear cujas soluções correspondem a AGMs. Isso abre novas possibilidades de resolução de problemas de otimização com estrutura de árvore ótima em seu conjunto de restrições, como árvores robustas e de Steiner com prêmio em vértices.
Short Bio:
Professor Titular, Universidade Federal do Ceará, Departamento de Estatística e Matemática Aplicada. Ph.D. em Ciência da Computação, Sorbonne Université Paris-Nord (2002), M.Sc. em Engenharia de Sistemas e Computação, COPPE-UFRJ (1999), B.Sc. em Ciência da Computação, Universidade Estadual do Ceará (1997). Trabalha nas áreas de otimização combinatória e suas aplicações em problemas de dimensionamento de redes. Possui artigos de pesquisa nas seguintes revistas: Management Science, Annals of Operations Research, Discrete Applied Mathematics, NETWORKS, European Journal of Operational Research, Computer & Operations Research, International Transactions in Operational Research. Possui bolsa de produtividade do CNPq.