MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 008

Enunciado: Quantas arestas possui o grafo completo que tem como quantidade de vértices o número cromático do grafo abaixo?

a) 1

b) 5

c) 6

d) 10

e) NDA

Ideia original de: Marlon Fernandes de Alcantara

MO405 - Questão para a prova oral

Número: 007

Enunciado: Considere as seguintes afirmações sobre os conceitos fundamentais de grafos.  Quais delas estão corretas?:

I - Um grafo simples não possui ciclos nem arestas múltiplas.
II - A matriz de incidência de um grafo simples é sempre binária (possui somente 0's e 1's).
III - Um grafo é k-partido se e somente se o número cromático é no mínimo k.
IV - O grafo de Petersen possui entre outras propriedades: cintura (girth) de tamanho 5, 10 vértices de grau 3, 15 arestas.

1. somente I. II e III
2. somente I, II e IV
3. somente II e III
4. somente II e IV
5. NDA

Idéia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 006

Enunciado: O número de arestas e a soma dos graus de todos os vértices de um grafo K8 são, respectivamente:

a) 21, 56

b) 26, 54

c) 28, 56

d) 29, 54

e) NDA

Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

Número: 005

Enunciado:
Seja G um grafo bipartido que aceita uma decomposição em ciclos com pelo menos um ciclo. Podemos afirmar que:

a) O número cromático de G é igual a 2.

b) G não é planar.

c) G é conexo.

d) A cintura de G é ímpar.

e) NDA

Ideia original de: Priscila do Nascimento Biller

MO405 - Questão para a prova oral

Número: 004

Enunciado: Quantos grafos diferentes com vértices A, B, C, D, E existem?

a) 512

b) 605

c) 1000

d) 1024

e) NDA

Ideia original de: Thierry Pinheiro Moreira

MO405 - Questão para a prova oral

Número: 003

 
Enunciado: Dado o grafo abaixo, o que se pode dizer sobre a matriz de adjacência M do grafo complementar?

a) M[A,E] = 1, M[D,C] = 0

b) M[B,D] = 0, M[E,A] = 0

c) M[D,A] = 1, M[C,E] = 1

d) M[E,B] = 1, M[B,D] = 0

e) NDA

Ideia original de: Jefferson Capovilla

MO405 - Questão para a prova oral

Número: 002


Enunciado: Qual das alternativas a seguir está incorreta? Considere apenas grafos simples.

a) A cintura de um grafo triangulo é igual a cintura de um grafo casa.

b) O complemento de um grafo completo é um grafo sem arestas.

c) O grau de cada vertice em um grafo completo é igual ao número de vertices menos 1.

d) Todo grafo completo possui um clique.

e) NDA