MO405 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa incorreta em relação ao limite superior de coloração.

a) χ(G) ≤ Δ(G) + 1, pela coloração gulosa.


b) χ(G) ≤ 1 + max_i min{d_i, i - 1}, em que d_1 ≥ d_2 ≥ ... ≥ d_n é a sequencia de graus de G. 


c) χ(G) ≤ Δ(G), se o grafo é completo.


d) χ(G) ≤ 1 + max_{H ⊆ G} δ(H), sendo H subgrafo k-crítico de G.


e) NDA


Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando a rede abaixo, assinale a alternativa que corresponda ao fluxo em cada aresta após a 3ª iteração do algoritmo de fluxo máximo.
OBS: A escolha do vértice a ser visitado é feita na ordem alfabética.

a)

b)

c)

d)

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Dadas as seguintes afirmações, assinale a alternativa correta:

I - Um path Pn possui n-1 blocos.

II - O grafo K5 possui 2 1-factor e 1 2-factor.

III - Um path e uma estrela, com o mesmo número de vértices, possuem a mesma quantidade de blocos.

IV - Seja F um bond de um grafo, então |F| = δ(G).

a) As alternativas I e II estão corretas.

b) As alternativas I e III estão corretas.

c) As alternativas II e IV estão corretas.

d) As alternativas III e IV estão corretas.

e) NDA

Ideia original de: Rafael de Oliveira Werneck