MO405 - Questão para a prova oral

Número:

Enunciado:
A seguir o grafo G:

Analise as afirmações abaixo e assinale a alternativa correta:
I - O grafo G é hamiltoniano;
II - χ(G)=3;
III - χ'(G)=3;
IV- O grafo dual de G possui 10 faces

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

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo simples. Qual dos grafos a seguir pertence a Classe 1? Sabendo que a Classe 1 é representada por χ(G) = Δ(G).

A. Grafo Completo K7
B. Petersen
C. Grafo Completo K5
D. Grafo k-regular
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Sabendo que a "espessura" de um grafo G é o número mínimo de grafos planares em uma decomposição de G em grafos planares. E o "número de cruzamentos" de um grafo G é o número mínimo de cruzamentos em um desenho de G no plano. O valor da espessura e o número de cruzamentos do grafo de Peterson são respectivamentes:

A. 1 e 1
B. 1 e 2
C. 2 e 1
D. 2 e 2
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Um grafo planar G com duas faces de tamanho 3 e três faces de tamanho 4. Sabendo que G é um grafo simples e regular, i.e. que todos os seus vértices têm o mesmo grau, determine o número V de vértices e o grau d comum a todos o vértices de G.

A. V = 6 e d = 4
B. V = 4 e d = 6
C. V = 6 e d = 3
D. V = 8 e d = 3
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja um grafo qualquer G. O que podemos dizer sobre o seu número cromático?

A. χ(G) ≤ Δ
B. χ(G) ≤ Δ +1
C. χ(G) = ω
D. χ(G) > ω
E. NDA

Ideia original de: Zhenlei Ji