MO405 - Questão para a prova oral

Número:

Enunciado: Sobre a coloração de vértices de grafos simples é incorreto afirmar que:

A. Toda árvore com dois ou mais vértices é 2-colorível.
B. Ao se remover uma aresta de K_n o número cromático do grafo resultante diminui uma unidade, portanto, K_n é n-crítico (n-critical).
C. O algoritmo guloso de coloração sempre encontra uma coloração ótima para ciclos de tamanho par, independentemente da ordem em que os vértices são percorridos.
D. Se um grafo com n vértices tem α = (1 + n - ω), então χ = ω.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes afirmações:

I - Todo caminho disjunto nas arestas também é disjunto nos vértices.
II - Todo caminho maximal em uma árvore é uma orelha da árvore.
III - O grafo linha de C_n é C_n, e o grafo linha de K_n é K_n(n-1)/2.
IV - Seja N uma rede composta pelos vértices s e t, e um digrafo D bipartido nos conjuntos X e Y com capacidades associadas aos arcos. Considere que s é ligado a todo vértice de X, e todo vértice de Y é ligado a t, por arcos com capacidade infinita. A capacidade de um corte mínimo corresponde a soma total da capacidade dos arcos de D.

Podemos afirmar que são verdadeiras somente as afirmações:

A. I, II e III.
B. II, III e IV.
C. III e IV.
D. IV.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Considere as seguinte afirmações:

I - Todo grafo completo tem um 1-factor.
II - Todo grafo regular tem um 2-factor.
III - Seja k e k', repectivamente, a conectividade (de vértices) e a conectividade de arestas de um grafo. Então k=k'=3 sempre que o grafo for 3-regular.
IV - Seja G um grafo simples e H o grafo obtido removendo-se as arestas de corte de G. Os blocos de G correspondem às arestas de corte de G e as componentes conexas de H.

Podemos afirmar que são verdadeiras somente as afirmações:

A. I, II e III.
B. I, II, III e IV.
C. III.
D. IV.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:


Enunciado: Considere o seguinte procedimento iterativo. Inicialmente é fornecida como entrada uma árvore T e temos um conjunto M vazio. Na i-ésima iteração, recebemos a árvore da iteração anterior,  e removemos dela todos os seus vértices folha. Considere que na primeira iteração (i=1) a árvore recebida é T. Além disso, se i for impar acrescentamos em M as arestas removidas da árvore durante a iteração. Este processo termina quando a árvore recebida não possuir vértices. No final deste procedimento, podemos afirmar que:

A. M é sempre um emparelhamento.
B. M é sempre uma cobertura por arestas.
C. M é um emparelhamento perfeito, se T possuir tal emparelhamento.
D. M é um emparelhamento máximo, se T possuir uma quantidade impar de arestas.
E. NDA

Ideia original de: Lucas