MC828- Mat. Combinatória, Grafos e Aplicações

Of.: S-6 T:04 L:00 HS:04 SL:04 C:04

 

Pre-Req.: MC538

 

Equiv.: MC828 eq MC808

 

Ementa:

 

Noções básicas da teria dos grafos. Modelagem de problemas: fluxos em redes e programação linear. Tratamento de problemas NP-completos.

 

Programa:

 

  1. Noções básicas de teoria dos grafos
    1. Revisão de nomenclatura e conceitos básicos. Famílias de grafos. Caracterização de uma família.
    2. Passeios de Euler e circuitos Hamiltonianos
    3. Coloração de vértices e de arestas
    4. Planaridade
    5. Conexidade: em vértices, em arestas; cortes. Teorema de Menger
    6. Emparelhamentos e o teorema de Hall
    7. Componentes biconexos
    8. Componentes fortemente conexos
  2. Modelagem de problemas: fluxos em redes e programação linear
    1. O problema do fluxo máximo. Teorema do fluxo máximo/corte mínimo
    2. Algoritmos de Ford e Fulkerson. Algoritmo de Edmonds-Karp
    3. Aplicação: conexidade de redes
    4. Aplicação: emparelhamento e cobertura em grafos bipartidos
    5. O problema de programação linear. Fluxo máximo como um programa linear. Interpretação geométrica de PL. Dualidae.
    6. Aplicações de PL e de programação inteira
  3. Tratamento de problemas NP-completos
    1. Busca exaustiva: backtracking
    2. Busca exaustiva: branch-and-bound
    3. Algoritmos de aproximação
    4. Métodos heurísticos

 

Bibliografia:

 

R. Ahuja, T. Magnanti e J. Orlin. Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993

T. Cormen, C.Leiserson e R. Rivest, Introduction to Algorithms, MIT Press, 1990

R. Dieste. Graph Theory. Springer-verlag, 1997