I. O sistema pode ser representado como um grafo misto, onde há a presença de arestas e arcos para representar as rotas de transportes (ruas).
II. Um grafo que possui arcos pode ser chamado de grafo orientado, dirigido ou dígrafo.
III, Em um grafo não orientado a relação é simétrica entre os vértices (a,b) = (b, a), e em um grafo orientado é assimétrica (a,b) != (b, a).
É correto o que se afirma em
A) I e II apenas.
B) II e III apenas.
C) I e III, apenas.
D) I, II e III
E) I, apenas
2) A teoria dos grafos pode ser aplicada em diversas áreas e uma delas é em jogos. Vamos imaginar um jogo em que os jogadores têm o objetivo de explorar um castelo antigo para buscar um tesouro perdido. Este castelo é composto por diversas salas. Os jogadores podem ser movimentar entre elas para progredir na história e enfrentar desafios. O grafo abaixo as salas representam os vértices e o caminho entre elas são as arestas.
- questao_2.jpg (16.57 KiB) Exibido 612 vezes
I. O grafo é conexo e a ordem do grafo é 8 e o tamanho é 8.
II. Este grafo é não direcionado, e neste tipo de grafo, o grau de vértice é determinado pela quantidade de arestas incidentes neste vértice.
III. Neste grafo é possível realizar um ciclo Euleriano, pois todos os vértices possuem grau ímpar.
IV. Este grafo pode ser considerado regular.
É correto o que se afirma em
A) I e II apenas.
B) II e III apenas.
C) I, III e IV apenas.
D) I, II e III.
E) III e IV, apenas.
3) O ciclo euleriano surgiu em 1736 com Leonhard Euler que se deparou com um questionamento existente em uma cidade chamada de Konigsberg. Nela havia sete pontes que cruzavam o rio Pregel. Estas pontes conectavam 4 ilhas (regiões). O questionamento que surgiu foi como é possível sair de uma região e retornar para esta mesma região passando por cada ponte uma única vez?. Levando em consideração o grafo abaixo responda quais afirmativas estão corretas.
- questao_3.jpg (9.38 KiB) Exibido 608 vezes
II. Trata-se de um grafo que possui ciclo euleriano, pois dois vértices são de grau par e os demais de grau ímpar.
III. O ciclo euleriano correspondente a este grafo é: {A-B, B-C, C-D, D-E, E-C, C-G, G-F, F-E, E-G, G-B, B-F, F-A}
IV. Em um ciclo euleriano é permitido repetir vértices.
É correto o que se afirma em
A) I e II apenas
B) II e III apenas
C) I, III e IV apenas.
D) Incorreta: I, II e III.
E) III e IV, apenas.
4) Gustavo está desenvolvendo uma rede social onde os usuários podem se conectar uns com os outros. Uma das funcionalidades que ele quer implementar é um sistema de recomendação de amigos, onde um usuário pode encontrar conexões indiretas (amigos de amigos) dentro da rede. Para isso, ele pode utilizar o algoritmo de busca em profundidade (Depth-First Search, DFS) para explorar a rede e encontrar possíveis recomendações.
Gustavo é um desenvolvedor de software e esta trabalhando em uma rede social. Nesta rede os usuários podem se conectar uns com os outros. Nesta aplicação, o objetivo é recomendação de amigos, onde um usuário pode encontrar conexões indiretas (amigos de amigos) dentro da rede. Para isto, Gustavo deve implementar o caminhamento (ou percurso) no grafo para realizar a busca por um elemento nessa estrutura.
I. O algoritmo de profundidade é útil para verificar se existe um caminho de um vértice para o outro. Logo Gustavo pode usar este algoritmo.
II. Gustavo resolveu usar o algoritmo Depth-First Search (DFS) para realizar o percurso no grafo, pois utiliza os pesos dos vértices para determinar o caminho de menor peso em grafos ponderados.
III. Gustavo também pode usar o algoritmo de busca em largura, pois esse algoritmo explora os vértices de um grafo em camada à medida que aumenta sua distância do vértice inicial.
É correto o que se afirma em
A) I, apenas
B) II, apenas.
C) I e II, apenas.
D) II e III, apenas.
E) I e III, apenas.
5) Durante o planejamento de uma rede de distribuição elétrica inteligente, engenheiros modelaram a estrutura das conexões entre os postos de distribuição e os transformadores utilizando grafos não direcionados. Nessa representação:
Cada vértice representa uma unidade de distribuição (como subestações ou transformadores),
E cada aresta representa uma linha de conexão elétrica entre duas unidades.
Para otimizar a carga e o balanceamento da rede, foi proposto um modelo em que cada unidade de distribuição esteja conectada exatamente ao mesmo número de outras unidades.
Com base nessa modelagem, assinale a alternativa que define corretamente o tipo de grafo descrito, considerando a igualdade de graus entre os vértices:
A) Um grafo é rotulado quando todos os seus vértices têm o mesmo grau.
B) Um grafo é bipartido quando todos os seus vértices têm o mesmo grau.
C) Um grafo é completo quando todos os seus vértices têm o mesmo grau.
D) Um grafo é regular quando todos os seus vértices têm o mesmo grau.
E) Um grafo é valorado quando todos os seus vértices têm o mesmo grau.
6) Qual das seguintes afirmações é verdadeira sobre um ciclo euleriano em um grafo?
A) é um ciclo que passa por cada aresta do grafo uma única vez e retorna ao vértice inicial.
B) é um ciclo que passa por cada vértice do grafo exatamente uma vez e retorna à aresta inicial.
C) é um ciclo que passa por cada vértice do grafo exatamente duas vezes.
D) é um ciclo que passa por cada aresta do grafo exatamente duas vezes.
E) é um ciclo que passa por todos os vértices do grafo, mas não necessariamente retorna ao vértice inicial.
7) Em um projeto de monitoramento ambiental de uma reserva natural, uma equipe de engenheiros utilizou um grafo não direcionado para representar os sensores distribuídos pela área e as conexões diretas entre eles para troca de dados.
Nesse modelo:
- Cada vértice representa um sensor instalado em um ponto da reserva.
- Cada aresta representa uma ligação direta de comunicação entre dois sensores.
- V é o conjunto de sensores ativos, e
- A é o conjunto de pares de sensores conectados diretamente.
- Sensor 1 está conectado aos sensores 2, 3 e 4.
- Sensor 4 está conectado ao sensor 5.
A) V = {1, 2, 3, 4, 5} e A = {{1,2}, {1,4}, {2,3}, {2,4}, {5,4}}
B) V = {1, 2, 3, 4} e A = {{1,2}, {1,3}, {1,4}, {4,5}}
C) V = {1, 2, 3, 4, 5} e A = {{1,2}, {1,3}, {1,4}, {4,5}}
D) V = {1, 2, 3, 4} e A = {{1,2}, {1,4}, {2,3}, {2,4}}
E) V = {1, 2, 3, 4, 5} e A = {{1,2}, {1,3}, {1,4}, {2,3}, {5,4}}
8) Uma empresa de infraestrutura está projetando uma rede de telecomunicação para interligar cidades por meio de cabos de fibra óptica. Para representar essa rede, os engenheiros utilizam grafos, nos quais:
- Cada vértice representa uma cidade, e
- Cada aresta representa uma conexão direta de fibra óptica entre duas cidades.
Durante a análise do grafo da rede, foi necessário calcular a sua ordem, um conceito importante para determinar a escala da infraestrutura.
Com base nesse contexto, assinale a alternativa que define corretamente o conceito de “ordem” de um grafo:
A) Define-se a “ordem” de um grafo como sendo a quantidade de arestas, ou seja, o número de conexões diretas existentes.
B) Define-se a “ordem” de um grafo como sendo a quantidade de vértices que possuem ao menos um vizinho adjacente.
C) Define-se a “ordem” de um grafo como sendo o número total de vértices do grafo, ou seja, o total de cidades conectadas ou não.
D) Define-se a “ordem” de um grafo como sendo a quantidade de caminhos fechados (ciclos) presentes na rede de conexões.
E) Define-se a “ordem” de um grafo como sendo o número de vértices terminais (ou sumidouros), ou seja, cidades que só recebem conexões.
9) Um aluno está estudando a matéria de teoria dos grafos. Ele iniciou seus estudos pelos conceitos básicos de grafos e um deles é conhecer os tipos de grafos.
Assinale a alternativa correta a respeito de tipos de grafos.
A) Um grafo simples pode conter múltiplas arestas entre o mesmo par de vértices.
B) Um multigrafos é aquele em que vértices podem conter arestas em paralelo.
C) Um grafo bipartido é aquele em que os vértices podem ser divididos em três conjuntos disjuntos.
D) Um grafo direcionado é aquele em que cada aresta não tem direção e pode ser percorrida em ambos os sentidos.
E) Um grafo conexo é aquele em que não há caminho entre pelo menos um par de vértices.
10) Na modelagem de sistemas de transporte urbano, é comum representar os pontos de parada (como estações, terminais e pontos de ônibus) por nós de um grafo, enquanto os trajetos ou conexões entre eles são representados por arestas.
Em um estudo para otimizar as conexões entre os bairros de uma cidade, os engenheiros criaram um grafo em que:
- Cada nó representa uma estação de integração.
- Cada aresta representa um trajeto direto entre duas estações.
Com base nesse modelo, foi necessário calcular o grau de cada nó para identificar os pontos com maior fluxo de conexões.
Nesse contexto, é correto afirmar que o grau de um nó é:
A) o número de arcos (ou arestas) incidentes nesse nó.
B) um número associado ao arco, também chamado de peso.
C) a distância entre este nó e um outro nó qualquer do grafo.
D) a posição deste nó em relação ao nó raiz do grafo.
E) o número de pares ordenados que formam o arco.
11) Uma equipe de urbanistas projetou um parque interativo composto por sete atrações principais conectadas por doze trilhas. A estrutura foi representada por um grafo não direcionado, em que:
- Cada vértice representa uma atração, e
- Cada aresta representa uma trilha que liga diretamente duas atrações.
Durante um festival cultural, uma visitante deseja percorrer todas as trilhas do parque uma única vez, iniciando e finalizando o percurso na mesma atração — independentemente de qual for o ponto de partida.
Com base nessa situação e nos conceitos de grafos, avalie as afirmações:
I. É possível realizar o passeio, pois o grafo é euleriano, ou seja, há um ciclo que começa e termina no mesmo vértice e passa por todas as arestas apenas uma vez.
II. O passeio é possível porque o grafo é euleriano, já que ele é conexo e todos os vértices possuem grau par.
III. O passeio também é possível porque o grafo é hamiltoniano, ou seja, ele possui um ciclo que visita todos os vértices uma única vez, sem repetir, e retorna ao ponto inicial.
É correto apenas o que se afirma em:
A) I, apenas.
B) III, apenas.
C) I e II, apenas.
D) II e III, apenas.
E) I, II e III.
12) Imagine um mapa contendo as cidades e as estradas que as ligam. Duas cidades (vértices) que se conectam através de uma estrada são ditas adjacentes e duas estradas (arestas) que partem de uma mesma cidade são ditas ligações adjacentes também. Logo, podemos dizer que um percurso em um grafo é uma coleção de vértices ou arestas sequencialmente adjacentes.
I. Vamos considerar que a cidade A possui 3 estradas que conectam a outras cidades. Logo podemos dizer que o grau do vértice A é 3.
II. A vizinhança da cidade A é formada por todas as cidades adjacentes a ela, ou seja, inclui todas as cidades ligadas diretamente a ela.
III. Matriz de incidência é uma matriz que apresenta a relação entre vértices e arestas. Logo, se a cidade A possui as estradas 1, 2 e 3 ligadas a ela, na matriz de incidência a coluna será representada pelo vértice A e as linhas pelas arestas 1, 2 e 3, ou o contrário também é possível.
É correto o que se afirma em
A) I e II apenas.
B) II e III apenas.
C) I e III, apenas
D) I, II e III.
E) I, apenas.
13) Gustavo está implementado uma rede social na qual os usuários estão conectados. Neste projeto uma das funcionalidades permite enviar uma mensagem de e-mail para outro usuário usando as conexões entre eles. Para isto, a mensagem sai de um computador de origem e se encaminha para outro computador pelo caminho mais curto.
Considerado essa situação, sobre os algoritmos que Gustavo pode implementar para estabelecer essa menor rota, avalie as asserções a seguir e a relação proposta entre elas.
I. Gustavo pode implementar o algoritmo de Dijkstra por se tratar de um dos algoritmos empregado para resolver problemas de menor caminho em grafo.
II. O algoritmo de Dijkstra é um algoritmo que pode ser aplicado a grafos que possuem arestas com pesos negativos.
III. Gustavo pode usar o algoritmo de Dijkstra que é um algoritmo que determina o caminho mais curto de um vértice de origem a todos os outros em um grafo ponderado.
A respeito dessas asserções, assinale a opção correta.
A) As asserções I, II e III são proposições verdadeiras
B) As asserções I e II são proposições verdadeiras, mas a III é falsa
C) As asserções I e III são proposições verdadeira, e a II é uma proposição falsa
D) As asserções I é uma proposição falsa, e a II e III são proposições verdadeiras
E) As asserções I, II e III são proposições falsas
14) Um grafo consiste em um conjunto de vértices, também denominados de nós e em um conjunto de arestas(arcos). É correto afirmar que em um grafo direcionado o grau total de um nó é:
A) Composto pelo grau interno e o grau externo, ou seja, a soma do grau de entrada e saída deste nó.
B) O número de vértices do grafo.
C) A soma de todos os valores de arestas.
D) A distância deste nó a qualquer outro do grafo.
E) A quantidade de arestas do grafo.
15) Considere uma cidade pequena com várias ruas e esquinas conectadas. Uma empresa de entregas precisa planejar uma rota para entregar pacotes em cada esquina exatamente uma vez, retornando ao depósito inicial no final. A empresa deseja minimizar a distância total percorrida durante a entrega.
Gustavo irá implementar esta aplicação onde as esquinas da cidade são os vértices do grafo, onde as ruas são representadas por arestas. Um ciclo hamiltoniano nesta rede representaria uma rota que visita cada esquina exatamente uma vez, exceto o depósito inicial, onde a rota começa e termina.
Qual das seguintes afirmações é verdadeira sobre a rota planejada pela empresa de entregas?
A) A rota planejada passará por cada rua da cidade exatamente uma vez, garantindo que todos os pacotes sejam entregues.
B) A rota planejada passará por cada esquina da cidade exatamente uma vez, exceto o depósito inicial, onde a rota começa e termina.
C) A rota planejada passará pela mesma esquina várias vezes para garantir que todos os pacotes sejam entregues com eficiência.
D) A rota planejada passará pelo depósito inicial e final várias vezes para garantir que todos os pacotes sejam entregues.
E) A rota planejada passará por cada esquina e por cada rua quantas vezes forem necessárias para realizar todas as entregas, mesmo que tenha que repetir as visitas as esquinas e ruas.