MO 405 - Questão para prova oral (5° semana)

Número:

Enunciado: Considerando um grafo bipartido é incorreto dizer:

a) O índice de estabilidade (independence number) nem sempre é igual ao tamanho de uma das partições.

b) O máximo tamanho de emparelhamento sempre é igual ao mínimo tamanho de cobertura de vértice.

c) O máximo tamanho de conjunto independente sempre é igual ao mínimo tamanho de cobertura de aresta.

d) Seja k > 0. Todo grafo bipartido k-regular possui um emparelhamento perfeito.

e) nda

MO 405 - Questão para prova oral (4° semana)

Número:

Enunciado: Dado um conjunto de vértices de tamanho 10, o número de árvores que pode ser formado com este conjunto é:

a) 10⁸

b) 8¹⁰

c) 10¹⁰

d) 10¹²

e) nda

MO 405 - Questão para prova oral (3° semana)

Número:

Enunciado: A respeito de digrafos, qual das opções a seguir é incorreta?

a) A somatória dos graus de entrada dos vértices é igual a somatória dos graus de saída.

b) Todo digrafo fortemente conexo é euleriano.

c) Todo digrafo com o valor 1 para o grau de saida mínimo possui um ciclo.

d) Todo digrafo com n > 1 vertices contendo um ciclo de tamanho n é euleriano.

e) nda

MO 405 - Questão para prova oral (3° semana)

Número:

Enunciado: Qual das opções a seguir não é característica de uma árvore com n vertices (n > 1)?

a) G é conectado e não possui ciclos.

b) G é conectado e possui n - 1 arestas.

c) G possui n - 1 arestas e não possui ciclos.

d) Para u, v E V(G), G possui caminhos u, v.

e) nda

Ch. 1: What is a graph?

Número:

Enunciado: Qual das alternativas a seguir está incorreta? Considere apenas grafos simples.

a) Todo grafo completo possui um clique.

b) O complemento de um grafo completo é um grafo sem arestas.

c) A cintura de um grafo triangulo é igual a cintura de um grafo casa.

d) O grau de cada vertice em um grafo completo é igual ao número de vertices menos 1.

e) NDA