Arnaldo Mandel
IME-USP
Sexta-feira, 28 de março de 2008, às 14:00
Anfiteatro do NUMEC
Resumo:
O conceito de largura arbórea, introduzido por Robertson e Seymour, mostrou ser muito útil tanto para a Teoria dos Grafos "pura", quanto para o desenvolvimento de algoritmos. Assim, vale a pena ter diferentes caracterizações desse conceito.
A complicada definição dessa largura passa pelo conceito de decomposição arbórea (DA), uma construção típica de grafos que envolve vértices e arestas de forma essencial. Em um artigo no JCT (2006), Hlineny e Whittle propuseram uma noção de "decomposição arbórea livre de vértices" (DALV), e uma noção de largura associada. Embora não haja relação natural entre DA e DALV, eles provaram que as duas larguras coincidem (se não, qual a graça?)
A motivação para DALV é estender o conceito de largura arbórea para matróides; neste sentido, a largura arbórea livre de vértices de um grafo é a largura arbórea de seu matróide dos ciclos.
No seminário será apresentado o teorema de Hlineny e Whittle; conhecimento de matróides ajudará na compreensão, mas a exposição pretende ser acessível a pessoas com conhecimento básico de grafos.