2024-153

Questão 9 - Dado os contextos de fluxos máximos e grafos k-coloráveis, assinale a alternativa correta:

a) O problema de min-edge-cover pode ser resolvido com algoritmos de fluxo máximo em tempo polinomial para grafos bipartidos.

b) Todo grafo k-colorável dá origem a um grafo (k-1)-colorável se qualquer vértice for retirado.

c) Se um grafo é bipartido então o maior grau do grafo é menor que o número cromático do grafo.

d) O problema de min-vertex-cover é mais difícil do que o problema de max-independent-set para grafos quaisquer.

e) N.D.A

Ideia original: Daniel Hosomi

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-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