523534196-Graphs-Lista-Final

Prévia do material em texto

Lista de Exerćıcios - Teoria dos Grafos
Prof. Amauri H. Souza
April 1, 2021
1. Considere um grafo G satisfazendo as seguintes propriedades:
• G é conexo
• Se removermos qualquer aresta de G, o grafo obtido é desconexo
Então é correto afirmar que o grafo G é:
(a) Um circuito
(b) Não bipartido
(c) Uma árvore
(d) Hamiltoniano
(e) Euleriano
2. Os grafos G = (VG, EG) e H = (VH , EH) são isomorfos. Assinale a alternativa que justifica esta afirmação.
(a) As sequências dos graus dos vértices de G e H são iguais.
(b) Os grafos têm o mesmo número de vértices e o mesmo número de arestas.
(c) Existe uma bijecção de VG em VH que preserva adjacências.
(d) Cada vértice de G e de H pertence a exatamente quatro triângulos distintos.
(e) Ambos os grafos admitem um circuito que passa por cada aresta exatamente uma vez.
3. A respeito da representação de um grafo de n vértices e m arestas é correto dizer que:
(a) a representação sob a forma de matriz de adjacência exige espaço Ω(m2)
1
Se um grafo conexo se torna desconexo ao remover 
qualquer uma das suas arestas, então o grafo é uma 
árvore.
Número diferente de arestas
Somente em Vh
Há mais que 
quatro triângulos.
Passa mais de 
uma vez 
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
(b) a representação sob a forma de listas de adjacência permite verificar a existência de uma aresta ligando
dois vértices dados em tempo O(1).
(c) a representação sob a forma de matriz de adjacência não permite verificar a existência de uma aresta
ligando dois vértices dados em tempo O(1).
(d) a representação sob a forma de listas de adjacência exige espaço Ω(n + m).
(e) Todas as alternativas estão corretas.
4. Um grafo G = (V,E) é uma árvore se G é conexo e aćıclico. Assinale a definição que NÃO pode ser usada
para definir árvores.
(a) G é conexo e o número de arestas é mı́nimo.
(b) G é conexo e o número de vértices excede o número de arestas por uma unidade.
(c) G é aćıclico e o número de vértices excede o número de arestas por uma unidade.
(d) G é aćıclico e, para todo par de vértices v, w, que não são adjacentes em G, a adição da aresta (v, w)
produz um grafo contendo exatamente um ciclo.
(e) G é aćıclico, e o número de arestas é mı́nimo.
5. Em um grafo G = (V,E), o grau de um vértice é o número de vértices adjacentes a v. A esse respeito,
assinale a afirmativa CORRETA.
(a) Num grafo, o número de vértices com grau ı́mpar é sempre par.
(b) Num grafo, o número de vértices com grau par é sempre ı́mpar.
(c) Num grafo, sempre existe algum vértice com grau par.
(d) Num grafo, sempre existe algum vértice com grau ı́mpar.
(e) Num grafo, o número de vértices com grau ı́mpar é sempre igual ao número de vértices com grau par.
6. Seja G = (V,E) um grafo tal que |V | = n e |E| = m. Analise as seguintes sentenças:
I Se G é aćıclico com no máximo n–1 arestas, então G é uma árvore.
II Se G é um ciclo, então G tem n árvores geradoras distintas.
III Se G é conexo com no máximo n–1 arestas, então G é uma árvore.
IV Se G é conexo e tem um ciclo, então para toda árvore geradora T de G, E(G)–E(T ) 6= Ø
A análise permite concluir que:
(a) apenas os itens I e III são verdadeiros.
(b) apenas os Itens II e III são verdadeiros.
(c) apenas o item I é falso.
2
Floresta
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
(d) todos os itens são verdadeiros.
(e) apenas os itens II e IV são verdadeiros.
7. Considere o algoritmo de busca em largura em grafos. Dado o grafo a seguir e o vértice A como ponto de
partida, a ordem em que os vértices são descobertos é dada por:
(a) A B C D E F
(b) A B D C E F
(c) A C D B F E
(d) A B C E D F
(e) A B D F E C
8. Qual é o número cromático do grafo K3,2?
(a) 2
(b) 3
(c) 4
(d) 5
(e) 6
9. Considere o grafo a seguir.
O grafo representa a relação:
(a) R = {(1, 1), (1, 2), (1, 3), (3, 1), (4, 3)}
(b) R = {(1, 1), (1, 2), (1, 3), (3, 1), (3, 4)}
(c) R = {(1, 1), (1, 3), (2, 1), (3, 1), (3, 4)}
(d) R = {(1, 1), (1, 2), (1, 3), (3, 4), (4, 3)}
3
Intuitivamente, você começa pelo vértice raiz e explora todos os 
vértices vizinhos. Então, para cada um desses vértices mais 
próximos, exploramos os seus vértices vizinhos inexplorados e 
assim por diante, até que ele encontre o alvo da busca.
O número cromático de um grafo 
representa o menor número de 
cores necessárias para colorir os 
vértices de um grafo sem que 
vértices adjacentes tenham a 
mesma cor.
Se traçarmos o caminho partindo de 1 
notamos que (1,1) logo em seguida (1,2) e 
(1,3), desta forma já eliminamos os itens 
(c)(d)(e) , continuando, nota-se que o 3 retorna 
ao 1 (3,1) e o 4 ao 3(4,3).Sendo assim, 
relação é dada pelo conjunto de arestas do 
dígrafo. o elemento 5 não esta relacionado a 
nenhum outro elemento. 
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
(e) R = {(1, 1), (1, 3), (2, 1), (3, 1), (4, 3)}
10. Sejam 10 cidades conectadas por rodovias, conforme o grafo a seguir.
Um vendedor sai de uma das cidades com o intuito de visitar cada uma das outras cidades uma única
vez e retornar ao seu ponto de partida. Com base no grafo e nessa informação, considere as afirmativas a
seguir.
(I) O vendedor cumprirá seu propósito com êxito se sair de uma cidade par.
(II) O vendedor cumprirá seu propósito com êxito se sair de uma cidade ı́mpar.
(III) O vendedor não cumprirá seu propósito com êxito se sair de uma cidade par.
(IV) O vendedor não cumprirá seu propósito com êxito se sair de uma cidade ı́mpar.
Assinale a alternativa correta.
(a) Somente as afirmativas I e II são corretas.
(b) Somente as afirmativas I e IV são corretas.
(c) Somente as afirmativas III e IV são corretas.
(d) Somente as afirmativas I, II e III são corretas.
(e) Somente as afirmativas II, III e IV são corretas
11. Seja G um grafo conexo. Considere a notação a seguir.
• cv é o número cromático em vértices de G.
• ce é o número cromático em arestas de G.
• gmin é o grau mı́nimo de G.
• gmax é o grau máximo de G.
• w é a quantidade de vértices do maior subgrafo completo de G.
Assinale a alternativa correta.
(a) cv ≤ ce
4
Francisco Laurindo Costa Junior <francisco.laurindo.costa00@aluno.ifce.edu.br>
(b) cv ≤ w
(c) ce ≤ gmax
(d) cv ≤ gmax + 1
(e) cv ≥ gmin
12. Seja G = (V,E) um grafo em que V é o conjunto de vértices e E é o conjunto de arestas. Com base nesse
grafo, considere as afirmativas a seguir.
I Se G é o K3,3 então o número cromático de G é 3.
II Se G é o K3,3 então, retirando-se uma aresta de G, o grafo se torna planar.
III Se G é o K2,2 então G é um grafo euleriano e hamiltoniano ao mesmo tempo.
IV Se G é um Kn,n então G tem um conjunto independente máximo igual a n.
Assinale a alternativa correta.
(a) Somente as afirmativas I e II são corretas.
(b) Somente as afirmativas I e IV são corretas.
(c) Somente as afirmativas III e IV são corretas.
(d) Somente as afirmativas I, II e III são corretas.(e) Somente as afirmativas II, III e IV são corretas.
13. Seja G = (V,E) um grafo em que V é o conjunto de vértices e E é o conjunto de arestas. Considere a
representação de G como uma matriz de adjacências.
0 1 0 1 0 0
0 0 0 0 1 0
0 0 0 0 1 1
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
O correspondente grafo orientado G é:
(a)
5
(b)
(c)
(d)
(e)
14. Considere os grafos, a seguir.
Pela análise desses grafos, verifica-se que
(a) G3 e G4 são grafos completos.
(b) G1 e G2 são grafos isomorfos.
(c) G3 e G1 são grafos bipartidos.
6
(d) G2 e G3 são grafos planares.
(e) G4 e G1 são multigrafos
15. A matriz de um grafo G = (V,A) contendo n vértices é uma matriz n × n de bits, em que A[i, j] é 1
(ou verdadeiro, no caso de booleanos) se e somente se existir um arco do vértice i para o vértice j. Essa
definição é uma:
(a) Matriz de adjacência para grafos não ponderados.
(b) Matriz de recorrência para grafos não ponderados.
(c) Matriz de incidência para grafos não ponderados.
(d) Matriz de adjacência para grafos ponderados.
(e) Matriz de incidência para grafos ponderados.
16. Em relação a Teoria dos Grafos, relacione a Coluna 1 à Coluna 2.
1 Grafo Completo.
2 Hipergrafo.
3 Árvore Livre.
4 Grafo Planar.
5 Grafo não direcionado antirregular.
( ) Grafo não direcionado, no qual todos os pares
de vértices são adjacentes entre si.
( ) Grafo não direcionado em que cada aresta
conecta um número arbitrário de vértices, ao
invés de conectar dois vértices apenas.
( ) Grafo não direcionado aćıclico e dirigido.
( ) Grafo em que seu esquema pode ser traçado em
um plano, de modo que duas arestas quaisquer
se toquem, no máximo, em alguma extremi-
dade.
( ) Grafo que possui o maior número posśıvel de
graus diferentes em sua sequência.
A ordem correta de preenchimento dos parênteses, de cima para baixo, é:
(a) 1 – 2 – 3 – 4 – 5.
(b) 2 – 3 – 4 – 5 – 1.
(c) 3 – 4 – 5 – 1 – 2.
(d) 4 – 5 – 1 – 2 – 3.
(e) 5 – 1 – 2 – 3 – 4.
17. Em relação ao grafo da Figura (a), as Figuras (b) e (c) representam, respectivamente,
7
(a) matriz de arestas e lista de incidências.
(b) matriz de adjacências e lista de adjacências.
(c) matriz de conexões e lista de arestas.
(d) matriz de incidências e lista de vértices.
(e) matriz de vértices e lista de conexões.
18. O grafo da Figura (a) abaixo indica precedência entre atividades. Uma aresta direcionada (u, v) indica
que a atividade u tem que ser realizada antes da atividade v. Por exemplo, a atividade 3 (representada
pelo vértice 3) somente pode ser iniciada após o término das atividades 0 e 2, já a atividade 9 pode ser
realizada em qualquer ordem.
A Figura (b) acima mostra para o grafo da Figura (a)
(a) os componentes fortemente conectados que representam as atividades mutualmente alcançáveis a
partir de cada vértice.
(b) o caminhamento entre todas as atividades, usando o algoritmo de busca em largura.
(c) a árvore geradora mı́nima que representa todas as possibilidades de conexão entre as atividades,
usando o menor fluxo posśıvel entre elas.
(d) o caminhamento entre todas as atividades, usando o algoritmo de busca em profundidade.
(e) a ordenação topológica que mostra a ordem em que as atividades devem ser processadas.
19. Assinale a alternativa correta sobre as definições básicas de grafos.
8
(a) Um hipergrafo é um grafo direcionado em que cada aresta conecta dois vértices apenas.
(b) Um grafo ponderado é um grafo não direcionado no qual todos os pares de vértices são adjacentes
entre si.
(c) Uma floresta é um grafo não direcionado aćıclico e conectado.
(d) Uma árvore livre é um grafo não direcionado aćıclico, podendo ou não ser conectado.
(e) Um grafo direcionado é fortemente conectado se cada dois vértices quaisquer forem alcançáveis a partir
um do outro.
20. Sobre ordenação topológica em grafos, é correto afirmar que:
(a) A busca em largura é utilizada para obter a ordenação topológica de um grafo direcionado aćıclico.
(b) A ordenação topológica de um grafo pode ser vista como uma ordenação de suas arestas ao longo de
uma linha horizontal, de tal forma que todos os vértices estão classificados em ordem crescente.
(c) A ordenação topológica de um grafo direcionado aćıclico G=(V,A) é uma ordenação linear de todos
os seus vértices tal que G contém uma aresta (u, v), então u aparece antes de v.
(d) A busca binária é utilizada para obter a ordenação topológica de um grafo ćıclico não direcionado.
(e) O algoritmo para obter a ordenação topológica de um grafo direcionado usa o transposto do grafo que
consiste de todas as arestas com as suas direções invertidas.
21. Um mapa rodoviário é modelado como um grafo em que os vértices representam interseções. As arestas
representam segmentos de estrada entre interseções. O peso de cada aresta representa a distância entre
interseções. Agora, considere que um motorista deseja obter o caminho mais curto entre duas cidades.
Dado um mapa contendo as distâncias entre cada par de interseções adjacentes, como obter o caminho
mais curto entre duas cidades?
(a) Caminho mais curto com destino único.
(b) Caminho gerador mı́nimo de origem única.
(c) Caminho mais curto com origem única.
(d) Caminho mais curto entre todos os pares de vértices.
(e) Caminho gerador mı́nimo de origem múltipla.
22. Dado um grafo G e um vértice de origem, qual é o algoritmo de busca que descobre todos os vértices a
uma distância K do vértice origem, antes de descobrir qualquer vértice a uma distância K + 1?
(a) Pré-ordem
(b) Largura
(c) Pós-ordem
(d) Profundidade
(e) Simétrica
9