Teoria dos Grafos_Questionario 1

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções sobre o grafo representado graficamente abaixo. 
 
Fonte: autoria própria. 
 
I. Trata-se do grafo K32. 
II. O grafo é planar. 
III. Existe um caminho que passa por todas as arestas uma única vez. 
São corretas as afirmações: 
 
Resposta Selecionada: d. 
I, II e III. 
Respostas: a. 
Apenas I e II. 
 
b. 
Apenas I e III. 
 
c. 
Apenas II e III. 
 
d. 
I, II e III. 
 
e. 
Apenas II. 
Comentário da 
resposta: 
Resposta: D. 
Comentário: o grafo K32 é planar, pois é isomorfo ao seguinte grafo. Uma 
vez que apresenta dois nos ímpares, segundo o Teorema de Euler, 
apresenta um caminho que passa por todas as arestas uma única vez. 
 
Fonte: autoria própria. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta: 
Resposta 
Selecionada: 
c. 
A busca em largura é geralmente implementada utilizando 
uma estrutura de dados fila, que armazena os vértices que 
ainda não foram visitados em ordem de descoberta. Quando 
um vértice é descoberto, ele é adicionado à fila e quando é 
visitado, é removido da fila. 
Respostas: a. 
 
O grafo K5 é planar. 
 
b. 
Para investigar se um grafo apresenta caminho Hamiltoniano, 
emprega-se um algoritmo de desempenho O(n2). 
 
c. 
A busca em largura é geralmente implementada utilizando 
uma estrutura de dados fila, que armazena os vértices que 
ainda não foram visitados em ordem de descoberta. Quando 
um vértice é descoberto, ele é adicionado à fila e quando é 
visitado, é removido da fila. 
 
d. 
Um grafo é Euleriano se apresentar número par de nós 
ímpares. 
 
e. 
Todo grafo planar é Hamiltoniano. 
Comentário da 
resposta: 
Resposta: C. 
Comentário: trata-se de característica da busca em 
largura. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
O grafo K33 é representado graficamente como se segue: 
 
Fonte: autoria própria. 
 
Assinale a alternativa que apresenta uma afirmação incorreta. 
 
Resposta 
Selecionada: 
a. 
Trata-se de um grafo planar. 
Respostas: a. 
Trata-se de um grafo planar. 
 
b. 
Trata-se de um grafo conexo. 
 
c. 
Todos os nós apresentam grau 3. 
 
 
d. 
Não existe um caminho que passa por todas as arestas uma única vez. 
 
e. 
Apresenta o caminho: 1-4-2-5-3-6-1. Dessa forma, apresenta um 
caminho Hamiltoniano. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: o grafo K33 não é planar, pois não é possível representá-lo 
graficamente em um plano de tal forma queque as arestas se 
interceptem apenas nos vértices. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Assinale a alternativa que apresenta o número de regiões que o seguinte grafo divide o 
plano. 
 
Fonte: autoria própria. 
 
Resposta Selecionada: c. 
7 
Respostas: a. 
8 
 
b. 
13 
 
c. 
7 
 
d. 
9 
 
e. 
6 
Comentário da 
resposta: 
Resposta: C. 
Comentário: trata-se de um grafo planar com 8 nohs e 13 arestas. Por 
se tratar de um grafo planar, vale a relação: n-a+r=2. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta. 
Resposta 
Selecionada: 
b. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
representação planar divide o plano em r regiões, então: n-a+r=2. 
Respostas: a. 
 
Para um grafo planar conexo e simples com n nós e a arestas e se n < 3 e 
se não existem ciclos de comprimento 3, então; a > 2n – 4. 
 
b. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
representação planar divide o plano em r regiões, então: n-a+r=2. 
 
c. 
Para um grafo planar simples e conexo, se o número de nós é n, tal que 
n ≥ 3 então a > 3n – 6. 
 
d. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
representação planar divide o plano em r regiões, então: a-n+r=2. 
 
e. 
Não existe nenhuma relação entre o número de nós, arestas e regiões 
que um grafo planar, simples e conexo divide o plano. 
Comentário da 
resposta: 
Resposta: B. 
Comentário: trata-se de um teorema e, portanto, passível de ser 
provado como verdadeiro. 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Considere o grafo apresentado na figura que se segue: 
 
Fonte: autoria própria. 
 
Se se acrescentar ao grafo, uma aresta A6, tal que g(A6)=(2,4), pode se afirmar que a matriz 
adjacência para o dígrafo é: 
 
Resposta Selecionada: c. 
M = 
Respostas: a. 
M = 
 
b. 
M = 
 
c. 
M = 
 
 
d. 
M = 
 
e. 
M = 
Comentário da 
resposta: 
Resposta: C. 
Comentário: para o dígrafo resultante da adição da aresta A6, vale a 
função g, tal que: g(A1)=(1,2), g(A2)=(2,3), g(A3)=(3,4) (A5)=(4,3), 
g(A4)=(3,1) e g(A6)=(2,4). 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Para a árvore representada na figura seguinte, assinale a alternativa 
correta. 
 
Fonte: autoria própria. 
 
Resposta 
Selecionada: 
a. 
A altura da árvore é 2. 
Respostas: a. 
A altura da árvore é 2. 
 
b. 
O percurso pós-ordem: +–73*y2 resulta na notação 
polonesa. 
 
c. 
Percurso pré-ordem: 7–3+y*2 resulta na notação infixa. 
 
d. 
Percurso ordem simétrica: 73–y2*+ resulta na notação 
polonesa reversa. 
 
e. 
No percurso em pós-ordem, a raiz é a primeira a ser visitada 
a partir de todas as subárvores da esquerda para a direita. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: a profundidade de um nó em uma árvore é o 
 
comprimento do caminho da raiz ao nó; a raiz tem 
profundidade 0.A profundidade (altura) de uma árvore é a 
maior profundidade dos nós na árvore. 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Considere o grafo representado na figura seguinte. Assinale a alternativa que representa o 
percurso em nível no mesmo. 
 
Fonte: autoria própria. 
 
Resposta Selecionada: a. 
a, b, h, d, g, c, e, f 
Respostas: a. 
a, b, h, d, g, c, e, f 
 
b. 
a, h, b, d, g, c, f, e 
 
c. 
b, a, c, h, e, d, e, f, f 
 
d. 
a, b, c, d, e, f, g, h 
 
e. 
h, g, f, e, c, d, b, a 
Comentário da 
resposta: 
Resposta: A. 
Comentário: a busca em nível começa em um nó arbitrário, anota todos 
os seus nós adjacentes e seguidamente os nós adjacentes àqueles 
anteriormente encontrados, e assim por diante. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções e seguidamente assinale a alternativa 
correta. 
 
I. O problema do Circuito Hamiltoniano corresponde a verificar se existe um 
circuito que percorre por todos os nós de um grafo uma única vez. 
II. Encontrar um caminho Hamiltoniano em um grafo é um problema NP-
completo, o que significa que não há um algoritmo conhecido que possa 
resolver o problema de forma eficiente para todos os casos. 
III. O algoritmo conhecido para resolver o problema do circuito 
Hamiltoniano é O(n!). 
São corretas as afirmações: 
 
Resposta Selecionada: e. 
I, II e III. 
Respostas: a. 
Apenas I. 
 
b. 
Apenas I e II. 
 
c. 
Apenas I e III. 
 
d. 
Apenas II e III. 
 
e. 
I, II e III. 
Comentário 
da resposta: 
Resposta E. 
Comentário: o algoritmo conhecido para resolver o problema 
do circuito Hamiltoniano consiste em verificar se cada uma 
das permutações dos nós do grafo, constituem o caminho 
hamiltoniano. Assim na situação de pior caso é O(n!) e, 
portanto, não é eficiente. De fato, para um grafo de 10 nós, 
seriam necessárias na situação de pior caso mais de 3.000.000 
de cálculos. Logo, não é eficiente. O desempenho é, pois, NP-
Completo, ou seja, a solução eficiente, polinomial, não é 
conhecida. 
 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta. 
Resposta 
Selecionada: 
a. 
Uma ordenação topológica é uma ordenação linear dos 
vértices do grafo que respeita a direção das arestas. Em 
outras palavras, se existe uma aresta direcionada do vértice u 
para o vértice v, então u aparece antes de v na ordenação. 
Respostas: a. 
Uma ordenação topológica é uma ordenação linear dos 
vértices do grafo que respeita a direção das arestas. Em 
outras palavras, se existeuma aresta direcionada do vértice u 
para o vértice v, então u aparece antes de v na ordenação. 
 
b. 
O grafo K32 não é simples. 
 
c. 
Não existe solução para o problema do fluxo máximo. 
 
d. 
O problema do caminho Euleriano é, assim como o problema 
do circuito Hamiltoniano de desempenho polinomial. 
 
e. 
Dois grafos isomorfos podem apresentar números de nós 
distintos. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: trata-se da característica da ordenação 
topológica. 
 
 
• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções sobre o grafo representado graficamente abaixo. 
 
Fonte: autoria própria. 
 
I. Trata-se do grafo K32. 
II. O grafo é planar. 
III. Existe um caminho que passa por todas as arestas uma única vez. 
São corretas as afirmações: 
 
Resposta Selecionada: d. 
I, II e III. 
Respostas: a. 
Apenas I e II. 
 
b. 
Apenas I e III. 
 
c. 
Apenas II e III. 
 
d. 
I, II e III. 
 
e. 
Apenas II. 
Comentário da 
resposta: 
Resposta: D. 
Comentário: o grafo K32 é planar, pois é isomorfo ao seguinte grafo. Uma 
vez que apresenta dois nos ímpares, segundo o Teorema de Euler, 
apresenta um caminho que passa por todas as arestas uma única vez. 
 
Fonte: autoria própria. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta: 
Resposta 
Selecionada: 
c. 
A busca em largura é geralmente implementada utilizando 
uma estrutura de dados fila, que armazena os vértices que 
ainda não foram visitados em ordem de descoberta. Quando 
um vértice é descoberto, ele é adicionado à fila e quando é 
visitado, é removido da fila. 
Respostas: a. 
O grafo K5 é planar. 
 
b. 
Para investigar se um grafo apresenta caminho Hamiltoniano, 
emprega-se um algoritmo de desempenho O(n2). 
 
c. 
A busca em largura é geralmente implementada utilizando 
uma estrutura de dados fila, que armazena os vértices que 
 
ainda não foram visitados em ordem de descoberta. Quando 
um vértice é descoberto, ele é adicionado à fila e quando é 
visitado, é removido da fila. 
 
d. 
Um grafo é Euleriano se apresentar número par de nós 
ímpares. 
 
e. 
Todo grafo planar é Hamiltoniano. 
Comentário da 
resposta: 
Resposta: C. 
Comentário: trata-se de característica da busca em 
largura. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
O grafo K33 é representado graficamente como se segue: 
 
Fonte: autoria própria. 
 
Assinale a alternativa que apresenta uma afirmação incorreta. 
 
Resposta 
Selecionada: 
a. 
Trata-se de um grafo planar. 
Respostas: a. 
Trata-se de um grafo planar. 
 
b. 
Trata-se de um grafo conexo. 
 
c. 
Todos os nós apresentam grau 3. 
 
d. 
Não existe um caminho que passa por todas as arestas uma única vez. 
 
e. 
Apresenta o caminho: 1-4-2-5-3-6-1. Dessa forma, apresenta um 
caminho Hamiltoniano. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: o grafo K33 não é planar, pois não é possível representá-lo 
graficamente em um plano de tal forma queque as arestas se 
interceptem apenas nos vértices. 
 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Assinale a alternativa que apresenta o número de regiões que o seguinte grafo divide o 
plano. 
 
Fonte: autoria própria. 
 
Resposta Selecionada: c. 
7 
Respostas: a. 
8 
 
b. 
13 
 
c. 
7 
 
d. 
9 
 
e. 
6 
Comentário da 
resposta: 
Resposta: C. 
Comentário: trata-se de um grafo planar com 8 nohs e 13 arestas. Por 
se tratar de um grafo planar, vale a relação: n-a+r=2. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta. 
Resposta 
Selecionada: 
b. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
representação planar divide o plano em r regiões, então: n-a+r=2. 
Respostas: a. 
Para um grafo planar conexo e simples com n nós e a arestas e se n < 3 e 
se não existem ciclos de comprimento 3, então; a > 2n – 4. 
 
b. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
representação planar divide o plano em r regiões, então: n-a+r=2. 
 
c. 
Para um grafo planar simples e conexo, se o número de nós é n, tal que 
n ≥ 3 então a > 3n – 6. 
 
d. 
Para um grafo planar simples e conexo, com n nós e a arestas, se a 
 
representação planar divide o plano em r regiões, então: a-n+r=2. 
 
e. 
Não existe nenhuma relação entre o número de nós, arestas e regiões 
que um grafo planar, simples e conexo divide o plano. 
Comentário da 
resposta: 
Resposta: B. 
Comentário: trata-se de um teorema e, portanto, passível de ser 
provado como verdadeiro. 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Considere o grafo apresentado na figura que se segue: 
 
Fonte: autoria própria. 
 
Se se acrescentar ao grafo, uma aresta A6, tal que g(A6)=(2,4), pode se afirmar que a matriz 
adjacência para o dígrafo é: 
 
Resposta Selecionada: c. 
M = 
Respostas: a. 
M = 
 
b. 
M = 
 
c. 
M = 
 
d. 
M = 
 
e. 
M = 
Comentário da 
resposta: 
Resposta: C. 
Comentário: para o dígrafo resultante da adição da aresta A6, vale a 
função g, tal que: g(A1)=(1,2), g(A2)=(2,3), g(A3)=(3,4) (A5)=(4,3), 
 
g(A4)=(3,1) e g(A6)=(2,4). 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Para a árvore representada na figura seguinte, assinale a alternativa 
correta. 
 
Fonte: autoria própria. 
 
Resposta 
Selecionada: 
a. 
A altura da árvore é 2. 
Respostas: a. 
A altura da árvore é 2. 
 
b. 
O percurso pós-ordem: +–73*y2 resulta na notação 
polonesa. 
 
c. 
Percurso pré-ordem: 7–3+y*2 resulta na notação infixa. 
 
d. 
Percurso ordem simétrica: 73–y2*+ resulta na notação 
polonesa reversa. 
 
e. 
No percurso em pós-ordem, a raiz é a primeira a ser visitada 
a partir de todas as subárvores da esquerda para a direita. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: a profundidade de um nó em uma árvore é o 
comprimento do caminho da raiz ao nó; a raiz tem 
profundidade 0.A profundidade (altura) de uma árvore é a 
maior profundidade dos nós na árvore. 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Considere o grafo representado na figura seguinte. Assinale a alternativa que representa o 
percurso em nível no mesmo. 
 
 
Fonte: autoria própria. 
Resposta Selecionada: a. 
a, b, h, d, g, c, e, f 
Respostas: a. 
a, b, h, d, g, c, e, f 
 
b. 
a, h, b, d, g, c, f, e 
 
c. 
b, a, c, h, e, d, e, f, f 
 
d. 
a, b, c, d, e, f, g, h 
 
e. 
h, g, f, e, c, d, b, a 
Comentário da 
resposta: 
Resposta: A. 
Comentário: a busca em nível começa em um nó arbitrário, anota todos 
os seus nós adjacentes e seguidamente os nós adjacentes àqueles 
anteriormente encontrados, e assim por diante. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções e seguidamente assinale a alternativa 
correta. 
 
I. O problema do Circuito Hamiltoniano corresponde a verificar se existe um 
circuito que percorre por todos os nós de um grafo uma única vez. 
II. Encontrar um caminho Hamiltoniano em um grafo é um problema NP-
completo, o que significa que não há um algoritmo conhecido que possa 
 
resolver o problema de forma eficiente para todos os casos. 
III. O algoritmo conhecido para resolver o problema do circuito 
Hamiltoniano é O(n!). 
São corretas as afirmações: 
Resposta Selecionada: e. 
I, II e III. 
Respostas: a. 
Apenas I. 
 
b. 
Apenas I e II. 
 
c. 
Apenas I e III. 
 
d. 
Apenas II e III. 
 
e. 
I, II e III. 
Comentário 
da resposta: 
Resposta E. 
Comentário: o algoritmo conhecido para resolver o problema 
do circuito Hamiltoniano consiste em verificar se cada uma 
das permutações dos nós do grafo, constituem o caminho 
hamiltoniano. Assim na situação de pior caso é O(n!) e, 
portanto, não é eficiente. De fato, para um grafo de 10 nós, 
seriam necessárias na situação de pior caso mais de 3.000.000 
de cálculos. Logo, não é eficiente. O desempenho é, pois, NP-
Completo, ou seja, a solução eficiente, polinomial, não é 
conhecida.• Pergunta 10 
0,5 em 0,5 pontos 
 
Assinale a alternativa correta. 
Resposta 
Selecionada: 
a. 
Uma ordenação topológica é uma ordenação linear dos 
vértices do grafo que respeita a direção das arestas. Em 
outras palavras, se existe uma aresta direcionada do vértice u 
 
para o vértice v, então u aparece antes de v na ordenação. 
Respostas: a. 
Uma ordenação topológica é uma ordenação linear dos 
vértices do grafo que respeita a direção das arestas. Em 
outras palavras, se existe uma aresta direcionada do vértice u 
para o vértice v, então u aparece antes de v na ordenação. 
 
b. 
O grafo K32 não é simples. 
 
c. 
Não existe solução para o problema do fluxo máximo. 
 
d. 
O problema do caminho Euleriano é, assim como o problema 
do circuito Hamiltoniano de desempenho polinomial. 
 
e. 
Dois grafos isomorfos podem apresentar números de nós 
distintos. 
Comentário da 
resposta: 
Resposta: A. 
Comentário: trata-se da característica da ordenação 
topológica. 
 
•