MO405 - Questão para a prova oral

Número:


Enunciado: Seja G um grafo, avalie as seguintes alternativas:


a) Para qualquer k > 0, todo G k-regular tem um matching perfeito.


b) Se n(G) for ímpar, G não possui um matching perfeito.


c) O tamanho de um matching de G é igual à metade do número de arestas de G


d) Seja G um n-path, o β(G) = n/2


e) NDA


Ideia original de: Rafael Werneck

MO405 - Questão para a prova oral

Número:

Enunciado: Dada a seguinte sequência de Prüfer (11111), podemos afirmar:

a) O grafo possui 8 vértices.

b) O grafo é uma estrela.

c) O grafo é desconexo.

d) Pode-se gerar dois ou mais grafos à partir dessa sequência.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Dado o dígrafo a seguir, qual é a alternativa correta?

a) O dígrafo possui um kernel.

b) O dígrafo é fracamente conectado.

c) Contém uma trilha euleriana.

d) É um dígrafo funcional.

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Dado o seguinte grafo a seguir, qual é o seu número cromático?

a) 1

b) 2  

c) 3

d) 4

e) NDA

Inicial

Blog utilizado para postar questões para a matéria de Teoria dos GrafosI (MO405)