MO405 - Questão para a prova oral

Número: 039

Enunciado: Considere o Grafo G resultante da diferença simétrica de G1 e G2, e assinale a alternativa correta:

I. G possui um ciclo de tamanho 5;
II. G possui um caminho maximal de tamanho 3;
III.O tamanho da menor cobertura por vértices de G é 3.

a) Somente I está correta;
b) Somente II está correta;
c) I e II estão corretas;
d) I e III estão corretas; 
e) N.D.A
 
Ideia original de: Rafael L. Gomes

MO405 - Questão para a prova oral

Número: 038

Enunciado: Sobre o grafo apresentado na figura, podemos dizer que:












a) Possui um emparelhamento perfeito de tamanho 6;

b) Possui uma cobertura por vértices de tamanho 4;

c) Possui um emaprelhamento máximo de tamanho 4;

d) Possui um emparelhamento maximal de tamanho 3;

e) NDA


Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 037

Enunciado:
Quantos dos grafos a seguir não possuem um emparelhamento perfeito?

Grafo completo K5.
Árvore de vértices 1,...,8 com o seguinte código de Prüfer: 217821
Grafo simples desconexo com a seguinte sequência de graus: 332211
Grafo bipartido 5-regular.

a) 1
b) 2
c) 3
d) 4
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número: 036

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

a) Possuem um caminho (espinha) incidente a (ou contendo) cada aresta.

b) Toda centopéia possui Rotulagem Graciosa.

c) Nelas, todo vértice de grau d ≥ 3 tem 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

MO405 - Questão para a prova oral

Número:  035

Enunciado: Em relação ao Algoritmo de Kruskal, é correto afirmar que:

a) O algoritmo começa com uma árvore que aumenta sem se desconectar, culminando uma árvore geradora mínima.

b) O algoritmo encontra o menor caminho entre cada par de vértices do grafo.

c) O algoritmo percorre as arestas em ordem crescente de pesos, mas só inclui aquelas que ligam vértices de árvores distintas até o momento.

d) O algoritmo sempre inclui as N-1 menores arestas, onde N é o número de vértices.

e) N.D.A


Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

Número: 034

Enunciado:
Seja T uma árvore com número par de vértices, numerados de 1 a n = 2k, representada pelo código de Prufer C. Assinale a alternativa incorreta:

a) Se i é o número que mais vezes aparece em C, então o vértice i tem grau máximo em T.

b) Se i não aparece em C, então o vértice i tem grau mínimo em T.

c) Se todos os números de C são distintos, então T possui exatamente 2 folhas.

d) Se todos números de C são ímpares, então pelo menos metade dos nós de T são folhas.

e) NDA

MO405 - Questão para a prova oral

Número: 033

Enunciado: Observe o grafo a seguir e escolha qual das sequências representa os passos do algoritmo de Kruskal para uma árvore espalhada de peso mínimo. 

a) AB, DG, EF, BC, DH, BE, AC, CH

b) AB, DG, EF, BC, DH, BE, CH

c) AB, BE, EF, DG, DH, BE, CH

d) DG, AB, EF, DH, DG, BE, CH 

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 032

Enunciado: Dada a seguinte sequência de Prüfer (11111), podemos afirmar que:

a) O grafo possui 8 vértices.

b) O grafo é uma estrela.

c) O grafo é desconexo.

d) Pode-se gerar dois ou mais grafos a partir desta sequência.

e) NDA

Ideia original de:  Rafael Werneck

MO405 - Questão para a prova oral

Número: 031

Enunciado: Seja T a árvore com conjunto de vértices {0,...,8} obtida do Prufer Code 1144466. A lista de adjacências de T é:

a) (0,1); (1,2); (1,4); (3,4); (4,5); (7,8); (6,4); (6,8);

b) (8,6); (6,4); (7,8); (5,4); (3,5); (4,1); (1,0); (2,1);

c) (7,6); (4,6); (5,4); (6,8); (0,1); (1,2); (4,3); (1,4);

d) (4,1); (6,3); (2,1); (1,0); (4,6); (8,6); (7,6); (6,5);

e) NDA


 Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 030

Enunciado: Dado um conjunto de vértices de tamanho 10, o número de árvores com 8 arestas que pode ser formado com este conjunto é:

a) 10⁸

b) 10(9⁷)

c) 10(9¹⁰)

d) 10¹²

e) NDA

MO405 - Questão para a prova oral

Número: 029

Enunciado: Considere uma árvore T com 10 vértices e Prüfer code 24446669.  Assinale a alternativa correta:

I. T é uma caterpillar;
II. T possui como centro o vértice 6;
III. Aplicando-se uma BFS a partir do vértice 1 pode-se obter a seguinte sequência: 1, 2, 4, 6, 9, 10, 8, 7, 5 e 3.

a) Somente I está correta;
b) Somente II está correta;
c) I e II estão corretas;
d) I e III estão corretas; 
e) N.D.A
 
Ideia original de: Rafael L. Gomes

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 028

Enunciado:
Considere o grafo G da figura seguinte:

Designemos por τ(G) o número de árvores geradoras de G. Escolha a opção correta:

a) τ(G)=12
b) τ(G)=14
c) τ(G)=16
d) τ(G)=18
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 027

Enunciado: Seja S_n o grafo estrela com n + 1 vértices, para n ≥ 1. Este grafo possui um graceful labeling, isto é, seus vértices podem ser rotulados pelos inteiros de 0 a n de forma que não haja duas arestas uv e xy tais que |u - v|=|x - y|, se, e somente se, o seu vértice central for rotulado como:

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

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número: 026

Enunciado: Uma sequência de graus pode corresponder a vários grafos não isomorfos.  Considerando as sequências de graus abaixo, assinale aquela que não pode representar uma árvore. 

a) 3 2 2 1 1 1
b) 3 3 1 1 1 1
c) 3 3 2 2 1 1
d) 4 2 1 1 1 1
e) N.D.A
 
Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número: 025
Enunciado: Lembrando os conceitos de distância entre vértices (comprimento do menor caminho entre os dois vértices), excentricidade de um vértice (maior distância a partir do vértice), raio (menor excentricidade), diâmetro (maior distância) e centro (vértices com excentricidade mínima), considere o seguinte grafo:

Qual das afirmações é incorreta?

a) O centro do grafo é o vértice f

b) O diâmetro do grafo é 4

c) O raio do grafo é 2

d) O raio de um grafo é sempre metade do seu diâmetro

e) NDA

 Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 024

Enunciado:
Seja G um grafo conexo não orientado com uma aresta de corte. Suponha que G é o grafo subjacente do dígrafo D. Podemos afirmar que:

a) D possui pelo menos 2 componentes fracamente conexas.

b) D possui pelo menos 2 componentes fortemente conexas.

c) D possui pelo menos 3 componentes fortemente conexas.

d) Se G é o grafo subjacente de um outro dígrafo D', então D é isomorfo a D'.
 
e) NDA

 
Ideia original de: Priscila do Nascimento Biller

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 023

Enunciado: Dado o dígrafo a seguir, qual é a alternativa correta?

a) O dígrafo é fracamente conectado.

b) O dígrafo possui um kernel, isto é, um conjunto independente que recebe arestas de todos os vértices fora dele.

c) O dígrafo contém um circuito euleriano.

d) Este é um dígrafo funcional, isto é, sai exatamente uma aresta de cada vértice.

e) NDA

 

Ideia original de: Rafael Werneck

MO405 - Questão para a prova oral

Número: 022


Enunciado: Qual das sequências a seguir é a sequência gráfica de um grafo simples?

a) (5,5,5,4,2,2,1)

b) (6,4,3,3,3,2,2,1,1)

c) (6,4,4,3,3,2,2,2)

d) (6,6,5,4,3,2,2)

e) NDA

 Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

Número: 021

Enunciado: Dado o grafo a seguir, qual dos caminhos é maximal?

a) 1,2,3,4

b) 1,2,4,5

c) 2,3,4,5

d) 2,4,3

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 020

Uma estratégia para identificar grafos conexos é ir marcando os vértices, de acordo com certos critérios, de forma que, ao final, se todos os vértices estiverem marcados, o grafo é conexo; caso contrário, o grafo não é conexo.  Qual dos algoritmos abaixo efetua a marcação corretamente para identificar grafos conexos segundo esta estratégia?

a)
marcação(Grafo Simples){
____Para cada Vértice U
____Se existe pelo menos uma aresta U-V
________Marque U
}

b)
marcação(Grafo Simples){
____Para cada aresta ligando U a V
________Marque U
________Marque V
}

c)
marcação(Grafo Simples){
____Marque um vértice aleatório U
____Para cada aresta ligando U a V________Marque V
}

d)
marcação(Grafo Simples){
____Marque um vértice qualquer
____Enquanto existir aresta ligando um vértice marcado U a um vértice desmarcado V
________Marque V
}

e) NDA

Ideia Original de: Marlon Fernandes de Alcantara

MO405 - Questão para a prova oral

Número: 019

Enunciado: Considere 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 incorreta:

a) O grafo G1 é Euleriano.

b) O grafo G2 é Euleriano.

c) O grafos G1 U G2  é Euleriano.

d) A união de dois grafos Eulerianos sempre resulta num grafo Euleriano.

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: 018

Enunciado: Considerando as sequências de graus abaixo, qual pode representar a sequência de graus de um grafo bipartido?

a) 3,2,1,1,1

b) 4,3,3,3,3

c) 4,4,4,3,3

d) 4,4,4,4,4

e) NDA


Ideia original de : Junior Fabian

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 017

Enunciado: Seja G um grafo simples, conexo, bipartido, e com todos os vértices de grau 4. Das afirmações seguintes apenas uma é compatível com as hipóteses anteriores. Qual delas?

a) G pode ter 8 vértices e 16 arestas
b) G pode ter 8 vértices e 32 arestas
c) G pode ter 9 vértices e 18 arestas
d) G pode ter 9 vértices e 36 arestas
e) NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número: 016

Enunciado:
Seja G um grafo par com um conjunto não vazio de arestas. Podemos afirmar que:

a) Toda trilha maximal é fechada.

b) Somente a trilha máxima é fechada.

c) Toda trilha maximal é euleriana.

d) Somente a trilha máxima é euleriana.

e) NDA
Ideia original de: Priscila do Nascimento Biller

MO405 - Questão para a prova oral

Número: 015

Enunciado: Um certo grafo G possui um ciclo C, e a aresta e pertence a C. Com base nestas informações, que podemos afirmar que:

a) A aresta e não é cut-edge

b) O ciclo C é um subgrafo induzido

c) O grafo G é conexo

d) Todos os componentes de G são triviais

e) NDA

Ideia original de: Juliana M Destro

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 014

Enunciado: Analise as seguintes afirmações e assinale a alternativa que lista as corretas.

I - Ciclo é uma trilha fechada V1,...,Vn em que V1,...,Vn-1 são distintos.
II - Um componente não trivial é um vértice isolado.
III - O "Lema do aperto de mãos" é a fórmula da soma dos graus, onde.
IV - Todo grafo simples G possui um subgrafo bipartido com no mínimo e(G)/2 arestas.


a) somente I e III
b) somente I e IV
c) somente II e III
d) somente II e IV
e) NDA


Idéia original de: Lélis G. Yamaguti Lima

MO405 - Questão para a prova oral

Número: 013

Enunciado: O número de vértices de corte e o número de arestas de corte do grafo abaixo são, respectivamente:

a) 3 , 4

b) 4 , 5

c) 5 , 6

d) 6 , 7

e) NDA

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 012

Enunciado: Dado o grafo a seguir, qual é o seu número cromático?

a) 4

b) 3

c) 2

d) 1

e) NDA

Ideia original de: Rafael Werneck

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 011

 

Enunciado: Qual é o valor da soma dos graus de todos os vértices de um grafo G?  Nota: V(G) e E(G) indicam, respectivamente, os conjuntos de vértices e de arestas de G.

a) |E(G)| + |V(G)|

b) |E(G)| * |V(G)|

c) 2|E(G)|

d) 2|V(G)|

e) NDA

Ideia original de : Junior Fabian

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 010


Enunciado: Seja M a matriz de incidência de um grafo completo de n vértices. Se M' é a matriz transposta de M e N=M*M', então, o valor de N(i,i), com i=1,...,n, é? (Onde N(i,i) é o i-ésimo termo da diagonal principal).

1. 0
2. n-1
3. n
4. n(n-1)/2
5. NDA

Ideia original de: Jorge Alencar

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral

Número: 009

Enunciado:
Considere o grafo G da figura a seguir:



Designemos por χ(G) o número cromático de G. Escolha a opção correta:

a) G é um grafo bipartido e χ(G)=2
b) G não é um grafo bipartido e χ(G)=3
c) A cintura de G é 3 e χ(G)=4
d) G é um grafo simples, conexo e χ(G)=4
e) NDA

Ideia original de: Zhenlei Ji

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