Grafos

Prévia do material em texto

Grafos 
O que caracteriza um grafo simples?
a) Cada aresta pode conectar mais de dois vertices.
b) Cada aresta conecta exatamente dois vertices e nao ha lacos.
c) Existe a possibilidade de multiplas arestas entre dois vertices.
d) Todos os vertices possuem a mesma quantidade de arestas conectadas.
Resposta correta: b) Cada aresta conecta exatamente dois vertices e nao ha lacos.
Explicacao: Um grafo simples e aquele em que as arestas conectam apenas dois vertices e nao
existem lacos (arestas que conectam um vertice a ele mesmo) ou arestas multiplas entre os
mesmos vertices.
Qual e a diferenca entre grafos direcionados e nao direcionados?
a) Em grafos nao direcionados, as arestas possuem uma direcao definida.
b) Grafos direcionados nao possuem arestas.
c) Em grafos direcionados, as arestas tem uma direcao, ou seja, elas vao de um vertice a outro.
d) Grafos direcionados sempre possuem lacos.
Resposta correta: c) Em grafos direcionados, as arestas tem uma direcao, ou seja, elas vao de um
vertice a outro.
Explicacao: Em um grafo direcionado, as arestas possuem um sentido especifico, indo de um
vertice a outro, enquanto em grafos nao direcionados, as arestas nao possuem direcao, ou seja, a
conexao entre os vertices e bidirecional.
O que significa o grau de um vertice em um grafo?
a) O numero de arestas incidentes em um vertice.
b) O numero de arestas conectadas ao vertice, considerando apenas as arestas direcionadas.
c) A quantidade de vertices adjacentes a um vertice.
d) O numero de ciclos que envolvem o vertice.
Resposta correta: a) O numero de arestas incidentes em um vertice.
Explicacao: O grau de um vertice e simplesmente o numero de arestas que incidem sobre ele. Em
grafos direcionados, o grau de entrada e o grau de saida podem ser diferenciados.
Qual e a principal diferenca entre um grafo conexo e um grafo desconexo?
a) Um grafo conexo possui um caminho entre todos os vertices, enquanto em um grafo desconexo,
nao ha caminho entre pelo menos dois vertices.
b) Um grafo conexo possui arestas direcionadas, enquanto um grafo desconexo nao possui
nenhuma aresta.
c) Em grafos conexos, todos os vertices tem grau 2, enquanto em grafos desconexos o grau dos
vertices pode ser maior ou menor.
d) Grafos conexos nao possuem ciclos, enquanto grafos desconexos sempre tem ciclos.
Resposta correta: a) Um grafo conexo possui um caminho entre todos os vertices, enquanto em um
grafo desconexo, nao ha caminho entre pelo menos dois vertices.
Explicacao: Em um grafo conexo, e possivel encontrar um caminho entre qualquer par de vertices.
Ja em um grafo desconexo, existe pelo menos um par de vertices que nao estao conectados por
um caminho.
Qual e a definicao de um ciclo em um grafo?
a) Um caminho que comeca e termina no mesmo vertice, sem repetir arestas.
b) Um caminho entre dois vertices distintos, onde o numero de arestas e impar.
c) Um caminho entre vertices onde o grau de cada vertice e 2.
d) Um caminho em que todas as arestas tem direcao oposta.
Resposta correta: a) Um caminho que comeca e termina no mesmo vertice, sem repetir arestas.
Explicacao: Um ciclo em um grafo e um caminho fechado, ou seja, um caminho que comeca e
termina no mesmo vertice, e que nao repete arestas.
Em um grafo completo, qual e a quantidade de arestas entre
n vertices?
a)
n(n1)
b)
2
n(n1)
c)
n
2
d)
n
Resposta correta: b)
2
n(n1)
Explicacao: Um grafo completo e aquele onde existe uma aresta entre cada par de vertices. A
quantidade total de arestas em um grafo completo com
n vertices e dada pela formula
2
n(n1)
, pois cada par de vertices esta conectado por uma aresta.
Em grafos direcionados, o que e um "vertice isolado"?
a) Um vertice que possui arestas direcionadas tanto de entrada quanto de saida.
b) Um vertice que nao possui arestas incidentes a ele, nem de entrada nem de saida.
c) Um vertice que esta conectado a todos os outros vertices.
d) Um vertice que possui apenas arestas de entrada.
Resposta correta: b) Um vertice que nao possui arestas incidentes a ele, nem de entrada nem de
saida.
Explicacao: Um vertice isolado em um grafo direcionado e aquele que nao possui arestas
incidentes a ele, ou seja, nao tem arestas conectando a ele, nem de entrada nem de saida.
O que caracteriza um grafo bipartido?
a) Os vertices podem ser divididos em dois conjuntos disjuntos, de forma que todas as arestas
conectam vertices de conjuntos diferentes.
b) Todos os vertices de um grafo bipartido tem grau 2.
c) As arestas de um grafo bipartido sao sempre direcionadas.
d) Em grafos bipartidos, os vertices do primeiro conjunto estao conectados apenas aos vertices do
segundo conjunto.
Resposta correta: a) Os vertices podem ser divididos em dois conjuntos disjuntos, de forma que
todas as arestas conectam vertices de conjuntos diferentes.
Explicacao: Um grafo bipartido e aquele cujos vertices podem ser divididos em dois conjuntos
disjuntos, de forma que todas as arestas conectam vertices de conjuntos diferentes. Nao ha arestas
entre vertices do mesmo conjunto.
O que caracteriza um grafo planar?
a) Um grafo que pode ser desenhado no plano sem que suas arestas se cruzem.
b) Um grafo em que todos os vertices possuem o mesmo grau.
c) Um grafo onde todas as arestas tem o mesmo comprimento.
d) Um grafo que possui apenas ciclos.
Resposta correta: a) Um grafo que pode ser desenhado no plano sem que suas arestas se cruzem.
Explicacao: Um grafo e chamado de planar quando e possivel desenha-lo no plano de forma que
suas arestas nao se cruzem, ou seja, ele pode ser desenhado sem que as arestas se
sobreponham.
O que e uma arvore em teoria dos grafos?
a) Um grafo conexo sem ciclos.
b) Um grafo desconexo com um ciclo.
c) Um grafo com arestas direcionadas e ciclos.
d) Um grafo com vertices de grau maior que 2.
Resposta correta: a) Um grafo conexo sem ciclos.
Explicacao: Uma arvore e um tipo especial de grafo que e conexo (existe um caminho entre
quaisquer dois vertices) e nao contem ciclos, ou seja, nao ha caminhos fechados no grafo.
Em um grafo direcionado, o que e um "caminho" entre dois vertices?
a) Uma sequencia de arestas que conecta os vertices, sem repetir nenhuma aresta.
b) Um caminho entre dois vertices onde todas as arestas possuem a mesma direcao.
c) Um caminho entre dois vertices com arestas direcionadas para o vertice de destino.
d) Uma sequencia de vertices com grau 1.
Resposta correta: a) Uma sequencia de arestas que conecta os vertices, sem repetir nenhuma
aresta.
Explicacao: Um caminho entre dois vertices e uma sequencia de arestas direcionadas, onde cada
aresta conecta um vertice ao proximo, e nao ha arestas repetidas.
O que e um "grafo ciclico"?
a) Um grafo que contem pelo menos um ciclo.
b) Um grafo onde todos os vertices possuem grau 3.
c) Um grafo com exatamente um ciclo.
d) Um grafo sem vertices isolados.
Resposta correta: a) Um grafo que contem pelo