Grafo no ponderado

Prévia do material em texto

Grafo não ponderado 
O que caracteriza um grafo nao ponderado?
a) As arestas possuem pesos ou valores numericos associados.
b) As arestas nao possuem pesos; apenas indicam conexoes entre vertices.
c) O grafo possui somente um vertice e nenhuma aresta.
d) O grafo sempre e dirigido.
Resposta correta: b
Explicacao: Um grafo nao ponderado e aquele em que as arestas indicam apenas a existencia ou
ausencia de uma conexao, sem valores ou custos associados.
Em um grafo nao ponderado, como e determinada a distancia entre dois vertices?
a) Pelo peso da aresta que conecta os vertices.
b) Pelo numero minimo de arestas necessarias para ir de um vertice ao outro.
c) Pelo produto dos graus dos vertices.
d) Pela soma dos pesos das arestas incidentes.
Resposta correta: b
Explicacao: Em grafos nao ponderados, a distancia entre dois vertices e medida pelo menor
numero de arestas que ligam um ao outro.
Qual algoritmo e mais indicado para encontrar o caminho mais curto em um grafo nao ponderado?
a) Algoritmo de Dijkstra.
b) Busca em Largura (BFS).
c) Algoritmo de Bellman-Ford.
d) Busca em Profundidade (DFS).
Resposta correta: b
Explicacao: A BFS explora os vertices em niveis, garantindo encontrar o caminho com menor
numero de arestas em grafos nao ponderados.
Em um grafo nao ponderado, qual a principal funcao da matriz de adjacencia?
a) Armazenar pesos das arestas.
b) Indicar se ha ou nao uma conexao entre dois vertices.
c) Representar o grau dos vertices.
d) Ordenar os vertices do grafo.
Resposta correta: b
Explicacao: A matriz de adjacencia de um grafo nao ponderado registra se existe uma aresta entre
cada par de vertices, usando valores binarios.
Em um grafo nao ponderado, o que significa dizer que o grafo e conexo?
a) Que existe pelo menos um caminho entre quaisquer dois vertices do grafo.
b) Que todos os vertices tem o mesmo grau.
c) Que o grafo nao possui ciclos.
d) Que o grafo e um grafo dirigido.
Resposta correta: a
Explicacao: Um grafo e conexo quando e possivel alcancar qualquer vertice a partir de qualquer
outro vertice, considerando as conexoes.
Em grafos nao ponderados, qual estrutura de dados e mais eficiente para representar grafos
esparsos?
a) Matriz de adjacencia.
b) Lista de adjacencia.
c) Matriz identidade.
d) Arvore binaria.
Resposta correta: b
Explicacao: A lista de adjacencia armazena apenas as conexoes existentes, economizando espaco
em grafos esparsos.
Qual a diferenca entre o grau de um vertice em grafos dirigidos e nao ponderados?
a) Em grafos nao ponderados, grau e sempre zero.
b) Grau indica o numero de arestas incidentes sem considerar pesos ou direcao.
c) Grau depende do peso das arestas.
d) Grau indica o numero de ciclos envolvendo o vertice.
Resposta correta: b
Explicacao: Grau e o numero total de arestas conectadas a um vertice, independentemente de
pesos ou direcao.
Em um grafo nao ponderado, o que representa uma aresta?
a) Um caminho minimo entre dois vertices.
b) Uma conexao entre dois vertices, sem valor numerico associado.
c) Uma direcao do fluxo entre dois vertices.
d) Um peso aplicado a ligacao.
Resposta correta: b
Explicacao: Aresta em grafo nao ponderado indica simplesmente que ha uma conexao entre dois
vertices.
Por que o algoritmo de busca em profundidade (DFS) pode nao ser ideal para encontrar o caminho
mais curto em grafos nao ponderados?
a) Porque DFS nao visita todos os vertices.
b) Porque DFS pode explorar caminhos longos antes de encontrar um caminho mais curto.
c) Porque DFS nao funciona em grafos nao ponderados.
d) Porque DFS calcula apenas distancias ponderadas.
Resposta correta: b
Explicacao: DFS explora em profundidade, podendo seguir um caminho longo e encontrar uma
solucao que nao e a minima em numero de arestas.
Qual a principal vantagem da BFS em relacao a DFS em grafos nao ponderados?
a) BFS encontra o caminho mais curto em numero de arestas.
b) BFS usa menos memoria que DFS.
c) BFS so funciona em grafos ponderados.
d) BFS e usada para detectar ciclos.
Resposta correta: a
Explicacao: BFS explora os vertices por niveis e garante encontrar o menor caminho em grafos nao
ponderados.
Em um grafo nao ponderado, como pode ser representado um vertice isolado?
a) Vertice que possui arestas apenas para ele mesmo.
b) Vertice que nao possui nenhuma aresta conectada.
c) Vertice com grau igual a um.
d) Vertice com peso zero.
Resposta correta: b
Explicacao: Vertice isolado nao possui arestas ligando-o a outros vertices.
Em um grafo nao ponderado nao dirigido, qual a soma dos graus de todos os vertices em funcao do
numero total de arestas?
a) Igual ao numero total de arestas.
b) Duas vezes o numero total de arestas.
c) Metade do numero total de arestas.
d) Nao existe relacao.
Resposta correta: b
Explicacao: Cada aresta contribui com grau 2 (um para cada vertice conectado), entao a soma dos
graus e 2 vezes o numero de arestas.
O que e um caminho simples em um grafo nao ponderado?
a) Caminho que pode repetir vertices e arestas.
b) Caminho sem repeticao de vertices e arestas, exceto possivelmente o primeiro e o ultimo vertice
serem iguais.
c) Caminho que contem todos os vertices do grafo.
d) Caminho com todas as arestas paralelas.
Resposta correta: b
Explicacao: Caminho simples nao repete vertices nem arestas, a menos que seja um ciclo.
Qual a principal funcao da matriz de incidencia em um grafo nao ponderado?
a) Relacionar vertices e arestas indicando se um vertice e incidente a uma aresta.
b) Indicar pesos das arestas.
c) Armazenar os graus dos vertices.
d) Representar ciclos do grafo.
Resposta correta: a
Explicacao: A matriz de incidencia mostra a ligacao entre vertices e as arestas a que estao
conectados.
Qual algoritmo pode ser usado para detectar se um grafo nao ponderado possui ciclos?
a) Algoritmo de Dijkstra.
b) Busca em profundidade (DFS).
c) Algoritmo de Bellman-Ford.
d) Algoritmo de Prim.
Resposta correta: b
Explicacao: A DFS pode detectar ciclos em grafos nao ponderados verificando se um vertice ja
visitado e encontrado novamente durante a busca.
Em um grafo nao ponderado, o que significa que o grafo e bipartido?
a) O grafo pode ser dividido em dois conjuntos de vertices, sem arestas entre vertices do mesmo
conjunto.
b) O grafo possui exatamente duas arestas.
c) O grafo nao possui ciclos.
d) O grafo e dirigido.
Resposta correta: a
Explicacao: Grafos bipartidos tem vertices divididos em dois grupos, com arestas apenas entre os
grupos.
Em um grafo nao ponderado, qual o significado de um componente conexo?
a) Um subconjunto de vertices onde ha caminho entre quaisquer dois vertices desse subconjunto.
b) Um vertice isolado.
c) Uma aresta que conecta dois vertices.
d) Um ciclo presente no grafo.
Resposta correta: a
Explicacao: Componentes conexos sao partes do grafo em que todos os vertices estao interligados
por algum caminho.
Em um grafo nao ponderado, o que e uma arvore geradora?
a) Um subgrafo conexo que inclui todos os vertices do grafo e nao possui ciclos.
b) Um grafo completo.
c) Um grafo dirigido.
d) Um grafo com apenas vertices isolados.
Resposta correta: a
Explicacao: A arvore geradora e um subconjunto que conecta todos os vertices sem formar ciclos.
Por que os grafos nao ponderados sao usados para modelar redes sociais?
a) Porque as conexoes representam simplesmente relacoes de amizade sem peso.
b) Porque as relacoes tem custo associado.
c) Porque sao grafos direcionados.
d) Porque nao possuem ciclos.
Resposta correta: a
Explicacao: Em redes sociais, as conexoes geralmente indicam a existencia ou ausencia de
relacao, sem valores numericos.
Qual a complexidade do algoritmo BFS para um grafo nao ponderado representado por lista de
adjacencia?
a) O(n2), onde n e o numero de vertices.
b) O(n + m), onde n e o numero de vertices e m o numero de arestas.
c) O(m2), onde m e o numero de arestas.
d) O(1).
Resposta correta: b
Explicacao: BFS visita cada vertice e aresta no maximo uma vez, resultandoem complexidade
linear no tamanho do grafo.
Em um grafo nao ponderado, o que e uma aresta de corte?
a) Uma aresta cuja remocao aumenta o numero de componentes conexos do grafo.
b) Uma aresta que nao esta presente no grafo.
c) Uma aresta que faz parte de um ciclo.
d) Uma aresta que conecta vertices isolados.
Resposta correta: a
Explicacao: Arestas de corte sao essenciais para manter o grafo conexo; sua remocao desconecta
o grafo.
Em um grafo nao ponderado, como pode ser interpretado o caminho encontrado pelo algoritmo
BFS?
a) Caminho com o menor numero de arestas entre dois vertices.
b) Caminho com o menor peso total.
c) Caminho mais longo possivel.
d) Caminho que passa por todos os vertices do grafo.
Resposta correta: a
Explicacao: BFS encontra caminhos minimos em termos de quantidade de arestas.
Qual a diferenca entre uma trilha e um caminho em um grafo nao ponderado?
a) Trilha nao repete arestas; caminho nao repete vertices.
b) Trilha e caminho sao a mesma coisa.
c) Caminho nao repete arestas; trilha nao repete vertices.
d) Trilha passa por todos os vertices; caminho nao.
Resposta correta: a
Explicacao: Trilhas podem repetir vertices, mas nao arestas; caminhos nao repetem vertices.
O que e uma floresta em um grafo nao ponderado?
a) Conjunto de arvores disjuntas, ou seja, grafos aciclicos desconexos.
b) Um grafo completo.
c) Um grafo dirigido.
d) Um grafo com ciclos.
Resposta correta: a
Explicacao: Floresta e uma colecao de arvores, ou seja, grafos aciclicos que podem ser
desconexos.
Em um grafo nao ponderado simples, qual e o numero maximo de arestas possiveis para n
vertices?
a) n(n-1)/2
b) n2
c) n-1
d) 2n
Resposta correta: a
Explicacao: O grafo completo simples tem n(n-1)/2 arestas, todas as possiveis conexoes entre
pares de vertices.
Em um grafo nao ponderado, qual a utilidade da lista de adjacencia?
a) Listar os vertices vizinhos de cada vertice, facilitando a exploracao do grafo.
b) Armazenar pesos das arestas.
c) Contar o numero de ciclos no grafo.
d) Representar o caminho mais longo entre vertices.
Resposta correta: a
Explicacao: A lista de adjacencia armazena para cada vertice sua lista de vizinhos, otimizando
consultas e buscas.
Como pode ser caracterizado um grafo nao ponderado completo?
a) Grafo onde todo par de vertices esta conectado por uma aresta.
b) Grafo sem arestas.
c) Grafo com todos os vertices isolados.
d) Grafo com ciclos minimos.
Resposta correta: a
Explicacao: Em um grafo completo, todos os vertices tem conexao direta com todos os outros.
Em um grafo nao ponderado, o que ocorre quando removemos uma aresta de corte?
a) O grafo torna-se desconexo.
b) O grafo permanece conexo.
c) O numero de vertices diminui.
d) O grau de todos os vertices aumenta.
Resposta correta: a
Explicacao: Remover uma aresta de corte desconecta o grafo, aumentando o numero de
componentes conexos.
Por que grafos nao ponderados sao utilizados em problemas de redes de comunicacao?
a) Porque geralmente a preocupacao e com a existencia da conexao e numero de saltos, nao com
custos.
b) Porque todas as conexoes possuem o mesmo custo.
c) Porque grafos ponderados sao muito complexos.
d) Porque grafos nao ponderados sao sempre dirigidos.
Resposta correta: a
Explicacao: Em muitas redes, interessa o caminho minimo em termos de saltos, nao o custo
associado.
Em um grafo nao ponderado, o que significa a operacao de "complemento" do grafo?
a) Construir um grafo onde as arestas sao todas as conexoes ausentes no grafo original.
b) Remover todos os vertices isolados.
c) Transformar o grafo em dirigido.
d) Aumentar o peso das arestas.
Resposta correta: a
Explicacao: O grafo complemento contem as arestas que nao existem no grafo original.
Como e chamado o conjunto de todos os vertices diretamente conectados a um vertice em um
grafo nao ponderado?
a) Grau do vertice.
b) Vizinhanca do vertice.
c) Ciclo.
d) Caminho.
Resposta correta: b
Explicacao: A vizinhanca e o conjunto de vertices adjacentes a um dado vertice.
O que e um caminho Hamiltoniano em um grafo nao ponderado?
a) Caminho que passa por todos os vertices exatamente uma vez.
b) Caminho que passa por todas as arestas exatamente uma vez.
c) Ciclo minimo do grafo.
d) Caminho que passa por vertices isolados.
Resposta correta: a
Explicacao: Um caminho Hamiltoniano visita todos os vertices sem repetir nenhum.
Qual e a relacao entre grafos nao ponderados e arvores?
a) Toda arvore e um grafo nao ponderado conexo e aciclico.
b) Toda arvore tem pesos associados.
c) Arvore e um grafo dirigido.
d) Arvore possui ciclos.
Resposta correta: a
Explicacao: Arvores sao grafos nao ponderados que sao conexos e sem ciclos.
Em um grafo nao ponderado, o que e um ciclo Euleriano?
a) Ciclo que passa por todas as arestas exatamente uma vez.
b) Ciclo que passa por todos os vertices.
c) Caminho com o menor numero de arestas.
d) Caminho que nao passa por nenhum vertice duas vezes.
Resposta correta: a
Explicacao: Ciclo Euleriano percorre todas as arestas do grafo uma unica vez.
Como se representa um grafo nao ponderado na forma de lista de adjacencia?
a) Para cada vertice, uma lista dos vertices adjacentes sem valores associados.
b) Uma matriz com pesos das arestas.
c) Uma lista de arestas com pesos.
d) Uma tabela de graus dos vertices.
Resposta correta: a
Explicacao: Na lista de adjacencia, para cada vertice ha uma lista dos seus vizinhos.
Qual e o impacto do uso de grafos nao ponderados na eficiencia de algoritmos de busca?
a) Algoritmos como BFS tem complexidade linear no tamanho do grafo, facilitando buscas rapidas.
b) Algoritmos nao funcionam em grafos nao ponderados.
c) Algoritmos sao sempre mais lentos.
d) A complexidade dos algoritmos nao muda.
Resposta correta: a
Explicacao: Grafos nao ponderados simplificam buscas, pois nao ha calculo de pesos, otimizando
algoritmos como BFS.
Em que tipo de problema um grafo nao ponderado e insuficiente?
a) Quando e necessario considerar custos, distancias ou capacidades entre vertices.
b) Em problemas de caminho minimo em numero de arestas.
c) Em problemas de conectividade simples.
d) Em problemas que envolvem apenas existencia de conexoes.
Resposta correta: a
Explicacao: Grafos nao ponderados nao representam valores quantitativos nas conexoes, limitando
sua aplicacao onde custos sao relevantes.
Qual a vantagem de usar um grafo nao ponderado para representar relacoes de amizade