MO405 - Questão para a prova oral


Número: 125

Enunciado: Sobre a Multiplicação de Vértices de um grafo G por um vetor h de inteiros não negativos - onde gera-se o grafo G ○ h -  é incorreto afirmar que: 

a) Se G é bipartido, então o grafo G ○ h também é bipartido.

b) χ(G ○ h) = ω( G ○ h ) para todo grafo perfeito G e para todo h.

c) Se G é imperfeito, então G ○ h pode ser perfeito.

d) Mesmo G não sendo bipartido, G ○ h pode ser bipartido.

e) N.D.A.

Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número: 124

Enunciado: Suponha que um grafo G represente uma rede de fofocas da seguinte forma.  Cada vértice é uma pessoa fofoqueira e cada aresta é uma via de comunicação bidirecional entre duas pessoas. Cada pessoa conhece um segredo que nenhuma outra sabe, e, quando duas pessoas se comunicam através de uma aresta, cada extremidade conta à outra tudo o que sabe.  Seja f(G) o número mínimo de comunicações bidirecionais necessárias para que todas as pessoas de G saibam os segredos de todas as outras.

Com relação a f(C₅), qual das afirmações a seguir é FALSA ?

a) Se excluirmos um canal de comunicação, f aumenta, ou seja,  f(C₅ − e) > f(C₅).

b) É possível diminuir f apenas reorganizando melhor os canais de comunicação: existe um grafo G com n(G) = n(C₅), e(G) = e(C₅) e f(G) < f(C₅).

c) É possível diminuir f incluindo um novo canal de comunicação:  f(C₅ + e) < f(G) para alguma aresta e.

d) Se uma nova pessoa for incluída ao grupo e possuir ao menos um canal de comunicação com as outras fofoqueiras, f aumentará: f(G) > f(C₅) para qualquer grafo conexo G de seis vértices.

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número:  123

Enunciado: Qual dos grafos a seguir, descritos utilizando a representação por interseção, possui uma 4-coloração total ?

A. {1}, {1,2}, {1,3}, {2,4}, {3,4}.

B. {1}, {1,2}, {1,2}, {2,3}, {3}.

C. {1,2}, {1,3,5}, {2,4,6}, {3,4}, {5,6}.

D. Todas as alternativas anteriores.

E. NDA.


Ideia original de: Lucas

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 122

Enunciado: Considerando "list coloring", qual das alternativas é correta?

a) O "chromatic number" é sempre menor que o "list chromatic number".

b) Computar o "list chromatic number" é pelo menos tão difícil quanto computar "chromatic number".

c) O valor do maior grau de um grafo qualquer é sempre menor que o "list chromatic number".

d) O "list chromatic number" de um grafo planar é sempre maior que o valor do maior grau + 1.

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 121

Enunciado:
Seja G um grafo aleatório de 4 vértices onde cada aresta está presente com uma probabilidade p. 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: 120

Enunciado: Quantas das seguintes propriedades o grafo G abaixo possui: bipartido, euleriano, hamiltoniano, perfeito, planar, classe 1?

a) 3

b) 5

c) 4

d) 2

e) NDA

MO405 - Questão para a prova oral

Número: 119

Enunciado: Seja G um grafo conexo com polinômio cromático  

k⁴ − 4k³ + 5k² − 2k.

Não podemos afirmar que:

a) G é perfeito.

b) G é planar e seu grafo dual é Euleriano.

c) G possui um matching perfeito.

d) G possui pelo menos um vértice de corte e uma aresta de corte.

e) NDA