Paulo Feofiloff
IME-USP
Sexta-feira, 15 de maio de 1998, 14:00
Sala 259, Bloco A, IME-USP
Resumo: D.R. Woodall conjecturou (1978) que todo grafo orientado satisfaz a identidade min-max
|T| = |c| ,
onde c é um corte orientado mínimo e T é uma coleção disjunta máxima de transversais de cortes orientados. (O teorema de Lucchesi-Younger prova a identidade dual: |C| = |t| para toda coleção disjunta C de cortes orientados e toda transversal mínima t.)
Esta palestra pretende discutir um caso da conjectura conhecido desde 1982: |T| = |c| para grafos acíclicos em que toda fonte está ligada a todo sorvedouro por um caminho orientado.