MO405 - Questão para a prova oral

Número:

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

Número:

Enunciado: Dado um grafo simples G, podemos afirmar que temos um matróide se os conjuntos independentes são todos os subconjuntos de E(G) que:

A. Possuem ao menos um ciclo.
B. São caminhos.
C. Formam um subgrafo de G com grau máximo menor ou igual a 2.
D. São cliques.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com n vértices númerados de 1 a n (v₁, ... , v_n). A multiplicação de vértices de um grafo G por um vetor de inteiros não-negativos h = (h₁, ... , h_n) consiste em um grafo H contendo h_i cópias do vértice v_i de G. Além disso, dois vértices u_i e u_j em H, cópias dos vértices v_i e v_j em G, respectivamente, são adjacentes se, e somente se, os vértices v_i e v_j são adjacentes. Se H é o grafo obtido do resultado da multiplicação de vértices de G por h, e d(v_i) é o grau do vértice v_i em G, podemos afirmar que:

A. χ(H) > χ(G).
B. ω(H) > ω(G).
C. α(H) > α(G).
D. e(H) = ( d(v₁)h₁ + ... + d(v_n)h_n ) / 2.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Pode-se afirmar que o grafo abaixo:

A. É hamiltoniano.
B. É um Snark.
C. É 2-aresta-colorível.
D. Não possui um cycle double cover (CDC).
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Qual das afirmativas está correta:

A. Seja G um ciclo, o grafo closure de G é o próprio G.
B. Se G é um grafo simples, conexo e com uma aresta de corte e, então, G possui um caminho hamiltoniano se, e somente se, as componente de G - e possuírem um caminho hamiltoniano.
C. Se G não possui um ciclo hamiltoniano, então, o grafo linha de G também não possui um ciclo hamiltoniano.
D. K₅ é o menor grafo completo que possui dois ciclos hamiltonianos disjuntos nas arestas.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre imersão planar, podemos afirmar que:

A. Qualquer grafo planar possui uma imersão cujas faces são polígonos convexos.
B. Todo grafo planar possui K₅ como um grafo minor.
C. Se H possui crossing number igual a x e constitui um subgrafo de G, então o crossing number de G é pelo menos x.
D. O crossing number do K₆ é 2.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Qual das seguintes afirmações está correta:

A. Árvores constituem uma classe hereditária de grafos.
B. Todo cíclo é um grafo perfeito.
C. Se um grafo simples e conexo possui n vértices, m arestas, cintura c, e ao menos um ciclo, então ele não pode ser planar se m > (c(n - 2)) / (c - 2).
D. O grafo de Petersen é planar.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

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

A. Todo grafo completo multipartido também é bipartido.
B. Se um grafo possui uma k-coloração própria então ele tem pelo menos n(n-1) arestas.
C. Todo grafo k-crítico é k-aresta-conexo.
D. Todo grafo simples com número cromático χ possui um Kχ como subgrafo.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

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:

Enunciado: Considere as seguintes afirmações:

I - Todo caminho disjunto nas arestas também é disjunto nos vértices.
II - Todo caminho maximal em uma árvore é uma orelha da árvore.
III - O grafo linha de C_n é C_n, e o grafo linha de K_n é K_n(n-1)/2.
IV - Seja N uma rede composta pelos vértices s e t, e um digrafo D bipartido nos conjuntos X e Y com capacidades associadas aos arcos. Considere que s é ligado a todo vértice de X, e todo vértice de Y é ligado a t, por arcos com capacidade infinita. A capacidade de um corte mínimo corresponde a soma total da capacidade dos arcos de D.

Podemos afirmar que são verdadeiras somente as afirmações:

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

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Considere as seguinte afirmações:

I - Todo grafo completo tem um 1-factor.
II - Todo grafo regular tem um 2-factor.
III - Seja k e k', repectivamente, a conectividade (de vértices) e a conectividade de arestas de um grafo. Então k=k'=3 sempre que o grafo for 3-regular.
IV - Seja G um grafo simples e H o grafo obtido removendo-se as arestas de corte de G. Os blocos de G correspondem às arestas de corte de G e as componentes conexas de H.

Podemos afirmar que são verdadeiras somente as afirmações:

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

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:


Enunciado: Considere o seguinte procedimento iterativo. Inicialmente é fornecida como entrada uma árvore T e temos um conjunto M vazio. Na i-ésima iteração, recebemos a árvore da iteração anterior,  e removemos dela todos os seus vértices folha. Considere que na primeira iteração (i=1) a árvore recebida é T. Além disso, se i for impar acrescentamos em M as arestas removidas da árvore durante a iteração. Este processo termina quando a árvore recebida não possuir vértices. No final deste procedimento, podemos afirmar que:

A. M é sempre um emparelhamento.
B. M é sempre uma cobertura por arestas.
C. M é um emparelhamento perfeito, se T possuir tal emparelhamento.
D. M é um emparelhamento máximo, se T possuir uma quantidade impar de arestas.
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja S_n o grafo estrela com n + 1 vértices. Este grafo possui um graceful labeling se, e somente se, o seu vértice central for rotulado como:

A. 0
B. 1
C. n - 1
D. 0 ou n - 1
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com grau mínimo 10. Qual dos seguintes grafos podemos afirmar certamente que sempre será um subgrafo de G ?

A. K₁₁
B. K_5,5
C. Um grafo simples conexo e acíclico com 10 arestas
D. Um grafo simples com 10 cíclos
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com n vértices. Considere que d(G) e D(G) são, respectivamente, o grau mínimo e máximo de G. Dado o grafo complementar de G, denotado por H, podemos afirmar que d(H) e D(H) correspondem, respectivamente, à:


A. d(G) e D(G)
B. n - d(G) e n - D(G)
C. n - D(G) e n - d(G)
D. n - D(G) - 1 e n - d(G) - 1
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Dado um grafo G com n vértices, qual a maior quantidade de arestas que um subgrafo acíclico de G pode ter ?

A. n² - n
B. n² / 2
C. n / 2
D. n -1
E. NDA

Ideia original de: Lucas