Todos são bem-vindos!!
Seminário de Algoritmos e Combinatória
Título: As conjecturas de Woodall e de Edmonds-Giles
Palestrante: Marcel K. de Carli Silva
Local: sala 241 do bloco A
Data: terça, 01 de novembro, das 13:00 às 14:00
Resumo:
A conjectura de Woodall afirma que, num grafo orientado, o número
máximo de junções mutuamente disjuntas é igual ao tamanho mínimo de um
corte orientado. Ela está em aberto há quase 30 anos. Sabemos que sua
versão capacitada, conhecida como conjectura de Edmonds-Giles, é
falsa.
Ambas as conjecturas provaram-se válidas para algumas classes de
grafos, entre as quais estão grafos fonte-sorvedouro-conexos, grafos
série-paralelos e árvores transitivas. Neste seminário, apresentaremos
algumas provas desses casos. Veremos tanto provas puramente
combinatórias como também provas poliédricas.
Forum