2024-152

Dado o seguinte fluxo numa rede, possíveis valores de fluxo/capacidade para w, x, y e z, seriam:

a) w = 2/4, x = 10/14, y =19/20, z = 4/4

b) w = 3/4, x = 9/14, y = 8/20, z = 11/20

c) w = 1/4, x =11/14, y = 15/20, z =  4/4

d) w = 2/4, x =12/14, y = 11/20, z =  8/20

e) NDA 

Ideia original de: Juan David Nieto Garcia

2024-151

Lembrando que $\kappa (x,y)$ é o mínimo tamanho de um corte que separa $x$ de $y$, considere as seguintes alternativas e selecione a correta, considerando que $x,y$ são dois vértices que não tenham uma aresta direta entre si nos grafos em questão.

a) $\kappa (x,y)=2$ em um $C_6$, $\kappa (x,y)=2$ em um $P_6$ e $\kappa (x,y)=3$ em um $K_{3,3}$. 

b) $\kappa (x,y)=1$ em um $C_6$, $\kappa (x,y)=1$ em um $P_6$ e $\kappa (x,y)=3$ em um $K_{3,3}$. 

c) $\kappa (x,y)=1$ em um $C_6$, $\kappa (x,y)=1$ em um $P_6$ e $\kappa (x,y)=1$ em um $K_{3,3}$. 

d) $\kappa (x,y)=2$ em um $C_6$, $\kappa (x,y)=1$ em um $P_6$ e $\kappa (x,y)=3$ em um $K_{3,3}$. 

e) N.D.A.

Ideia original de: Guilherme Michel Carvalho

2024-150

Considere o grafo direcionado abaixo com as respectivas capacidades de cada aresta. Sejam S a fonte e T a fossa do grafo.

Então, sendo $n$ o valor do maior fluxo de S a T e $m$ o valor do menor S,T-corte, a soma $m+n$ resulta em:

A) 26

B) 28

C) 30

D) 32

E) NDE

Ideia Original de: Gabriel Cruz Vitale Torkomian.

2024-149

Dado o contexto de fluxo máximo em grafos, assinale a alternativa correta:

a) O algoritmo de Dinitz para fluxo máximo resolve o problema de fluxo com complexidade $O(E\sqrt{V})$.

b) Se todas as capacidade forem inteiras, é possível demonstrar que existe um fluxo máximo onde o fluxo por cada aresta é um número inteiro.

c) O algoritmo de Dijkstra resolve o problema de fluxo máximo.

d) O algoritmo de Kruskal resolve o problema de fluxo máximo.

e) N.D.A

Ideia original: Daniel Hosomi

2024-148

Considere as seguintes afirmações: 

1-) O grafo de Petersen possui 1-fator, 2-fator e 3-fator.

2-) O grafo abaixo possui emparelhamento perfeito.

3-) Para o grafo abaixo, temos que sua conectividade é κ = 3.

4-) Para o grafo abaixo, temos  κ < κ'.

Assinale a alternativa CORRETA:

a-) Somente as afirmativas 1 e 3 estão corretas

b-) Somente as afirmativas 2 e 4 estão corretas

c-) Somente as afirmativas 1, 2 e 4 estão corretas

d-) Somente as afirmativas 3 e 4 estão corretas

e-) N.D.A.

Ideia original de: Guilherme A. Terrell

2024-147

Considere o seguinte grafo não dirigido com 14 nós e 25 arestas. Cada nó possui um peso associado, conforme mostrado na ilustração. Qual é a soma máxima dos pesos de um corte mínimo no grafo? 

a) 9

b) 15

c) 7

d) 16

e) NDA

Ideia original de: Juan David Nieto

2024-146

Considere o grafo G abaixo com $|V(G)|=11$ e as afirmações a seguir:

1 - $G$ tem exatamente 8 blocos.

2 - $\kappa (G)={\kappa }^{\prime }(G)=1$.

4 - O maior bloco de $G$ tem tamanho 4.

A soma das afirmações corretas é:

A) 6

B) 5

C) 3

D) 2

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian 

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

2024-140

Suponha que temos um grafo $G$ com $n$ vértices e $m$ arestas. Se $G$ possui um emparelhamento máximo com $k$ arestas, o que se pode afirmar sobre a relação entre $n$, $m$ e $k$?

a) $m/2\le k\le n/2$

b) $k\le m/2$

c) $k=n$

d) $k\le n/2$

e) NDA

Ideia original de: Juan David Nieto 

2024-139

Considere as seguintes afirmações:

I) O algoritmo de Dijkstra serve para encontrar a mínima distância ponderada entre um vértice u e todos outros vértices. 

II) O algoritmo de Kruskal encontra os caminhos mínimos entre quaisquer dois vértices a partir da árvore geradora mínima. 

III) Se os pesos das arestas em um grafo G forem todos diferentes, então o algoritmo de Prim e o Algoritmo de Kruskal irão fornecer a mesma árvore geradora mínima.

IV) O algoritmo de Kruskal tem uma complexidade maior do que o de Prim.

Assinale a alternativa correta:

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

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

c) Apenas a afirmação II é correta.

d) Apenas as afirmações I, III e IV são corretas.

e) N.D.A

Ideia Original de: G. Michel Carvalho

2024-138

Considere as afirmações abaixo:

I) Em um ecossistema, existem $x$ espécies de animais e $y$ possíveis nichos ecológicos. Suponha que existe um natural $z$ não nulo com a seguinte propriedade:

Para cada espécie, existem exatamente $z$ possíveis nichos em que a espécie sobrevive e, para cada nicho, existem exatamente $z$ espécies de animais que podem habitá-lo.

Então, podemos alocar uma espécie por nicho de modo que todas sobrevivam.

II) Dado um grafo ponderado $G$ conexo com $n(G)\ge 2$, então quaisquer duas árvores espalhadas de peso mínimo tem pelo menos uma aresta em comum.

III) Seja $G$ um grafo simples. Então, $G$ possui um conjunto independente de $k$ vértices se, e somente se,  $\bar{G}$ (complementar de $G$) possuí um $K_k$ como subgrafo. Portanto, o maior clique subgrafo de $\bar{G}$ tem $\alpha (G)$ vértices, lembrando que $\alpha (G)$ é o tamanho de um conjunto independente máximo de $G$.

São verdadeiras somente:

A) I, III.

B) II, III.

C) I, II.

D) III.

E) NDE

Ideia original de: Gabriel Cruz Vitale Torkomian

2024-137

Qual o menor número de saltos necessários pra chegar no ponto B saindo do ponto A?

                  

Imagem adaptada de uma figura da página https://www.pngwing.com/pt/free-png-vteaz. Acesso em 04/04/2024.

A) 8

B) 9

C) 10

D) 11

E) N.D.A.

Ideia original de: Artur Silveira 

2012-004

Quantos grafos simples diferentes com vértices $A,B,C,D,E$ existem?

1. 512
2. 605
3. 1000
4. 1024
5. NDA

Ideia original de: Thierry Pinheiro Moreira