MO405 - Questão para a prova oral

Número:

Enunciado:
Qual dos grafos a seguir possui um emparelhamento perfeito?

a) Grafo completo K5.
b) Grafo com o seguinte código de Prüfer: 21214.
c) Grafo com a seguinte sequência: 33211
d) Grafo bipartido 5-regular.
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Considere o grafo G da figura seguinte:


Designemos por τ(G) o número de árvores geradoras de G. Escolha a opção correta:

a) G é um grafo birpatido e τ(G)=14
b) G não possui aresta de corte e τ(G)=12
c) G é um grafo completo K4 e τ(G)=16
d) G não possui vértice de corte e τ(G)=18
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja T uma árvore geradora de um grafo G com n vértices. Sabendo que o grau máximo da árvore T é m. Podemos afirmar que:

a) T possui n arestas e número de folhas pelo menos m.
b) T possui n - 1 arestas e número de folhas no máximo m.
c) T possui n arestas e número de folhas igual a m.
d) T possui n - 1 arestas e número de folhas pelo menos m.
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo simples, conexo, bipartido, e com todos os vértices de grau 4. Das afirmações seguintes apenas uma é compatível com as hipóteses anteriores.
Qual delas?

a) G pode ter 9 vértices e 18 arestas
b) G pode ter 8 vértices e 32 arestas
c) G pode ter 8 vértices e 16 arestas
d) G pode ter 9 vértices e 36 arestas
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Considere o grafo G da figura seguinte:



Designemos por χ(G) o número cromáticos de G. Escolha a opção correta:

a) G é um grafo bipartido e χ(G)=3
b) G não é um grafo bipartido e χ(G)=3
c) G é um grafo bipartido e χ(G)=4
d) G não é um grafo bipartido e χ(G)=4
e) NDA

Ideia original de: Zhenlei Ji