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, 25 de outubro, 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