MO405 - Prova I2

Criada: 2012-05-30
Modificada: 2012-06-02

Enunciado distribuido na sala.

Gabarito

  1. As posições (1,3), (2,5), (3,1), (4,2) e (5,4) formam uma transversal de peso 36. Para justificar, há uma cobertura formada por vetores (5,3,2,3,4) na horizontal e (5,4,4,4,2) na vertical, dando custo 36 também.
  2. Há um fluxo de tamanho 15. Para justificar, mostrar um corte de tamanho 15.
  3. [ (k-1)6 + (k-1) ] ( k3 - 4k2 + 6k - 4 ). O melhor é usar como aresta "e" uma que seja só do C5, e na segunda vez, uma que seja só do C4.
  4. Não é planar. Há uma subdivisão do K3,3. Há também uma subdivisão do K5.

Critérios de correção

Valores positivos são descontos na nota; valores positivos são o total dado à questão.

  1. Não deu cobertura: 1,5
  2. Passou mais fluxo do que capacidade em alguma aresta: -0,5
    Não deu corte válido: -1,0
  3. Errou sinal no resultado final: -0.5
    Errou desenho de algum grafo: -0,5
    Sabe fórmula de G-e e G.e, mas errou na aplicação: 0.5 (o instrutor preparou uma planilha para ver se as contas de cada aluno dão o resultado correto: polinomios.xls).
  4. Disse que o grafo "é" a subdivisão: -0,5
    Não mostrou a subdivisão completamente: -2,0
    Não considerou o grafo correto: -3,0.

MO405 Home

© 2012 João Meidanis