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