Seminário de Teoria da Computação


                    Grafos Pfaffianos


                      Alberto Miranda

             Sexta-feira, 28 de novembro de 2008
                     Sala 85  16:00hs


Resumo: 
Pfaffianos estão na teoria dos grafos desde a década de 40, quando
Tutte os utilizou na primeira prova de seu famoso teorema sobre
existência de emparelhamentos perfeitos de um grafo. Grafos Pfaffianos
são uma classe de grafos que tem sido estudada desde a década de 60.
Para um grafo nesta classe de grafos é possível contar o número de
seus emparelhamentos perfeitos em tempo polinomial, além de outras
aplicações.  Neste seminário apresentaremos os principais resultados
da área, e os seus problemas em aberto.