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
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
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.
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
Considere as seguintes afirmações:
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
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'(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
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
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
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
Considere as afirmações a seguir:
1) Um grafo \(K_{n,n}\) tem a seguinte matriz de pesos:
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
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 \leq k \leq n/2\)
b) \(k \leq m/2\)
c) \(k = n\)
d) \(k \leq n/2\)
e) NDA
Ideia original de: Juan David Nieto
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
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) \geq 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, \(\overline{G}\) (complementar de \(G\)) possuí um \(K_k\) como subgrafo. Portanto, o maior clique subgrafo de \(\overline{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
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
Quantos grafos simples diferentes com vértices \(A, B, C, D, E\) existem?
Ideia original de: Thierry Pinheiro Moreira
