Grafo não ponderado

Prévia do material em texto

Grafo não ponderado 
O que caracteriza um grafo nao ponderado?
a) As arestas possuem valores numericos que indicam a intensidade da conexao.
b) As arestas nao possuem direcao e nem peso associado.
c) As arestas possuem direcao, mas nao possuem peso.
d) As arestas sao direcionadas, mas todas possuem o mesmo peso.
Resposta correta: b) As arestas nao possuem direcao e nem peso associado.
Explicacao: Um grafo nao ponderado e aquele em que as arestas nao possuem pesos (ou custos
associados) nem direcao. Ou seja, as arestas sao simplesmente ligacoes entre os vertices.
Qual a diferenca principal entre um grafo nao ponderado e um grafo ponderado?
a) O grafo nao ponderado possui vertices com pesos, enquanto o ponderado possui arestas sem
peso.
b) O grafo ponderado nao possui arestas entre os vertices, ao contrario do grafo nao ponderado.
c) O grafo nao ponderado nao possui valores associados as arestas, enquanto o grafo ponderado
atribui pesos a elas.
d) O grafo nao ponderado possui arestas direcionadas, enquanto o grafo ponderado possui arestas
nao direcionadas.
Resposta correta: c) O grafo nao ponderado nao possui valores associados as arestas, enquanto o
grafo ponderado atribui pesos a elas.
Explicacao: A principal diferenca e que, no grafo ponderado, as arestas possuem um valor
associado, que pode representar distancia, custo ou outro parametro. Ja no grafo nao ponderado,
as arestas sao simplesmente conexoes entre vertices, sem qualquer peso.
Qual e a caracteristica de um grafo nao dirigido?
a) As arestas possuem direcao definida, ou seja, conectam um vertice ao outro de forma
unidirecional.
b) As arestas nao possuem direcao; ou seja, a conexao entre os vertices e bidirecional.
c) As arestas sao ponderadas, com valores numericos definidos.
d) Nao ha conexoes diretas entre os vertices.
Resposta correta: b) As arestas nao possuem direcao; ou seja, a conexao entre os vertices e
bidirecional.
Explicacao: Em um grafo nao dirigido, as arestas nao possuem direcao especifica, o que implica
que a conexao entre os vertices e bidirecional. Ou seja, se existe uma aresta entre A e B, tambem
e possivel ir de B para A.
O que e um caminho em um grafo nao ponderado?
a) Uma sequencia de vertices e arestas, em que a direcao das arestas e relevante.
b) Uma sequencia de vertices conectados por arestas, podendo haver repeticao de vertices ou
arestas.
c) Uma sequencia de vertices e arestas, onde a direcao nao importa, e nao ha repeticao de
vertices.
d) Um ciclo fechado em que os vertices sao repetidos.
Resposta correta: c) Uma sequencia de vertices e arestas, onde a direcao nao importa, e nao ha
repeticao de vertices.
Explicacao: Em um grafo nao ponderado, um caminho e uma sequencia de vertices conectados por
arestas, sem repeticao de vertices ou arestas, e onde a direcao das arestas nao e relevante.
O que significa um grafo ser conexo?
a) Um grafo e conexo quando ha um caminho entre pelo menos dois vertices.
b) Um grafo e conexo quando nao ha caminhos entre nenhum par de vertices.
c) Um grafo e conexo quando todos os vertices tem o mesmo numero de arestas incidentes.
d) Um grafo e conexo quando ha um caminho entre todos os vertices sem repeticao de arestas.
Resposta correta: d) Um grafo e conexo quando ha um caminho entre todos os vertices sem
repeticao de arestas.
Explicacao: Um grafo e considerado conexo quando e possivel encontrar um caminho entre
qualquer par de vertices, ou seja, todos os vertices estao conectados, direta ou indiretamente.
O que caracteriza um grafo simples?
a) O grafo possui multiplas arestas entre dois vertices.
b) O grafo nao possui arestas, apenas vertices.
c) O grafo possui apenas uma aresta entre dois vertices e nao permite lacos.
d) O grafo possui ciclos em todas as suas arestas.
Resposta correta: c) O grafo possui apenas uma aresta entre dois vertices e nao permite lacos.
Explicacao: Um grafo simples e aquele em que entre dois vertices existe no maximo uma aresta, e
nao sao permitidos lacos (arestas que conectam um vertice a ele mesmo).
O que e um grafo completo?
a) Um grafo em que todos os vertices estao conectados entre si por exatamente uma aresta.
b) Um grafo em que todos os vertices estao conectados por um numero infinito de arestas.
c) Um grafo que possui apenas um vertice.
d) Um grafo em que apenas dois vertices estao conectados.
Resposta correta: a) Um grafo em que todos os vertices estao conectados entre si por exatamente
uma aresta.
Explicacao: Um grafo completo e aquele em que todos os vertices estao diretamente conectados
entre si. Se um grafo tem n vertices, ele tera
2
n(n1)
arestas, pois cada par de vertices esta conectado por uma unica aresta.
O que e um ciclo em um grafo nao dirigido?
a) Uma sequencia de vertices conectados por arestas, onde o primeiro vertice e igual ao ultimo
vertice, e todos os outros vertices sao distintos.
b) Uma sequencia de arestas que conecta todos os vertices do grafo, sem repetir arestas.
c) Um caminho que retorna ao vertice inicial, mas sem repetir nenhum vertice.
d) Um caminho fechado em que todos os vertices sao repetidos.
Resposta correta: a) Uma sequencia de vertices conectados por arestas, onde o primeiro vertice e
igual ao ultimo vertice, e todos os outros vertices sao distintos.
Explicacao: Um ciclo em um grafo nao dirigido e um caminho fechado onde o primeiro vertice e
igual ao ultimo, mas sem repetir outros vertices ou arestas. Ou seja, e uma sequencia de vertices
distintos, exceto pelo vertice inicial e final, que sao o mesmo.
O que e o grau de um vertice em um grafo nao dirigido?
a) O numero de ciclos que incluem o vertice.
b) O numero de arestas que conectam o vertice a outros vertices.
c) O numero de arestas incidentes ao vertice, considerando que todas as arestas sao direcionadas.
d) O numero de vertices conectados a ele diretamente.
Resposta correta: b) O numero de arestas que conectam o vertice a outros vertices.
Explicacao: O grau de um vertice em um grafo nao dirigido e o numero de arestas que estao
conectadas a ele. Cada aresta que incide em um vertice aumenta seu grau em uma unidade.
O que e um grafo bipartido?
a) Um grafo em que os vertices podem ser divididos em duas partes, de modo que todas as arestas
conectam vertices de partes diferentes.
b) Um grafo que possui dois vertices conectados por multiplas arestas.
c) Um grafo no qual todos os vertices estao conectados entre si.
d) Um grafo em que todos os vertices tem o mesmo grau.
Resposta correta: a) Um grafo em que os vertices podem ser divididos em duas partes, de modo
que todas as arestas conectam vertices de partes diferentes.
Explicacao: Um grafo bipartido e um grafo cujos vertices podem ser divididos em dois conjuntos
disjuntos, de tal forma que todas as arestas conectam vertices de conjuntos diferentes. Nao ha
arestas entre vertices do mesmo conjunto.
Em um grafo nao dirigido, o que e um laco?
a) Um vertice que nao esta conectado a nenhum outro vertice.
b) Uma aresta que conecta dois vertices distintos.
c) Uma aresta que conecta um vertice a si mesmo.
d) Uma aresta que conecta um vertice a dois outros vertices.
Resposta correta: c) Uma aresta que conecta um vertice a si mesmo.
Explicacao: Um laco e uma aresta que conecta um vertice a ele mesmo. Em grafos simples,
geralmente nao sao permitidos lacos, mas em grafos nao simples, a presenca de lacos e permitida.
Qual e a representacao mais comum de um grafo nao ponderado?
a) Matriz de adjacencia.
b) Lista de arestas ponderadas.
c