MO405 - Questão para a prova oral

Número: 097

Enunciado: As figuras abaixo correspondem a colorações das faces de C₃ □ C₃ imerso num toro (identificando a borda esquerda com a direita, e a borda superior com a inferior).  Qual delas representa uma coloração própria?

a)

b)

c)

d)

e) NDA

Ideia original de: Edgard H. Santos

MO405 - Questão para a prova oral

Número: 096

Enunciado: Dado o grafo G abaixo, o que podemos afirmar sobre o L(G)?

a) L(G) é Hamiltoniano e χ’(L(G))= 4

b) L(G) é planar, mas não é Hamiltoniano

c) L(G) é classe 1, mas não é planar

d) L(G) é Hamiltoniano, mas não é classe 1

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 095

Enunciado: Sabendo que G é um grafo simples que possui como fecho (closure) o grafo K₅, analise as afirmações abaixo e assinale a alternativa correta.

  
I - G é Hamiltoniano.
II - A conectividade de G é maior ou igual ao seu número de independência, ou seja: κ(G) ≥ α(G).
III - O grau mínimo de G é maior ou igual ao seu número de vértices dividido por 2, ou seja: δ(G) ≥ n(G)/2.
IV - G possui um ciclo gerador de tamanho 6. 


a) Apenas a afirmação I está correta.

b) Apenas a afirmação IV está incorreta.

c) As afirmações II e IV estão incorretas.

d) Três destas afirmações estão corretas.

e) N.D.A.




Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 094

Enunciado: Sobre o grafo abaixo:

assinale a alternativa INCORRETA :

a) Δ(G) = χ'(G)

b) χ'(G) = χ( L(G) )

c) κ(G) ≥ α(G) , e portanto possui um ciclo hamiltoniano.

d) χ(G) = ω(G)

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: 093

Enunciado: Qual das afirmações abaixo é incorreta sobre o produto cartesiano Cn □ Cm dos grafos Cn e Cm, para n, m ≥ 3?

a) Cn □ Cm pode ser imerso na esfera, sem cruzamentos.

b) se n for par ou m for par, χ'(Cn □ Cm) = 4

c) se k ≤ n, então Ck □ Cm é um menor de Cn □ Cm

d) se ambos n e m  forem ímpares, χ'(Cn □ Cm) = 5

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 092

Enunciado: Seja G um grafo simples com número de vértice n, número de arestas e e cintura g. Assinale a expressão que corresponde à fórmula do número máximo de arestas para que o grafo G seja planar.

a) (g - 1)(n - 2) / (g - 2) ≥ e

b) g(n - g) / (2(g - 2)) ≥ e

c) g(n - 2) / (g - 2) ≥ e

d) (2g + 1)(n - 2) / (g - 2) ≥ e

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número: 091

Enunciado: O crossing number do grafo de Petersen, desenhado abaixo, é igual a:

a) 1

b) 2

c)  3

d) 4

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: 090

Enunciado: Considere um grafo simples G que possui uma imersão(embedding) em uma esfera sem cruzamento de arestas. Sobre este grafo é INCORRETO afirmar que:

a) G possui espessura (thickness) estritamente maior que 1.

b) G possui uma imersão (embedding) planar.

c) G pode ser colorido com 5 cores.

d)  G não possui uma subdivisão do K₅ nem do K_3,3 

e) N.D.A


Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 089

Enunciado: Sobre imersões planares, podemos afirmar que:


A. Todo grafo planar possui uma imersão cujas faces são polígonos convexos.

B. Se H é um menor de G, então G contém uma subdivisão de H.

C. Se H é um subgrafo de G, então ν(G) ≤ ν(H).

D. O crossing number do K_3,5 é 4.

E. NDA.


Ideia original de: Lucas

MO405 - Questão para a prova oral

Número: 088

Enunciado: Identifique a alternativa CORRETA:


A) O gênus de todo grafo imersível no toro é  1.

B) Todo grafo 4-colorável é imersível no plano.

C) A espessura (thickness) de um grafo é sempre menor ou igual ao seu número de cruzamento mais um (ni(G)+1).

D) O grafo de Petersen contém uma subdivisão do K_5.

E) NDA


Autor(a): Cândida Nunes da Silva

MO405 - Questão para a prova oral

Número: 087

Enunciado: Qual o número de faces do grafo G gerado pelo produto cartesiano entre P₂ e K_1,100 ?

A) G não é planar

B) 101 faces

C) 198 faces

D) 202 faces

E) NDA

Ideia original de: Vinicius José Fortuna

MO405 - Questão para a prova oral


Número: 086

Enunciado: Sobre as afirmações a seguir:

I - Se G* é o grafo dual do grafo plano G, pode-se dizer que G* e G têm o mesmo número de arestas e vértices;
II - Os grafos duais das imersões no plano de um grafo planar G têm o mesmo número de arestas e vértices;
III - Se G é bipartido completo e δ(G) ≤ 2, então G é planar;


podemos dizer que:

a) Apenas I é verdadeira.
b) Apenas I e II são verdadeiras.
c) Apenas II é verdadeira.
d) Apenas III é verdadeira.
e) NDA

Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 085

Enunciado: De quantas maneiras podemos colorir as regiões A, B, C e D abaixo utilizando 4 cores distintas? Nota: regiões que compartilham uma fronteira devem ter cores distintas.

a) 84

b) 48

c) 96

d) 64

e) NDA


Ideia original de : Junior Fabian

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 084

Enunciado: Considere o grafo abaixo:

Os números de colorações próprias, usando 3 e 4 cores, respectivamente, são:

a) 15, 240

b) 15, 160

c) 30, 120

d) 30, 240

e) N.D.A.

Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 083

Enunciado: Qual é o polinômio cromático do grafo abaixo?

a) k²(k-1)⁵(k-2)

b) k(k-1)⁴ (k-2)³

c) k²(k-1)³(k-2)³

d) k(k-1)⁵(k-2)²

e) NDA


Ideia original de: Juliana Medeiros Destro 

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral 

Número: 082

Enunciado: A respeito de grafos cordais, qual das alternativas a seguir é correta?


a) Todo grafo sem ciclos é cordal.

b) Todo grafo planar é cordal.

c) Todo grafo bipartido completo é cordal.

d) O grafo de Petersen é cordal.

e) NDA

MO405 - Questão para a prova oral

Número: 081

Enunciado: Considere dois grafos G e H, onde H=G-e (H é obtido pela remoção de uma aresta e de G). Quantas das afirmações abaixo são falsas?

(I) Se G é um K₅,então H é planar.

(II) Se G é perfeito, então H é perfeito.
(III) Se G é planar, então H é planar e o dual de H é G.e (contração da aresta e em G).

a) 3

b) 2

c) 1

d) 0

 

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 080

Enunciado: Dado as seguintes afirmações, assinale a incorreta.

a) A soma dos comprimentos das faces de um grafo plano G é igual ao dobro do número de arestas de G.

b) O grafo dual do grafo dual de um grafo plano G não é, necessariamente, isomorfo a G.

c) Se um grafo plano G é bipartido, então seu grafo dual (G* é euleriano.

d) Um grafo cordal possui uma ordenação simplicial.

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 079

Enunciado: Determine a soma dos comprimentos de todas as faces do grafo plano abaixo:

a) 20

b) 21

c) 22

d) 23

e) NDA

Ideia original de: Jefferson Capovilla

MO405 - Questão para a prova oral

Número: 078

Enunciado: Considere as afirmações a seguir, referentes a coloração de vértices.

I) Todo grafo estrela é crítico.

II) Todo grafo Kn é n-crítico e, portanto, é (n-1)-aresta-conexo.

III) O grafo Kx ∨ Cy, com x>0 e y>0, é crítico.

Podemos dizer que:

a) Apenas  I é verdadeira.
b) Apenas I e II são verdadeiras.
c) Apenas II é verdadeira.
d) Apenas II e III são verdadeiras.
e) NDA

Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 077

Enunciado: De acordo com as afirmações abaixo, e lembrando que o produto cartesiano G □ H de G e H é definido como:

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

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

assinale a alternativa correta:

I. O produto cartesiano de grafos bipartidos é um grafo bipartido;
II. Se o produto cartesiano de G e Km tem um conjunto independente de tamanho k, então G tem um subgrafo induzido de ordem k com número cromático no máximo m;
III. Nenhum ciclo pode ser representado por um grafo de intervalos.

a) Somente I e II estão corretas;

b)  Somente I e III estão corretas; 

c) Somente I está correta;

d) Todas estão corretas;

e) NDA.

 Ideia original de: Rafael L. Gomes

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