modulo 4

Prévia do material em texto

15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 1/7
Teoria dos Grafos
Módulo 4
Lista de adjacências de um grafo.
Caminhos de Euler.
Circuito de Hamilton (circuito hamiltoniano).
 
 
Clique no ícone para baixar o módulo 4 completo em pdf.
 
Para facilitar a navegação é recomendável que você clique com o botão direito do mouse e
selecione “abrir link em nova guia” ou “abrir link em nova janela”. Desta forma o arquivo abrirá
separadamente.
 
 
Exercício 1:
Sobre a lista de adjacência indicada acima são feita as seguintes afirmativas
I. O grafo representado por esta lista possui um laço.
II. O grafo representado por esta lista possui 6 arestas.
III. O grafo representado por esta lista é planar.
O correto afirmar que:
A)
Apenas a afirmativa I é verdadeira.
B)
Apenas a afirmativa II é verdadeira.
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 2/7
C)
Apenas a afirmativa III é verdadeira.
D)
Existem apenas duas afirmativas verdadeiras.
E)
As três afirmativas são verdadeiras.
O aluno respondeu e acertou. Alternativa(E)
Comentários:
A) asdasd
B) asdasd
C) asdasd
D) asdasd
E) asdasd
Exercício 2:
Com relação ao grafo G acima, podemos afirmar que:
A)
G não é conexo.
B)
G possui caminho de Euler.
C)
G é uma árvore com raiz.
D)
G é planar.
E)
G é acíclico.
O aluno respondeu e acertou. Alternativa(B)
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 3/7
Comentários:
A) sdasdasdad
C) sdasdasdad
B) sdasdasdad
Exercício 3:
Considere os grafos K4 , K5 e K2,3. Quais deles possuem caminho de Euler?
A)
K4 e K5
B)
K4 e K2,3
C)
K5 e K2,3
D)
nenhum deles
E)
todos eles
O aluno respondeu e acertou. Alternativa(C)
Comentários:
A) asdadad
B) asdadad
C) asdadad
Exercício 4:
Considere os grafos K4, K6 e K3,3. Quais deles possuem caminho de Euler?
A)
Apenas K6.
B)
K4 e K6.
C)
Apenas K3,3.
D)
Nenhum deles.
E)
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 4/7
Todos eles.
O aluno respondeu e acertou. Alternativa(D)
Comentários:
A) ddasdasd
B) ddasdasd
C) ddasdasd
D) ddasdasd
Exercício 5:
Em um grafo G, um caminho de Euler é um caminho:
A)
que passa por todos os vértices.
B)
que passa por todas as arestas sem repetir nenhuma.
C)
que percorre um ciclo.
D)
que passa por todos os vértices sem repetir nenhum.
E)
que liga dois vértices com mesma paridade.
O aluno respondeu e acertou. Alternativa(B)
Comentários:
A) asdasdasd
B) asdasdasd
Exercício 6:
A seguinte figura representa uma ilha em um rio com várias pontes interligando-as com as
margens e entre si. A respeito dessa configuração podemos afirmar que:
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 5/7
A)
É possível percorrer todas as pontes sem passar duas vezes pela mesma ponte, pois seu
grafo correspondente possui um número par de vértices.
B)
É possível percorrer todas as pontes sem passar duas vezes pela mesma ponte, pois em seu
grafo correspondente, a soma dos graus dos seus vértices é um número par.
C)
Não é possível percorrer todas as pontes sem passar duas vezes pela mesma ponte, pois
seu grafo correspondente possui um número ímpar de arestas.
D)
Não é possível percorrer todas as pontes sem passar duas vezes pela mesma ponte, pois
seu grafo correspondente possui um número par de vértices.
E)
Não é possível percorrer todas as pontes sem passar duas vezes pela mesma ponte, pois
seu grafo correspondente possui mais de 2 vértices com grau ímpar.
O aluno respondeu e acertou. Alternativa(E)
Comentários:
A) asdasdasd
B) asdasdasd
C) asdasdasd
D) asdasdasd
E) asdasdasd
Exercício 7:
Na figura abaixo estão representadas cinco ilhas e várias pontes interligando-as entre si.
Podemos afirmar que:
A)
É possível percorrer todas as pontes passando uma única vez em cada uma delas, e isso
pode ser feito iniciando o caminho a partir de qualquer ilha.
B)
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 6/7
É possível percorrer todas as pontes passando uma única vez em cada uma delas, e isso
deve ser feito iniciando o caminho pelas ilhas 1, 4 ou 5.
C)
É possível percorrer todas as pontes passando uma única vez em cada uma delas, e isso
deve ser feito iniciando o caminho pela ilha 4.
D)
É possível percorrer todas as pontes passando uma única vez em cada uma delas, e isso
deve ser feito iniciando o caminho pela ilha 2 ou 3.
E)
Não é possível percorrer todas as pontes passando uma única vez em cada uma delas.
O aluno respondeu e acertou. Alternativa(D)
Comentários:
A) asdadasdasd
B) asdadasdasd
C) asdadasdasd
C) asdadasdasd
D) asdadasdasd
Exercício 8:
Sobre a lista de adjacência indicada acima são feita as seguintes afirmativas
I. O grafo representado é um grafo de Euler.
II. O grafo representado possui um circuito Hamilton.
III. O grafo representado é grafo completo de 4 vértices (K4).
O correto afirmar que:
A)
Apenas a afirmativa I é verdadeira.
B)
Apenas a afirmativa II é verdadeira.
C)
Apenas a afirmativa III é verdadeira.
D)
Existem apenas duas afirmativas verdadeiras.
15/09/2019 UNIP - Universidade Paulista : DisciplinaOnline - Sistemas de conteúdo online para Alunos.
https://online.unip.br/imprimir/imprimirconteudo 7/7
E)
As três afirmativas são verdadeiras.
O aluno respondeu e acertou. Alternativa(D)
Comentários:
A) adadasdad
B) adadasdad
C) adadasdad
D) adadasdad