2024-145

Considere o problema de matching em grafos bipartidos com homens sendo x, y, z, w e mulheres sendo a, b, c, d e com as preferências listadas abaixo:

Homens: x: a > b > c > d y: a > c > b > d z: c > d > a > b w: c > b > a > d

Mulheres: a: z > x > y > w b: y > w > x > z c: w > x > y > z d: x > y > z > w

Defina pesos para as preferências como sendo 4, 3, 2, 1, com o valor mais alto para a maior preferência. Dado um matching, defina a felicidade dos homens como sendo a soma dos pesos de cada homem obtidas no matching. Analogamente, defina a felicidade das mulheres.

Considere as seguintes afirmações:

I) Num emparelhamento estável, o valor máximo para a felicidade dos homens é 13.

II) Num emparelhamento estável, o valor máximo para a felicidade das mulheres é 16.

III) Quando a felicidade dos homens é maximizada, a felicidade das mulheres tem valor 10.

Assinale a alternativa correta:

a) Apenas as afirmações I) e II) são corretas.

b) Apenas as afirmações I) e III) são corretas.

c) Apenas as afirmações II) e III) são corretas.

d) Todas as afirmações são corretas.

e) N.D.A

Ideia original de: G. Michel Carvalho