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

2024-144

Sobre o Algoritmo Húngaro, rodando num grafo de \(n\) vértices, podemos dizer que:

a) Dado um grafo qualquer, o algoritmo acha um emparelhamento de peso máximo com tempo de execução \(O(n^2)\)

b) Dado um grafo bipartido qualquer, o algoritmo acha um emparelhamento de peso mínimo com tempo de execução \(O(n^3)\)

c) Dado um grafo bipartido qualquer, o algoritmo acha um emparelhamento de peso máximo com tempo de execução \(O(n^2)\)

d) Dado um grafo qualquer, o algoritmo acha um emparelhamento de peso mínimo com tempo de execução \(O(n^3)\)

e) N.D.A

Ideia original de: Wellington T. A. da Silva

2024-143

Uma familia que morava no interior do estado de São Paulo, possuia 5 filhos com as seguintes idades 6, 8, 10, 12 e 14 anos.  A familia só possuia 5 brinquedos diferentes que as crianças podiam usar para brincar. Todas as tardes após a escola, as crianças começavam a brigar, pois sempre uma delas queria brincar com o brinquedo com o qual uma outra já estava brincando. Os pais, cansados de separar essas brigas, pediram para cada uma das crianças elencar a ordem de preferência dos brinquedos. Com isso, eles tiveram o seguinte resultado:

6   :     a > c > d > e > b

8   :     c > a > d > b > e

10 :     a > b > c > e > d

12 :     e > a > b > d > c

14 :     c > b > d > a > e

Porém, os pais sabiam que se deixassem, as crianças sempre iriam preferir os mesmos brinquedos.  Deste modo, os pais impuseram uma regra: se duas crianças quisessem o mesmo brinquedo, prevaleceria o desejo da mais velha.  Considerando a ordem de preferência acima e a regra criada pelos pais, qual das opções abaixo vai evitar trocas de brinquedos?

a) (6,d);(8,c);(10,b);(12,e);(14,a)

b) (6,a);(8,c);(10,b);(12,e);(14,d)

c) (6,b);(8,e);(10,a);(12,c);(14,d)

d) (6,b);(8,d);(10,a);(12,e);(14,c)

e) NDA;

Ideia original de: Gabriel S. Kraszczuk 

2024-142

Considere as afirmações a seguir:

1) Um grafo \(K_{n,n}\) tem a seguinte matriz de pesos:

Então, a soma de qualquer transversal associada é igual a \( \frac{\alpha^n-1}{\alpha-1} \).

2) Em qualquer matriz quadrada, toda transversal máxima possui a aresta de maior peso.

4) Em qualquer matriz quadrada, existe alguma transversal máxima com a aresta de maior peso.

Então, a soma das alternativas corretas é:

A) 1

B) 3

C) 5

D) 7

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian

2024-141

Considerando as afirmações, selecione a que não está correta.

a) Um matching maximal pode admitir um caminho aumentante.

b) Em uma árvore, toda aresta é uma aresta de corte.

c) Em uma árvore, o matching máximo sempre conterá pelo menos metade de todas as arestas.

d) O problema de Matching Máximo em grafos bipartidos pode ser modelado e, portanto, resolvido, como um problema de fluxo máximo.

e) N.D.A

Ideia original: Daniel Hosomi