MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre as afirmações abaixo, assinale a alternativa correta:

I   -  Uma k-coloração própria de um grafo k-cromático é uma coloração ótima.
II  -  Um grafo é 2-colorível apenas se o grafo for bipartido.
III -  Para todo grafo G, χ(G) ≥ ω(G) e χ(G) ≥ α(G)/n(G)
IV - Para todo grafo G, χ(G) - 1 ≤ ∆(G)


a)  Apenas as alternativasI e II estão corretas
b)  Apenas a alternativa II está incorreta
c)  Apenas as alternativas I, II e III estão corretas
d)  Apenas a alternativa III está incorreta
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:

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

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

b) Se G é imperfeito, então G ○ h nunca será perfeito.

c) χ(G ○ h) = ω( G  ○ h ) para todo grafo perfeito G e qualquer h.
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

MO405 - Questão para a prova oral


Número:

Enunciado: Um grafo G é perfeito se χ(H) = ω(H) para todo subgrafo induzido H de G. Sabendo disso,  analise as afirmações abaixo e assinale a alternativa correta.

I   - Grafos cordais são perfeitos.

II - Grafos bipartidos são perfeitos; o que não é válido para seus respectivos grafos linha.

III  - Grafos de intervalos são perfeitos.

IV  - Todo grafo perfeito possui uma imersão planar.

a) Apenas a afirmação IV está incorreta.
b) As afirmações I, II e IV estão corretas.
c) As afirmações II e IV estão incorretas.
d) Apenas a afirmação I está correta.
e) N.D.A.


Ideia original de: Leandro Teófilo

Questão extra

MO405 - Questão para a prova oral


Número:

Enunciado: Sendo G um grafo cúbico que possui um nowhere-zero 4-fluxo, é incorreto afirmar que: 

a) G é 3-aresta-colorível
b) G não possui um Cycle Double Cover. 
c) G não é o grafo de Petersen.
d) G é formado pela união de dois grafos pares.
e) N.D.A.


Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral


Número:

Enunciado: Sendo G o grafo abaixo, analise as afirmações que se seguem e assinale a alternativa correta.

I - G é Hamiltoniano.
II - G é um snark.
III - G possui coloração de Tait.
IV - G não possui um corte não-trivial de 3 arestas.



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 corretas.
d) Apenas a afirmação II está correta.
e) N.D.A.


Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral (Extra)

Número:

Enunciado: Sabendo que G é um grafo simples que possui como fechamento (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) Todas as afirmações estão corretas.
e) N.D.A.


Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G o grafo abaixo, assinale a opção incorreta:

a)  χ'(G) =  4 _.

b) O número cromático do grafo linha de G, denotado χ(L(G)) é igual a ∆(G).
c) O grafo é Classe 1.
d) O grafo possui um Ciclo Hamiltoniano.
e) N.D.A


Ideia original de: Leandro Teófilo

Questão dia 18/05

MO405 - Questão para a prova oral


Número:

Enunciado: Assinale a opção correta:

a) Todo grafo planar possui uma subdivisão de K_5.

b) Se χ (G) ≤  4  então G é um grafo planar.
c) Se um grafo G possui uma subdivisão de K_3,3 então G é planar.
d) O complemento de um grafo planar 2-conexo também é planar.
e) N.D.A


Ideia original de: Leandro Teófilo

Questão extra 3 - 04/05

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G o grafo formado pelo join C7 ν K5 , é incorreto dizer que:

a)  δ(G) ≥  χ(G) -1

b)  G é crítico (color-critical)
c)  ω(G) = 7
d)  χ(G) = 8
e) N.D.A       


Ideia original de: Leandro Teófilo

Questão extra 2 - 04/05

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando o grafo G contido na figura abaixo, podemos afirmar que:

a) G é crítico (color-critical) e  χ(G) > ω(G)
b) G não é crítico (color-critical) e  ω(G) = 6
c)  G é crítico (color-critical) e δ(G) <  χ(G) -1
d)  χ(G) = 6   e   ω(G) = 7
e) N.D.A


Ideia original de: Leandro Teófilo

Questrão extra - 04/05

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre as afirmações abaixo, assinale a alternativa correta:

I   -   Um  grafo G  sem vértices isolados  é crítico (color-critical) se  e somente se   χ(G - e) < χ(G), para todo e Є E(G) .

II  -  Todo grafo κ-crítico é (κ-1)-aresta-conectado.
III -  Em um grafo κ-crítico G temos  χ(G - v) < χ(G) = κ ,  para todo v Є V[G] .


a)  As alternativas I, II e III estão incorretas
b)  Apenas a alternativa III está incorreta
c)  As alternativas I, II e III estão corretas
d)  Apenas a alternativa I está correta
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 04/05

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G um grafo κ-crítico, é incorreto dizer que:

a)  χ(G - v)  ≤  χ(G) = κ , para todo  v Є V[G] .

b)  G é (κ-1)-aresta-conectado.
c)  Sendo H um grafo κ-crítico, então H ν G ( join entre H e G ) também é κ-crítico.
d)  δ(G) ≥ κ - 1
e) N.D.A

Ideia original de: Leandro Teófilo

Questão extra 3 - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre o produto cartesiano de grafos, é incorreto afirmar que:

a)  A operação de produto cartesiano é simétrica, ou seja G□H é isomorfo a H□G
b)  χ(G□H) = max (χ(G),χ(H) )
c)  O conjunto de vértices de G□H é o produto cartesiano dos conjuntos de vértices de G e H

d)  K2□K₂ é um ciclo de tamanho 4.
e) N.D.A

Ideia original de: Leandro Teófilo

Questão extra 2 - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre coloração de vértices, assinale a alternativa incorreta:

a)  O grafo de Petersen não admite 3-coloração.
b)  Seja G um grafo com caminho máximo P, então χ(G) ≤ n(P).
c)  Para todo grafo G,  χ(G) < n(G) - δ(G)

d)  Para todo grafo G bicolorível, χ(G) > ω(G).
e) N.D.A

Ideia original de: Leandro Teófilo

Questão extra - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre as afirmações abaixo, assinale a alternativa correta:

I   -  Uma k-coloração própria de um grafo k-cromático é uma coloração ótima.
II  -  Um grafo é 2-colorível apenas se o grafo for bipartido.
III -  Para todo grafo G, χ(G) ≥ ω(G) e χ(G) ≥ α(G)/n(G)
IV - Para todo grafo G, χ(G) - 1 ≤ ∆(G)


a)  Apenas as alternativasI e II estão corretas
b)  Apenas a alternativa II está incorreta
c)  Apenas as alternativas I, II e III estão corretas
d)  Apenas a alternativa III está incorreta
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre coloração de vértices, assinale a alternativa incorreta:

a) Uma k-coloração é própria se vértices adjacentes têm diferentes cores.
b) Um grafo é k-colorível se sua k-coloração é própria.
c)  Um grafo é k-cromático se seu número cromático é igual a k
d)  O clique number de um grafo G é o clique de maior tamanho em G.
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 13/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G o grafo abaixo, selecione a opção que indica quais das componentes  selecionadas (1 a 5) não representam um bloco?

a) 1 e 5
b) 2 e 3 
c) 2 e 5
d) 4 e 5
e) N.D.A


Ideia original de: Leandro Teófilo

Questão dia 06/04

MO405 - Questão para a prova oral

Número:

Enunciado: Dentre as alternativas abaixo, assinale a incorreta:

a) O menor grafo com um matching maximal que não é um matching máximo é P4.
b) Um matching perfeito pode ser representado por uma matriz que só possui um 1 em cada coluna, bem como em cada linha.
c) O tamanho de um matching é calculado através do número de vértices do grafo.
d) Dado um grafo G e M um matching de G. Caso consigamos adicionar uma aresta a  a M de forma que M+a' continue sendo um matching de G, então concluímos que M não era um matching maximal.
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 23/03

MO405 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa incorreta em relação às árvores do tipo centopéia (lagarta). 

a) Possui um caminho(espinha) incidente a (ou contém) todas as arestas
b) Toda centopeia possui Rotulagem Graciosa
c) Todos os seus vértices de grau  d >=3 têm no mínimo 3 vizinhos que não são folhas
d) Todos os vértices não pertencentes à espinha são folhas
e) N.D.A



Ideia original de: Leandro Teófilo

Questão dia 16/03

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando as sequencias de graus abaixo,assinale aquela que não representa uma árvore. 

a) 1 3 2 1 3 2
b) 1 2 1 1 4 1
c)  2 1 2 1 1 3
d)  3 1 1 1 3 1
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 09/03

MO405 - Questão para a prova oral

Número:

Enunciado: Considerando os grafos G1 e G2 da figura abaixo, 

Sendo G1 U G2 o grafo formado pela união dos grafos G1 e G2, escolha a opção correta:

a)Os grafos G1, G2, e G1 U G2  são grafos Eulerianos.

b)O grafo G1 é um grafo euleriano, mas G2 não é um grafo Euleriano.

c)Os grafos G1 e G2 são grafos Eulerianos. O grafo G1 U G2  não é Euleriano 

d)O grafo G1 não pode ser decomposto em ciclos

e)N.D.A

Ideia original de: Leandro Teófilo