MO405 - Prova Individual 2

Criada: 2002-11-10

Data da prova: 2002-12-04

Enunciado: aqui

Soluções e Critérios de Nota:

1. Pode-se afirmar que o grafo é euleriano, por ser par (todos os vértices têm grau par) e possuir uma única componente não trivial. Pode-se também afirmar que o grafo não é bipartido, pois a existência de um passeio fechado de tamanho ímpar implica a existência de ciclo ímpar. Por outro lado, não se pode afirmar que o grafo tenha um ciclo de tamanho par. Por exemplo, C₃ satifaz a todas as condições do enunciado mas não tem ciclo par.
   O critério de avaliação usado nesta questão foi basicamente o de que cada item (A,B,C,D) valia 1/4 da nota da questão, se fosse bem justificado. Adicionalmente, subtraí 0,5 da nota por cada um dos seguintes erros:
   • dizer "equivale" quando na verdade o certo é "implica"
   • afirmar que grafo par é sempre euleriano (esquecer de que precisa ter apneas uma componente não tricial)
   • afirmar que grafo par não trivial é euleriano (mesmo comentário acima)
   • não dar um contra-exemplo para dizer que D é falsa
   • não saber o que é "grafo par"
   • enganar-se e trocar "não trivial" por "trivial"
   • afirmar que se um grafo é euleriano e bipartido então ele é C_2n para algum n
2. A alternativa correta é a B.
   O critério de correção atribuiu pontos aos seguintes itens:
   • 0,5 por dizer qual é o único emparelhamento estável
   • 1,0 por argumentar porque este emparelhamento é estável
   • 1,0 por argumentar porque nenhum outro emparelhamento é estável
   Outras coisas que fizeram perder pontos foi confundir "estável" com "perfeito" e fazer confusão entre os dois "lados" do grafo nos argumentos.
3. As alternativas A e D são corretas, e B e D são incorretas.
   O critério de avaliação usado nesta questão foi basicamente o de que cada item (A,B,C,D) valia 1/4 da nota da questão, se fosse bem justificado.
   Quem esqueceu de analisar K₁ na A perdeu 0,5.
   
4. A resposta correta é B.
   Os pontos foram atribuídos da seguinte forma:
   • 0,5 por uma coloração total de P₅ com 3 cores
   • 1,0 por um argumento de que C₅ precisa de 4 cores
   • 0,5 por um argumento de que K₅ precisa de 4 ou mais cores
   • 0,5 por um argumento de que K_1,5 precisa de 4 ou mais cores
   Além disso, tirei 0,5 pontos de quem afirmou que algum grafo precisava de mais cores do que o correto. Por exemplo, alguns disseram que o K₅ precisa de 10 cores, quando o correto é que 5 cores bastam. Outros afirmaram que o K_1,5 precisa de 7 cores, quando na verdade 6 cores bastam.