Ea 4
Ea 4
Ea 4
3 Considere a planta baixa de uma casa abaixo. Como determinar se é possível partir de algum
cômodo da casa, visitar todos os cômodos mas passando uma única vez em cada porta, e sempre vol-
tando ao cômodo do início? Modele o problema usando grafos, identificando vértices e arestas, além
de fornecer um algoritmo que resolve o problema.
1
Fonte: Levitin 3ed.
a. Execute o algoritmo de backtracking apresentado para o problema (isto é, aquele que vai cons-
truindo passo-a-passo todos os circuitos).
b. Execute as três heurísticas construtivas para o problema: “vizinho mais próximo”, “inserção mais
próxima” e “inserção gulosa de arestas”. Deixe indicado os caminhos intermediários sendo cons-
truídos em cada caso.
a. Supondo que o predecessor de um vértice u.π esteja corretamente determinado após a execução
de algum algoritmo de caminhos mínimos a partir de uma única fonte (Bellman-Ford ou Dijkstra),
crie um algoritmo que imprima a sequência de vértices em um caminho mínimo entre u, v ∈ V .
Assinatura: PRINT-SHORTEST-PATH(u).
2
8 Considere o problema de encontrar os caminhos de custo mínimo a partir de uma única fonte s em
um grafo acíclico direcionado (DAG) e ponderado. Forneça um algoritmo de complexidade O(m + n)
que resolva o problema. Dica: ordenação topológica.
9 Seja um grafo G = (V, E) direcionado e com pesos nas arestas. Os vértices desse grafo represen-
tam nós em uma rede de computadores e os arcos representa canais de comunicação entre um par de
computadores. O peso de um arco (u, v), denotado como w(u, v), indica a confiabilidade do respec-
tivo canal e representa probabilidade de que o canal u para v não falhe (um número entre 0 e 1:
0 ≤ w(u, v) ≤ 1). Assumindo que as probabilidades sejam independentes, forneça um algoritmo que
dados dois vértices fonte s e destino t e o grafo em questão, calcule o caminho mais confiável entre s e
t.
11 Como adaptar o problema do fluxo máximo para o caso em que se tem múltiplas fontes (s1 , s2 , · · · )
e/ou múltiplos destinos (t 1 , t 2 , · · · )? Explique as modificações necessárias.
12 P quePs ∈ S (fonte)
Um corte em uma rede de fluxo é uma partição dos vértices em S e T , de modo
e t ∈ T (destino). A capacidade de um corte (S, T ) é definida como sendo c(S, T ) = u∈S v∈T c(u, v) –
isto é, a soma das capacidades dos arcos que atravessam de S até T . Existe uma propriedade importante
em redes de fluxos que é: o fluxo máximo de uma rede é igual à capacidade de algum corte dessa rede.
Pois bem, para a rede ilustrada anteriormente, encontre qual é esse corte.
13 Escreva um algoritmo (pseudocódigo) que calcule a capacidade de um corte num grafo capaci-
tado. Entrada: grafo capacitado G = (V, E) e um conjunto S de vértices, representado por meio de um
arranjo s[v] que é igual a 1 se v ∈ S, e deve devolver a capacidade do corte (S, V \ S).
3
14 Uma pequena oficina possui quatro diferentes tornos mecânicos e deve processar cinco peças
com esses tornos. Cada torno deverá realizar somente duas operações de usinagem de modo a otimizar
o tempo de conclusão dos trabalhos. Todavia as peças demandam 1,2 ou 3 operações. A figura abaixo
mostra quais tornos podem operar sobre as peças. Abaixo de cada peça é anotada a demanda de opera-
ções associada à peça. Como realizar o planejamento da distribuição dos tornos e das tarefas de forma
a atender a produção da oficiina?
Isomorfismo, planaridade
15 Para cada um dos pares de grafos G e H a seguir, determine se são isomorfos (mostrando uma
bijeção) ou não (indicando alguma invariante que é violada).
4
16 Construa dois grafos de 5 vértices e 8 arestas que não sejam isomorfos. Indique o raciocínio
utilizado na construção.
18 Utilize o teorema de Kuratowski para mostrar se os grafos a seguir são planares ou não.
5
Coloração de vértices
19 Escreva um algoritmo que receba um arranjo [c1 , · · · , cn ] com cores dos n vertices de um grafo
e determine se a coloração é válida ou não.
21 Execute os algoritmos DSATUR e Zykov no grafo de Petersen (se você não se recorda, é só pes-
quisar que grafo é esse, ele é bem conhecido).
24 Uma cobertura de vértices de um grafo G = (V, E) é um conjunto C ⊆ V de tal forma que, para
qualquer aresta (u, v) ∈ E, uma de suas extremidades está no conjunto C. Isto é, u ∈ C ou v ∈ C ou
u, v ∈ C. Veja um exemplo na figura abaixo.
6
Fonte: Goldbarg & Goldbarg (2012).
Encontre uma cobertura de vértices mínima (menor quantidade de vértices possível) para o grafo
de Petersen.
25 Uma cobertura de arestas de um grafo G = (V, E) é um conjunto C ⊆ E de tal forma que, para
qualquer vértice u ∈ V , u é incidente a alguma aresta (v, w) ∈ C. Veja um exemplo na figura abaixo.
Encontre uma cobertura de arestas mínima (menor quantidade de arestas possível) para o grafo de
Petersen.
7
Fonte: Goldbarg & Goldbarg (2012).