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
sábado, 28 de abril de 2012
MO405 - Questão para a prova oral
Enunciado: Considere dois grafos G e H. Qual é o valor de χ(G ∨ H), ou seja, o número cromático do join dos grafos G e H? Lembrando que G ∨ H é a união disjunta de G com H onde são adicionadas as arestas {xy | x ∈ V(G) e y ∈ V(H)}.
A. χ(G) + χ(H)
B. média(χ(G), χ(H))
C. min(χ(G), χ(H))
D. max(χ(G), χ(H))
E. NDA
Ideia original de: Zhenlei Ji
sexta-feira, 27 de abril de 2012
MO405 - Questão para a prova oral
Enunciado: Assinale a alternativa INCORRETA:
a) Um grafo completo de N ≥ 1 vértices, tem como número cromático o próprio N.
b) Um ciclo sempre pode ser colorido com três cores.
c) Retirando-se uma aresta de um grafo completo de N vértices, o grafo resultante pode ser colorido com N-1 cores.
d) Para qualquer grafo, o número cromático é menor ou igual ao grau máximo.
e) N.D.A
Ideia original de: Marlon F. de Alcantara
segunda-feira, 23 de abril de 2012
MO405 - Questão para a prova oral
Enunciado:
Seja T uma árvore geradora de um grafo G com n vértices. Sabendo que T não tem vértices de grau 2, podemos afirmar que:
a) T possui n arestas e número de folhas pelo menos 2.
b) T possui n - 1 arestas e pode ter número de folhas igual a n/2.
c) T possui n arestas e pode ter número de folhas igual a n - 1.
d) T possui n - 1 arestas e número de folhas pelo menos 1 + n/2.
e) NDA
Ideia original de: Zhenlei Ji
sábado, 21 de abril de 2012
MO405 - Questão para a prova oral
Número: 065
Enunciado: Considere a rede e o fluxo f apresentados na figura. Cada aresta da rede possui uma capacidade e um fluxo, sendo que o fluxo é o valor entre parênteses. O fluxo máximo da rede e o valor do fluxo (val(f)) são, respectivamente:
Número: 065
Enunciado: Considere a rede e o fluxo f apresentados na figura. Cada aresta da rede possui uma capacidade e um fluxo, sendo que o fluxo é o valor entre parênteses. O fluxo máximo da rede e o valor do fluxo (val(f)) são, respectivamente:
a) 7, 7
b) 6, 5
c) 6, 3
d) 7, 4
e) NDA
Ideia original de: Vitor Afonso
MO405 - Questão para a prova oral
Número: 064
Enunciado: Suponha que n(G), e(G) e L(G) denotem, respectivamente, o número de vértices, o número de arestas e o grafo linha de um grafo G. Qual das implicações abaixo é FALSA?
b) Se G é um ciclo, então L(L(G)) = G.
c) Se G é uma estrela com i folhas, então L(G) = Ki.
d) Se G é um caminho com n vértices, então L(G) é um caminho com n-1 vértices.
e) NDA
Número: 064
Enunciado: Suponha que n(G), e(G) e L(G) denotem, respectivamente, o número de vértices, o número de arestas e o grafo linha de um grafo G. Qual das implicações abaixo é FALSA?
a) Se G é um K4, então n(G) + e(G) = n(L(G)) + e(L(G)).
b) Se G é um ciclo, então L(L(G)) = G.
c) Se G é uma estrela com i folhas, então L(G) = Ki.
d) Se G é um caminho com n vértices, então L(G) é um caminho com n-1 vértices.
e) NDA
MO405 - Questão para a prova oral
Número: 063
Enunciado: Observando o grafo abaixo, podemos afirmar que:
b) Sua conectividade de vértices é igual à sua conectividade de arestas.
c) Admite uma decomposição em orelhas fechadas.
d) É um grafo 2-conexo.
e) NDA
Número: 063
Enunciado: Observando o grafo abaixo, podemos afirmar que:
a) Possui quatro orelhas fechadas.
b) Sua conectividade de vértices é igual à sua conectividade de arestas.
c) Admite uma decomposição em orelhas fechadas.
d) É um grafo 2-conexo.
e) NDA
Ideia original de: Edgard H. Santos
MO405 - Questão para a prova oral
Número: 062
Enunciado: Considere as seguintes afirmações e assinale a alternativa INCORRETA.
Número: 062
Enunciado: Considere as seguintes afirmações e assinale a alternativa INCORRETA.
- A soma entre a quantidade de arestas e a quantidade de vértices em um grafo linha é igual a esta soma no grafo original.
- Em todo grafo 3-regular, k'(G) = k(G).
- Todo grafo 2-conectado é 2-aresta-conectado.
- Todo grafo 2-conectado possui uma orientação que o torne fortemente conexo.
- NDA
MO405 - Questão para a prova oral
Número: 061
Enunciado: A figura a seguir representa um trecho de uma rede com fluxo passando nela. Os valores do fluxo em AB, CA e CB são desconhecidos. Supondo que todos os valores de fluxo são não negativos, qual é o menor valor que x2 pode ter?
Enunciado: A figura a seguir representa um trecho de uma rede com fluxo passando nela. Os valores do fluxo em AB, CA e CB são desconhecidos. Supondo que todos os valores de fluxo são não negativos, qual é o menor valor que x2 pode ter?
b) x2 = 50
c) x2 = 40
d) x2 = 30
e) NDA
Ideia original de : Junior Fabian
MO405 - Questão para a prova oral
Enunciado: Considere as seguintes afirmações:
I - Caminhos disjuntos nas arestas também são disjuntos nos vértices.
II - Todo caminho maximal em uma árvore é uma orelha da árvore.
III - O grafo linha de Cn é Cn, e o grafo linha de Kn é Kn(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 à soma total da capacidade dos arcos de D.
Podemos garantir 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
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? Lembrando que o join é a soma dos grafos G e H acrescida de arestas de cada vértice de G para cada vértice de H.
a) κ(G) + κ(H)
b) κ(H) * κ(G)
c) min(n(G) + κ(H), n(H) + κ(G))
d) min(n(G) + κ(G), n(H) + κ(H))
e) NDA
Ideia original de: Zhenlei Ji
MO405 - Questão para a prova oral
Enunciado:
Considere a rede abaixo, onde a notação “(f)c” representa os valores de fluxo (f) e capacidade (c) em cada aresta. Qual alternativa a seguir mostra corretamente a sequência de
vértices de um caminho aumentante e valor máximo de fluxo adicional que pode ser enviado por este caminho?
b) a-e-f-d, 4
c) a-b-c-d, 2
d) a-b-c-e-f-d, 1
e) NDA
Ideia original de: Jefferson Capovilla
domingo, 15 de abril de 2012
MO405 - Questão para a prova oral
Enunciado: Marque a alternativa correta considerando um grafo bipartido Km,n com m ≥ 1, n ≥ 1, e bipartição X, Y, onde |X| = m e |Y| = n:
a) o grafo tem um vértice de corte em X se e somente se m < n
b) Km,n é p-conectado se p < δ(Km,n)
c) κ(Km,n) < κ’(Km,n)
d) Km,n é n-conectado somente se n < m
e) NDA
Ideia original de: Juliana M Destro
MO405 - Questão para a prova oral
Número: 054
Enunciado: Qual é o valor da conectividade por vértices, κ(G), e da conectividade por arestas, κ'(G), do grafo G seguinte, onde Kn representa um grafo completo com n vértices e n ≥ 9:
b) κ(G) = 2 e κ'(G) = 8
c) κ(G) = 8 e κ'(G) = 4
d) κ(G) = 8 e κ'(G) = 16
e) NDA
Ideia original de : Junior Fabian
MO405 - Questão para a prova oral
Número: 052
Enunciado: A respeito de conectividade em grafos, é correto dizer:
a) Em todo grafo simples, a conectividade de vértices é sempre maior ou igual à conectividade de arestas.
b) Para m ≥ 1, um grafo completo de m vértices tem conectividade de arestas igual a m.
c) Para n ≥ 2, a conectividade de vértices de um grafo completo de n vertices menos uma aresta é n - 1.
d) A conectividade de vértices de um grafo Km,n é max(m,n), sendo n ≥ 1 e m ≥ 1.
e)NDA
MO405 - Questão para a prova oral
Número: 051
Enunciado: Dadas as seguintes afirmações, assinale a alternativa correta:
I - Um caminho com n vértices possui n - 1 blocos.
II - O grafo K5 possui dois 1-fatores e um 2-fator.
III - Um caminho e uma estrela com o mesmo número de vértices possuem a mesma quantidade de blocos.
IV - Se F é um bond de um grafo G, então |F| = δ(G).
a) As alternativas I e II estão corretas.
b) As alternativas II e III estão corretas.
c) As alternativas III e IV estão corretas.
d) As alternativas IV e I estão corretas.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sábado, 14 de abril de 2012
MO405 - Questão para a prova oral
Enunciado: Considere as seguinte afirmações:
I - Todo grafo completo tem um 1-fator.
II - Todo grafo regular tem um 2-fator.
III - Sejam κ e κ', repectivamente, a conectividade (de vértices) e a conectividade de arestas de um grafo. Então κ=κ'=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 às 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: 048
Enunciado: Sobre conectividade em grafos, marque a alternativa errada:
a) Se G é o grafo de Petersen, então κ(G) = 2.
b) Se G é o grafo de Petersen, então κ'(G) = 3.
c) Se dois blocos possuem um vértice em comum, este vértice é de corte.
d) Se G é um grafo simples e H é o seu grafo de blocos e pontos de corte , então as folhas de H correspondem a blocos de G.
e) NDA
Ideia original de: Thierry Pinheiro Moreira
Número: 048
Enunciado: Sobre conectividade em grafos, marque a alternativa errada:
a) Se G é o grafo de Petersen, então κ(G) = 2.
b) Se G é o grafo de Petersen, então κ'(G) = 3.
c) Se dois blocos possuem um vértice em comum, este vértice é de corte.
d) Se G é um grafo simples e H é o seu grafo de blocos e pontos de corte , então as folhas de H correspondem a blocos de G.
e) NDA
Ideia original de: Thierry Pinheiro Moreira
domingo, 8 de abril de 2012
MO405 - Questão para a prova oral
Número: 044
Enunciado: Seja G um grafo bipartido ponderado, com bipartição (X,Y), onde |X| = |Y|, e seja M sua matriz de pesos não negativos, onde as linhas de M correspondem a X e as colunas a Y. Podemos afirmar que:
a) Existe uma transversal máxima de M que contém uma das arestas de maior peso em G.
b) Dada uma cobertura ponderada (u,v) de G, se uma transversal de M não possui o mesmo valor de (u,v), então a transversal não é máxima.
c) Um emparelhamento de G corresponde a uma transversal de M.
d) Uma transversal de M corresponde a um emparelhamento maximal (ou seja, não contido propriamente em nenhum outro emparelhamento) de G.
e) NDA
Número: 044
Enunciado: Seja G um grafo bipartido ponderado, com bipartição (X,Y), onde |X| = |Y|, e seja M sua matriz de pesos não negativos, onde as linhas de M correspondem a X e as colunas a Y. Podemos afirmar que:
a) Existe uma transversal máxima de M que contém uma das arestas de maior peso em G.
b) Dada uma cobertura ponderada (u,v) de G, se uma transversal de M não possui o mesmo valor de (u,v), então a transversal não é máxima.
c) Um emparelhamento de G corresponde a uma transversal de M.
d) Uma transversal de M corresponde a um emparelhamento maximal (ou seja, não contido propriamente em nenhum outro emparelhamento) de G.
e) NDA
MO405 - Questão para a prova oral
Enunciado: Considere que o caminho P = ( (2,6), (6,1), (1,7), (7,3), (3,9), (9,5), (5,8) ) é alternante para um emparelhamento M = ( (6,1), (7,3), (9,5) ) de um grafo bipartido G com nove vértices. Podemos afirmar que:
a) | M | = α'(G)
b)
| P ∆
M | = α'(G)
c)
| P | + | M | = α'(G)
d)
| M | = α(G)
e)
NDA
MO405 - Questão para a prova oral
Enunciado: Considere o seguinte procedimento iterativo tendo como entrada uma árvore T. Inicialmente formamos um conjunto M vazio. Na i-ésima iteração, recebemos a árvore da iteração anterior (ou T quando i=1) e removemos dela todos os seus vértices folha. Além disso, se i for ímpar, acrescentamos a M as arestas removidas da árvore durante esta iteração. Este processo termina quando a árvore recebida não possuir vértices. No final deste procedimento, podemos afirmar que:
A. M é um emparelhamento perfeito, se T possuir tal emparelhamento.
B. M é um emparelhamento máximo, se T possuir uma quantidade impar de arestas.
C. M é sempre um emparelhamento.
D. M é sempre uma cobertura por arestas.
E. NDA
Ideia original de: Lucas de Oliveira
domingo, 1 de abril de 2012
MO405 - Questão para a prova oral
Número: 040
Enunciado: Dado o grafo G abaixo, o que podemos afirmar? Lembrando que parâmetros sem linha (α e β) se referem a conjuntos de vértices, enquanto que os com linha (α' e β') se referem a arestas. Além disso, parâmetros com a letra grega alfa (α e α') se referem a elementos que não se tocam, enquanto que beta (β e β') indica coberturas.
a) α' (G)+β' (G)≤n(G)
b) α' (G)+β(G)=n(G)
c) α(G)=β(G)
d) β(G)≤α(G)
e) NDA
Número: 040
Enunciado: Dado o grafo G abaixo, o que podemos afirmar? Lembrando que parâmetros sem linha (α e β) se referem a conjuntos de vértices, enquanto que os com linha (α' e β') se referem a arestas. Além disso, parâmetros com a letra grega alfa (α e α') se referem a elementos que não se tocam, enquanto que beta (β e β') indica coberturas.
a) α' (G)+β' (G)≤n(G)b) α' (G)+β(G)=n(G)
c) α(G)=β(G)
d) β(G)≤α(G)
e) NDA
Assinar:
Postagens (Atom)