MO405 - Questão para a prova oral

Número:

Enunciado:
Considere um grafo bipartido G e um emparelhamento máximo M. Podemos afirmar que:

a) Todo caminho M-alternante possui as duas extremidades saturadas por M.

b) M é o único emparelhamento máximo em G.

c) Todo emparelhamento maximal possui o mesmo tamanho de M.

d) Não existem caminhos M-aumentantes em G.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja T uma árvore com número par de vértices, representada pelo código de Prufer C. Nem sempre podemos afirmar que:

a) Se i é o número que mais vezes aparece em C, então o vértice i tem grau máximo em T.

b) Se i é o número que menos vezes aparece em C, então o vértice i tem grau mínimo em T.

c) Se todos os números de C são distintos, então T possui exatamente 2 folhas.

d) Se todos números de C são ímpares, então pelo menos metade dos nós de T são folhas.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo conexo não orientado com uma aresta de corte. Suponha que G é o grafo subjacente do dígrafo D. Podemos afirmar que:

a) D possui pelo menos 2 componentes fracamente conexas.

b) D possui pelo menos 2 componentes fortemente conexas.

c) D não possui componentes fortemente conexas.

d) Todos os dígrafos obtidos a partir do grafo subjacente G são isomorfos a D.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo par com um conjunto não vazio de arestas. Podemos afirmar que:

a) Somente a trilha máxima é euleriana.

b) Toda trilha maximal é euleriana.

c) Somente a trilha máxima é fechada.

d) Toda trilha maximal é fechada.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo bipartido que aceita uma decomposição em ciclos. Podemos afirmar que:

a) A cintura é ímpar.

b) O número cromático é igual a 2.

c) G é conexo.

d) G não é planar.

e) NDA