MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 076

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

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

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número: 075

Enunciado: Sobre coloração de grafos, qual afirmativa está correta?

a) O grafo de Petersen é 3-cromático e 3-crítico.

b) Se um grafo é 10-crítico podemos afirmar que seu grau mínimo é maior ou igual a 9.

c) Um ciclo com 255 vértices é 5-crítico.

d) Um grafo de intervalos que possui um número de clique (número máximo de vértices numa clique) igual a 180 possui número cromático igual a 90.

e) NDA

Ideia original de: Edgard H. Santos

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 074

Enunciado: Suponha que você tenha que agendar provas finais e que tenha que evitar que um aluno faça mais de uma prova num mesmo dia. Na tabela abaixo, as disciplinas estão representadas com os números 1, 2, 3, 4, 5, 6, 7. Um * na posição i, j representa que a disciplina i tem pelo menos um aluno em comum com a disciplina j, de modo que você não pode colocar uma prova da disciplina i e da disciplina j no mesmo dia.  

.	1	2	3	4	5	6	7
1	.	*	*	*	-	*	*
2	*	.	*	-	-	-	*
3	*	*	.	*	-	-	-
4	*	-	*	.	*	*	-
5	-	-	-	*	.	*	-
6	*	-	-	*	*	.	*
7	*	*	-	-	-	*	.

Qual é o menor número de dias que você precisa para agendar todas as provas?

a) 4

b) 5

c) 6

d) 7

e) NDA


Ideia original de : Junior Fabian

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 073

Enunciado: Considere o grafo G a seguir:

Assinele a alternativa correta:

a) ω(G) = Δ(G)

b) χ(G) > α(G) 

c) χ(G) = δ(G)

d) χ(G) < Δ(G) - 1

e) N.D.A

Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 072

Enunciado: Sobre a coloração de vértices de grafos simples é incorreto afirmar que:

A. Toda árvore com dois ou mais vértices é 2-colorível.

B. Ao se remover uma aresta de K_n o número cromático do grafo resultante diminui uma unidade, portanto, K_n é n-crítico (n-critical).

C. O algoritmo guloso de coloração sempre encontra uma coloração ótima para ciclos de tamanho par, independentemente da ordem em que os vértices são percorridos.

D. Se um grafo com n vértices tem α = (1 + n - ω), então χ = ω.

E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número: 071

Enunciado: Lembrando que:

V(G □ H) = V(G) × V(H), e

E(G □ H) = {(u,v)(u',v') | (u ∈ V(G) e vv' ∈ E(H)) ou (uu' ∈ E(G) e v ∈ V(H))},

marque a alternativa correta:

a) Δ(G □ H) = max [ Δ(G), Δ(H) ]

b) Δ(G □ H) = Δ(G) + Δ(H)

c) χ(G □ H) = min [ χ(G), χ(H) ]

d)  χ(G □ H) = χ(G) + χ(H)

e) N.D.A


Ideia original de: Thierry Pinheiro Moreira

MO405 - Questão para a prova oral

Número: 070

Enunciado: Lembrando que:

V(G □ H) = V(G) × V(H), e
E(G □ H) = {(u,v)(u',v') | (u ∈ V(G) e vv' ∈ E(H)) ou (uu' ∈ E(G) e v ∈ V(H))}

V(G ∨ H) = V(G) ∪ V(H), sendo V(G) e V(H) disjuntos, e
E(G ∨ H) = E(G) ∪ E(H)

O que podemos dizer sobre as afirmações a seguir ?

I - Todo grafo G completo com n(G) > 1 é crítico (color-critical)
II - O número cromático de G □ H é X(G) + X(H)
III - O número cromático de G ∨ H é max{X(G), X(H)}

a) Apenas II e III estão corretas
b) Apenas II está correta
c) Apenas I está correta
d) As três afirmações estão corretas
e) NDA

Ideia original de: Vitor Afonso