MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo aleatório de 4 vértices. Sabendo que a probabilidade de G ser um grafo completo é igual a 0,000064. Qual é a probabilidade do grafo G ser um ciclo?

A. 0,000256
B. 0,001024
C. 0,004096
D. 0,016384
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Sobre as afirmações a seguir:

I- Os conjuntos independentes de um grafo são os conjuntos independentes de um matróide.
II- Todo matróide particionado é um matróide transversal
III- O valor R(3,3), número de Ramsey, é 6
IV- Seja T uma árvore geradora do grafo cubo Q7, então existe uma aresta de Q7 diferente das arestas de T cuja adição em T cria um ciclo de tamanho pelo menos 12

Quais são as  INCORRETAS?

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

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G o grafo abaixo.

Considerando o grafo G como entrada do programa MCS (Maximum Cardinality Search). Qual é a ordem dos vértices retornado pelo programa?

A. 271643589
B. 271634859
C. 271648359
D. 271643859
E. NDA

Ideia original de: Zhenlei Ji

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

MO405 - Questão para a prova oral

Número:

Enunciado:
Sejam os grafos G e H. Qual é o valor de χ(G v H), ou seja o número cromático do join dos grafos G e H?

A. χ(G) + χ(H)
B. média(χ(G), χ(H))
C. min(χ(G), χ(H))
D. max(χ(G), χ(H))
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado: Sejam G e H grafos simples. Qual é o valor de κ(G v H), ou seja a conetividade do join dos grafos G e H?

a) v(G) + κ(H)
b) v(H) + κ(G)
c) min(v(G) + κ(H), v(H) + κ(G))
d) min(v(G) + κ(G), v(H) + κ(H))
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Dado o grafo abaixo, calcule quantos blocos possui.


a) 5
b) 6
c) 7
d) 8
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Qual a soma dos valores da transversal de menor peso da matriz abaixo:


a) 31
b) 32
c) 33
d) 34
e) NDA

Ideia original de: Zhenlei Ji

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