📝

Lista de Exercícios 3
Aula do dia @26/04/2025

Disciplina 📍 Grafos e Aplicações

Tipo Estudos

Pontos principais Aula 3

Q1 - Grafos vs. Árvores

Explique as principais diferenças conceituais entre grafos e árvores. Discuta
como as estruturas de dados utilizadas para representar cada uma (listas de
adjacência, matrizes, etc.) refletem essas diferenças.

Resposta
Árvore são tipos especial de grafos, sendo conexas e acíclicas, enquanto um
grafo pode ter ciclos e não precisa necessariamente ser conexo.
Em árvore também há exatamente um único caminho simples entre quaisquer
dois vértices.
Listas e matrizes de adjacência mostram essas diferenças logo de cara:

Matrizes de adjacência raramente são utilizadas para representar árvores,

já que elas são esparsas, porém podem ser úteis para grafos muito densos

Listas de adjacência são muito utilizadas em árvores pois tornam a busca

eficiente, e se mostrar melhores para grafos esparsos.

Q2 - Busca em Largura (BFS)

Explique em detalhes o funcionamento do algoritmo BFS. Em sua resposta,
inclua:

Utilização de uma fila como estrutura auxiliar

Lista de Exercícios 3 1
 O papel do esquema de cores (branco, cinza e preto) para marcar o status
dos vértices

Como o algoritmo garante a descoberta de caminho mínimos

Resposta
O algoritmo BFS realiza uma busca em camadas pelo grafo, visitando todos os
vizinhos do vértice inicial, depois os vizinhos dos vizinhos e por aí vai até
terminar de visitar todos os vértices
Todos os vértices começam com a cor branca (não visitado) e a distância até
cada vértice é considerada infinita, exceto pelo vértice inicial que é 0
A fila se inicia vazia.

No começo da busca, o vértice inicial é pintado de cinza (descoberto, porém

não visitado) e colocado na fila
Até que a fila esteja vazia o algoritmo:

1. Remove o primeiro vértice da fila (explora)

2. Para cada vizinho de cor branca deste vértice:

a. Pinta de cinza (descoberto, não visitado)

b. Define sua distância como a distância do vértice pai + 1

c. Coloca os vizinhos na fila

3. Depois de explorados todos os vizinhos, pinta o vértice na cor preta

(visitado)

A utilização da fila faz com que os vértices sejam processados na ordem de

descoberta, fazendo com que o grafo seja explorado por ordem de largura ou
camadas.

O esquema de cores ajuda a classificar os vértices:

Branco — Não descoberto

Cinza — Descoberto, não visitado, está na fila

Preto — Visitado, consumido

O algoritmo garante a descoberta de caminhos mínimos pois sempre visita os

vértices mais próximos, calculando o menor número de arestas necessárias
para chegar em um vértice, logo, o caminho do vértice inicial até qualquer
outro é o caminho de menor comprimento

Lista de Exercícios 3 2
 Q3 - Exercício Prático com Graphviz - BFS
Considere o seguinte grafo representado pelo código DOT abaixo:

digraph G {
A -> B;
A -> C;
B -> D;
B -> E;
C -> F;
E -> F;
D -> G;
F -> G;
}

Gere uma figura a partir deste código

Execute o algoritmo BFS a partir do vértice A e anote a ordem de descoberta
dos vértices.

Resposta
1. Inicializa A com cinza e distância
0

2. Visita A

a. B e C são colocados na fila e

pintados de cinza

b. Fila: B C

3. Visita B

a. D e E são colocados na fila

(cinza)

b. Fila: C D E

4. Visita C

a. F é colocado na fila

b. Fila: D E F

Ordem de descoberta: 5. Visita D

Lista de Exercícios 3 3
 a. Coloca G na fila
A -> B -> C -> D -> E -> F -> G
b. Fila: E F G

6. Visita E

a. F já está na fila, próximo

b. Fila: F G

7. Visita F

a. G já está na fila, próximo

b. Fila: G

8. Visita G

a. Sem vizinhos

9. Fim.

Q4 - Complexidade do BFS
Determine a complexidade temporal do algoritmo BFS em termos de |V|
(número de vértices) e |E| (número de arestas). Justifique sua resposta.

Resposta
Complexidade de O(|V| + |E|)
Cada vértice precisa ser visitado pelo menos uma vez, e cada aresta é
verificada apenas uma vez (para saber se leva a um novo vértice)

Q5 - Pseudocódigo do BFS
Escreva um pseudocódigo simples para o algoritmo de Busca em Largura,
enfatizando a atualização dos estados dos vértices.

Resposta

BFS(G, s):
para cada vértice v em G.V:
cor[v] = BRANCO
distancia[v] = ∞
predecessor[v] = NULL

Lista de Exercícios 3 4
 cor[s] = CINZA
distancia[s] = 0
predecessor[s] = NULL
fila = nova Fila()
fila.enfileira(s)

enquanto fila não está vazia:

u = fila.desenfileira()

para cada vértice v adjacente de u:

se cor[v] == BRANCO:
cor[v] = CINZA
distancia[v] = distancia[u] + 1
predecessor[v] = u
fila.enfileira(v)

cor[u] = PRETO

Q6 - Busca em Profundidade (DFS)

Descreva o funcionamento do algoritmo DFS e como ele utiliza uma pilha
(explícita ou pela recursão).
Explique a importância dos vetores d[v] (tempo de descoberta) e f[v] (tempo
de finalização).

Resposta
A DFS explora o grafo indo o mais longe possível em um caminho antes de
explorar outros.

Começamos no vértice inicial, o marcando como descoberto

Para cada vizinho não visitado, chamamos a função recursivamente

Quando todos os vizinhos de um vértice foram explorado, voltamos ao

vértice anterior

Podemos utilizar uma pilha explicitamente (push e pop de vértices) ou

implicitamente (recursão — call stack)

Lista de Exercícios 3 5
 A pilha é usada para garantir que o grafo seja explorado por profundidade, ou
seja, cada novo vértice descoberto é explorado antes de voltar ao anterior
Os vetores de tempo de descoberta (d[u]) e finalização (f[u]) são importantes
para classificar arestas (árvore, retorno, avanço e cruzamento), determinar a
ancestralidade de vértices e realizar ordenação topológica.

Tempo de descoberta é quando o vértice é encontrado pela primeira vez

Tempo de finalização é quando terminamos de visitar todos os vizinhos de

um vértice

Q7 - Classificação de Arestas em DFS

Liste e defina os quatro tipos de arestas (árvore, retorno, avanço e
cruzamento) identificados durante uma execução da DFS. Ilustre cada tipo com
um exemplo simples.

Resposta
Árvore: Aresta que leva a um vértice branco - não descoberto
Retorno: Aresta que leva a um vértice cinza - indica que há ciclos no grafo

Avanço: Aresta que leva a um vértice totalmente explorado (preto)

Cruzamento: Aresta entre vértices que não são ancestrais ou descendentes -

vértice de diferentes ramos

Lista de Exercícios 3 6
 Q8 - Teorema dos Parênteses
Explique o Teorema dos Parênteses no contexto da DFS e como os intervalos
[d[u], f[u]] podem ser utilizados para determinar relações de ancestralidade
entre os vértices.

Resposta
O teorema dos parênteses diz que durante a execução de uma DFS cada
vértice recebe um tempo de descoberta e um tempo de finalização, e esses
tempos se organizam como parênteses (abrimos um parênteses na descoberta
e o fechamos na finalização).
Isso nos ajuda a determinar ancestralidade pois, se um intervalo d[u] → f[u]
está contido em d[v] → f[v], significa que o nó u é um descendente de v, já que
ele é explorado e finalizado antes da finalização de v
Se os intervalos não se sobrepõem, então u e v estão em subárvores diferentes

Q9 - Comparação: BFS vs. DFS

Liste, pelo menos, três diferenças fundamentais entre os algoritmos de busca
em largura e em profundidade, tanto na implementação quanto nas

Lista de Exercícios 3 7
 informações que cada um extrai do grafo.

Resposta
BFS usa fila e DFS utiliza uma pilha

BFS visita os vértices por nível de distância, primeiro os vizinhos, depois

vizinhos dos vizinhos — DFS vai até o fim de um caminho antes de voltar

BFS obtém os caminhos mínimos entre o vértice inicial e qualquer outro —

DFS permite classificar as arestas e detectar ciclos

Q10 - Grafos Acíclicos

Defina o que é um grafo acíclico. Explique, utilizando exemplos, como a
ausência de ciclos pode ser verificada em um grafo.

Resposta
Um grafo acíclico é um grafo sem ciclos/caminhos fechado, não existe nenhum
caminho onde um vértice pode ser alcançado novamente partindo dele
mesmo.
Se ele for um grafo direcionado, é chamado DAG (directed acyclic graph)
Podemos verificar a ausência de ciclos em um grafo utilizando a DFS para
verificar arestas de retorno, ou tentar realizar a ordenação topológica do grafo.

Q11 - Conectividade em Grafos

Defina o que significa um grafo ser conexo. Forneça um exemplo de grafo
desconexo e explique por que ele não satisfaz a propriedade de conectividade.

Resposta
Um grafo é conexo se existe um caminho entre qualquer par de vértices
Podemos ir de qualquer vértice A para qualquer vértice B seguindo as arestas
do grafo

Neste exemplo de grafo desconexo,

não há nenhum caminho de A até C
ou B até D por exemplo, fazendo com
que ele não cumpra os requisitos
para ser um grafo conexo

Lista de Exercícios 3 8
 digraph G {
A -> B;
C -> D;
}

Q12 - Teorema dos Grafos Conexos

Explique o seguinte teorema: Qualquer grafo conexo G, com n vértices, deve
ter pelo menos n − 1 arestas

Resposta
Para garantir que um grafo seja conexo, ele precisa de um número mínimo de
arestas para conectar todos os vértices:

Um grafo com 2 vértices precisa de pelo menos uma aresta

Um com 3 vértices, no mínimo duas arestas

Para n vértices, é necessário pelo menos n - 1 arestas para garantir a

conexão entre os vértices

Q16 - Ordenação Topológica

Defina o que é uma ordenação topológica e identifique em que tipo de grafo
ela pode ser aplicada.
Explique por que a existência de ciclos inviabiliza a ordenação topológica.

Resposta
Uma ordenação topológica de um grafo dirigido é uma forma de organizar seus
vértices em uma sequência linear, de forma que para cada aresta direcionada u
→ v, u apareça antes de v na sequência
A existência de ciclos inviabiliza a ordenação topológica pois cria dependência
circulares entre vértices, fazendo impossível a realização de uma ordenação
linear.

Q19 - Caminhadas Aleatórias e Cadeias de Markov

Explique a relação entre caminhadas aleatórias em grafos e cadeias de Markov
finitas.

Lista de Exercícios 3 9
 Quais aplicações práticas podem se beneficiar desta abordagem?

Resposta
Uma caminhada aleatória em um grafo é um processo estocástico onde um
"caminhante" se move de um vértice para outro de forma aleatória, geralmente
seguindo as arestas do grafo. A cada passo, a escolha do próximo vértice
depende apenas do vértice atual e da distribuição das arestas, sem considerar
a história dos passos anteriores.
Uma cadeia de Markov é um processo estocástico que possui a propriedade
de "memória curta", ou seja, o estado futuro do processo depende apenas do
estado atual e não dos estados passados. Isso é conhecido como a
propriedade de Markov.
Uma caminhada aleatória pode ser modelada como uma cadeia de Markov, os
estados correspondem aos vértices e a transição entre eles segue uma
distribuição de probabilidade dependendo das arestas do vértice atual.
As principais aplicações desta abordagem se dão em algoritmos de conexão
de redes sociais, redes de computadores e o famoso algoritmo PageRank

Q20 - Aplicações Práticas

Discuta uma situação real em que os algoritmos de busca (BFS e DFS) e a
ordenação topológica possam ser aplicados para resolver problemas práticos
(por exemplo, gerenciamento de tarefas, análise de redes, etc.). Quais desafios
você espera encontrar na implementação dessa solução?

Resposta
Uma situação prática e real é o gerenciamento de tarefas com dependências
em um projeto de software.

Cada tarefa seria um vértice

Uma aresta de A a B significa que A precisa ser concluída antes de B

começar

Usaríamos ordenação topológica para ordenar as tarefas em uma sequência

que respeite as dependências
Podemos usar BFS para encontrar o caminho mais curto entre uma tarefa e
outra

Lista de Exercícios 3 10
 E DFS para identificar todos os caminhos de execução possíveis, e detectar
possíveis ciclos (que tornariam as tarefas impossíveis)
Desafios possíveis:

Detecção e resolução de ciclos

Volume de dados (muitas tarefas)

Mudanças dinâmicas (novas tarefas ou remoções)

Ordem de prioridade

Lista de Exercícios 3 11