Exercícios PAA- Grafos
Eduardo Laber
Exercício de Implementação
1. Modifique o código da BFS para que esta preencha um vetor d com n
entradas aonde d(u) é a distância da origem s até o vértice u.
for every vertex v of G not explored yet
d(v) infinito
End For
2
d(s)  0
3
mark vertex s as visited
4
while S is not empty do
5
u ← Dequeue(S);
6
For each v in Adj[u] then
7
if v is unexplored then
8
mark vertex v as visited
9
d(v)  d(u)+1
10
Enqueue(S,v)
2
Cap 3-Tardos
Exercício 2
• Modifique o pseudo-código da busca em
profundidade da seguinte forma.
• Ao visitar um vértice v a partir de u
– Se v não foi visitado faça
• upai (v)
– Se v já foi visitado
• Se v<> pai(u)
– Ciclo existe (uv+ caminho de u a v na árvore)
Cap 3-Tardos
Exercicio 2: Ciclo em grafo direcionado
• Execute uma busca em profundidade no grafo anotando, para cada
vértice v,
– o pai de v
– o momento que a busca em v começa: pre(v)
– o momento que a busca em v termina: pos(v)
• Ao tentar visitar um vértice v a partir de u tal que a busca em v já
começou mais ainda não terminou (pos(v) =-1) podemos obter um
ciclo da seguinte forma.
– Caminhe pelos pais de u até encontrar v. O ciclo é formado por este
caminho + o arco (u,v)
Cap 3-Tardos
Exercício 3
• Execute uma ordenação topológica no Grafo. Se em algum ponto
não houver uma fonte, quer dizer que o grafo contém ciclos.
• Execute o algoritmo do slide anterior
Cap 3-Tardos
Exercício 4
• Etapa 1. Construa o grafo G[S] induzido pelas
arestas do conjunto S. Utilize uma DFS(BFS)
para determinar as componentes conexas deste
grafo. Atribua o número da componente para
cada vértice (borboleta).
• Etapa 2. Faça uma varredura nos pares (i,j) tal
que a borboleta i é diferente da borboleta j. Se
algum par (i, j) for encontrado tal que a
borboleta i está na mesma componente de j
(conforme etapa 1) então a atribuição é
inconsistente. Se nenhum par for encontrado a
atribuiçào é consistente.
• O(m+n)
Cap 3-Tardos
Exercício 7
• Seja v um nó do grafo. Se u não é vizinho
de v então existe um nó, digamos w, que
é vizinho de u e de v. Caso contrário o
grafo teria mais de n vértices (n/2 vizinhos
de u, n/2 outros vizinhos de v, u e v).
Contradição
• Portanto, vwu é um caminho de v
para u
Cap 3-Tardos
Exercício 8
• Para um contra exemplo considere uma
clique K com n- n0.5 e um único vértice
desta clique ligado a um caminho de n0.5
vértices.
Cap 3-Tardos
Exercício 9
• Considerar a árvore gerada a partir de
uma busca em largura começando em s.
– Como a altura desta árvore é maior que n/2
então existe um nível nesta árvore ( > 1 e <
nível t) com apenas um nó.
– Como toda aresta de G liga vértices da
mesma camada ou de camadas adjacentes,
ao remover este vértice desconectamos o
grafo.
Cap 3-Tardos
Exercício 9
• Algoritmo
– Faça uma busca em largura calculando a
distância de s a cada nó e preencha um vetor
(de listas) indicando, na posição i, os vértices
que distam i de s. Retorne o primeiro nó
diferente de s que se encontra sozinho em
uma lista
Cap 3-Tardos
Exercício 10
• Utilizar uma busca em largura para decompor a
árvore em camadas. Marcar para cada nó u a
sua distância ao nó de origem v.
• Em uma segunda passada acumular em cada
nó u um contador num(u) indicando o número
de caminhos de v a u.
– Inicialmente os contadores são 0, exceto Num(v)=1.
– Ao tentar visitar um nó y, com d(y)=i+1, a partir de um
nó x, com d(x)=i, fazer
num(y) num(y)+num(x)
Cap 3-Tardos
Exercício 12
Construa um grafo direcionados G da seguinte forma
a) Para cada pessoa P(i) crie dois vértices: B(i) – data de
nascimento e D(i), data de morte
b) Para todo i, crie uma arco de B(i) para D(i)
c) Se nos dados coletados, P(i) morre antes de P(j) nascer
crie um arco de D(i) para B(j)
d) Se nos dados coletados, a vida de P(i) tem interseção
com a vida de P(j), crie um arco de P(i) para B(j) e um
arco de B(i) para P(j)
Se G tem uma ordenação topológica os dados são
consistentes, caso contrário não
Dasgupta-Cap 3
Exercício 8
• Criamos 11*8*5=440 nós e associamos
cada nó do grafo a uma tripla (a,b,c)
correspondendo a quantidade de água em
cada um dos recipientes.
• . Existe uma aresta direcionado de um nó
para outro se for possivel de um estado
alcancar o outro com um movimento.
Dasgupta-Cap 3
Exercício 8
• Cada nó pode ter 6 arestas partindo dele,
logo o número de arestas é no máximo
1320
Dasgupta-Cap 3
Exercício 8
Basta executar uma BFS(DFS) no grafo
começando no estado (0,7,4) e verificar
se o estado (0,0,0) e alcançável
Dasgupta-Cap 3
Exercício 9
• Duas passadas completas na lista de
adjacência do grafo
– A primeira passada calcula o grau de cada
vértice
• For each v in Adj[u]
– degree(u)  degree(u)+1
– Na segunda, acumulamos em twodegree[u],
para cada u, a soma dos graus dos vizinhos
de u.
• For each v in Adj[u]
– Twodegree[u]  Twodegree[u]+d(v)
Dasgupta-Cap 3
Exercício 13
a) Defina um vértice s em G e execute uma
DFS a partir de s. Seja T a árvore obtida.
Qualquer folha de T satisfaz a propriedade
desejada
b) Qualquer Ciclo direcionado
c) G= dois ciclos disjuntos
Dasgupta-Cap 3
Exercício 15
a) Seja G=(V,E) o grafo direcionado em
que V é o conjunto de interseções de
ruas e E representa o conjunto das ruas
• Verifique se o grafo é fortemente conexo
utilizando o algoritmo ensinado em sala
com complexidade O(m+n)
Dasgupta-Cap 3
Exercício 15
b) Seja v o nó correspondente a Town Hall. Seja
S o conjunto de nó alcançáveis a partir de v. S
pode ser obtido em O(m+n) através de uma
DFS( BFS).
Seja G’ o grafo reverso de G. Seja T o
conjunto de nós obtidos a partir de v em G’.
Se S for um subconjunto de T então a
propriedade é verdadeira. Caso contrário, é
falsa. Podemos testar se S e subconjunto de T
em O(n)
Dasgupta-Cap 3
Exercício 18
• Execute uma DFS em G a partir de r e
armazene os contadores pre e post para
cada vértice do grafo.
• u é ancestral de v se e somente se
pre[u] <pre[v]< post[v]<post[u]
Dasgupta-Cap 3
Exercício 22
• Execute uma DFS em G e armazene os
contadores pre e post para cada vértice do
grafo. Seja v o vértice com maior post. Sabemos
que ele pertence a um source node em G~ (aula
de componentes fortemente conexos).
• Execute uma DFS começando em v. Se apenas
uma árvore for gerada então existe o nó
desejado. Caso contrário, não.
Dasgupta-Cap 3
Exercício 24
Execute o algoritmo linear para ordenação
topológica.
• Se em algum ponto o conjunto S dos
vértices com grau de entrada igual a 0
tiver mais de um elemento, então G não
possui o caminho desejado. Caso
contrário, ordem topológica é o caminho
desejado.
Exercicio Resolvido
Problema
Seja um grafo G=(V,E) representando a planta de um edifício.
Inicialmente temos dois robos localizados em dois vértices de V, a e b,
que devem alcançar os vértices c e d de V.
A cada passo um dos robos deve caminhar para um vértice adjacente ao
vértice que ele se encontra no momento.
Exiba um algoritmo polinomial que decida se é possível, ou não, os robos
partirem de a e b e chegarem em c e d, respectivamente, sem que em
nenhum momento eles estejam a distância menor do que r, onde r é um
inteiro dado.
23
Exercicio Resolvido
Solução
Seja H um grafo representando as configurações possíveis (posições
dos robos) do problema. Cada nó de H corresponde a um par ordenado
de vértices de V cuja distância menor ou igual a r.
Um par de nós u e v de H tem uma aresta se e somente em um passo é
possível alcançar a configuração v a partir da configuração u em um
único passo, ou seja, se u=(u1,u2) e v=(v1,v2) então uma das alternativas
é válida
(i) u1=v1 e (u2,v2) pertence a E
(i) u2=v2 e (u1,v1) pertence a E
O problema portanto consiste em decidir se existe um camìnho entre o
nó (a,b) e o nó (c,d) em H. Isso requer tempo linear no tamanho de H.
Como H tem O(n2) vértices e O(n3) arestas, o algoritmo executa em
O(n3) .
24
Dasgupta, Cap 4 -Exercício 11
• Execute Dijkstra a partir de cada vértice v.
O(|V|3)
• Guarde em uma tabela Dist a menor
distância Dist(u,v) entre u e v para cada
para u,v
• Procure na tabela Dist o par de vértices
u,v que minimiza Dist(u,v)+Dist(v,u). Se o
mínimo é infinito então o grafo é acíclico
– O(|V|3), já que temos que considerar todos os
pares
Dasgupta, Cap 4 -Exercício 12
• Seja e=(u,v)
• Remova a aresta e de G
– O(|V|)
• Execute Dijkstra para encontrar o caminho
P de custo mínimo entre v e u em G-e.
– O(|V|2), utilizando vetor como fila de
prioridades
• O ciclo é dado pela união de P com e.
Dasgupta, Cap 4 -Exercício 14
1. Execute Dijkstra para encontrar o
caminho de custo mínimo entre v0 e os
demais vertices em G
2. Execute Dijkstra para encontrar o
caminho de custo mínimo entre v0 e os
demais vertices em GR (grafo reverso)
3. O caminho mínimo entre u e w passando
por vo é o caminho mínimo entre u e v0 e
vo e w
Dasgupta, Cap 4 -Exercício 17.a
• Utilize um vetor de nW posições como fila
de prioridade.
• A posição i do vetor deve guardar os nós v
tal que o custo π(v) do menor caminho da
origem s até v é i.
Dasgupta, Cap 4 -Exercício 17.a
• Portanto, encontrar o custo total de
encontrar o vértice com menor valor π()
requer O(nW) operações
– Se o ultimo vértice colocado em S foi u então
a busca pelo menor valor de π() deve ser
feita a partir de π(u).
• As atualizações podem ser feitas em O(E)
ESTUDEM