Orlando Lee (lee@ime.usp.br)
IME-USP
Sexta-feira, 6 de março de 1998, 14:00
Sala 259, Bloco A, IME-USP
Resumo: Dado um grafo orientado D=(V,A), dizemos que C é um corte orientado se existe $X\subset V$ tal que C é exatamente o conjunto de arcos que saem de X e não existem arcos entrando em X. Uma transversal de cortes orientados é um conjunto de arcos que intercepta todos os cortes orientados.
Em 1978, Woodall conjecturou que em um grafo orientado qualquer, o tamanho de um corte orientado mínimo é igual ao número máximo de transversais disjuntas. Para grafos orientados planares, usando dualidade, esta conjectura diz que o tamanho de um circuito mínimo é igual ao número máximo de transversais disjuntas de circuitos (conjunto de arcos que intercepta todos os circuitos).
Neste seminário apresentaremos um histórico do que já se sabe sobre esta conjectura e mostraremos que ela vale para grafos série-paralelos.