MO405 - Exercícios - Propostos em 2002-09-16

Nos exercícios que perguntam "verdadeiro ou falso", deve-se justificar a resposta da seguinte forma: se for verdadeiro, com uma prova; se for falso, com um contra-exemplo.

1. (3.2.1 do livro)
2. (3.2.3 do livro)

Soluções - Discutidas em classe em 2002-09-18

1. 3.2.1 – Usando pesos não negativos para as arestas, construa um grafo ponderado com 4 vértices o qual o emparelhamento de peso máximo não seja o emparelhamento de tamanho máximo.

    

    Resolução:

    

         

    

   Emparelhamento de peso máximo: {(b,c)}

   Emparelhamento de tamanho máximo: {(a,b), (c,d)}

    

    

2. 3.2.3 – Dê  um exemplo do problema do casamento estável com 2 homens e 2 mulheres onde existe mais de um casamento estável.

    

           Resolução:

    

               Considerando a seguinte configuração:

                    

          

   Onde a bipartição é X = {a,b} e Y = {c,d} e 

          

    significa que "x prefere y do que o outro vértice do lado de y", existem os dois casamentos estáveis: