Grafos-P3

Prévia do material em texto

POR FAVOR: 
PERGUNTAS EM NEGRITO 
RESPOSTAS SEM NEGRITO 
PARA FACILITAR A VISUALIZAÇÃO 
 
Prova vespertino 
 
1 - Mostre que K5-e é planar tal que e pertence a E(G). Mostre Ψe. 
 
2 - Considere o seguinte problema. Existem x homens e y mulheres. Um homem só pode dançar com uma 
mulher de altura menor q a sua. Apresente um tipo de grafo para solucionar tal problema e uma solução 
para maximar o número de pares de dança formados. 
 
3 - Mostre quando um clique é uma cobertura. Justifique. 
 
4 - Considere um grafo k-regular, com k>0, mostre X(G), considerando diferentes topologias. Justifique. 
 
5 - Não lembro o grafo corretamente, mas acho que era assim: 
V(g) = {s, v2, v3, v4, v5, t}, com s fonte e t como sorvedouro 
E(g) = {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15} 
P(e1) = {s, v2}, P(e2) = {s, v3}, P(e3) = {s, v4}, P(e4) = {s, v5}, P(e5) = {s, t} 
P(e6) = {v2, v3}, P(e7) = {v2, v4}, P(e8) ={v2, v5}, P(e9) = {v2, t} 
P(e10) = {v3, v4}, P(e11) = {v3, v5}, P(e12) = {v3, t} 
P(e13) = {v4, v5}, P(e14) = {v4, t} 
P(e15) = {v5, t} 
 
Os valores estou supondo, pois não lembro todos corretamente 
C(e1) = 2, C(e2) = 3, C(e3) = 3, C(e4) = 2, C(e5) = 4 
C(e6) = 3, C(e7) = 4, C(e8) = 2, C(e9) = 2 
C(e10) = 3, C(e11) = 2, C(e12) = 5 
C(e13) = 3, C(e14) = 4 
C(e15) = 3 
 
Apresentar uma solução de fluxo máximo e uma de corte minimo e justificar. 
 
Aula 20: Fluxo Máximo e Corte Mínimo 
https://docs.google.com/viewer?a=v&q=cache:ULI8cCw1H3IJ:www.dct.ufms.br/~marco/analise2007/aula2122
_4.pdf+&hl=pt­BR&gl=br&pid=bl&srcid=ADGEESjZkvW7cZGoh97gLd1u8jsLG3v7­pjN7iD5GXQ1l7Z­fmMNWgo
do1OBwXTyM9J9n_wNS5fjfd6akzLgYZTzgkBVCelJaaE0Sasa8kPvKhPIz4c_EGjzF8sxDklqqgnfv3JGD­U2&sig
=AHIEtbQqEWMxMgI1DqOJVv­YGoe2QHYT4Q 
 
Algoritmo 1: Fluxo Máximo 
Entrada: Rede capacitada ℂ=(C, s, t), C=(G, c(e)), G=(V(G),E(G),PG(e)). 
Saída: Fluxo w. 
Auxiliares: Aresta e, resíduo r, caminho P. 
para toda e ∈ E(G) faça 
w(e) ← 0 
enquanto ExisteCaminhoAumento( ℂ, w ) faça 
P ← CaminhoAumento( ℂ, w ) 
r ← CapacidadeResidual( ℂ, P, w ) 
para toda e ∈ P(G) faça 
se SentidoParalelo( P, G, e ) então faça 
w(e) ← w(e) + r 
senão faça 
w(e) ← w(e) ­​ r  
retorne w 
 
No Algoritmo 1, as funções têm o seguinte significado: 
ExisteCaminhoAumento( ℂ, w ): Retorna verdadeiro se existe um caminho de aumento em ℂ 
baseado no fluxo w. 
CaminhoAumento( ℂ, w ): Retorna um 
CapacidadeResidual( ℂ, P, w ): Retorna a capacidade residual do caminho de aumento P. 
SentidoParalelo( P, G, e ): Retorna verdadeiro se a aresta e percorrido em P em relação à sua 
orientação em G. 
 
1. Baseado no resultado do Algoritmo 1, como seria possível conseguir o valor do fluxo máximo? 
Via Wikipédia:  
Resposta humana: o valor do fluxo máximo pode ser encontrado através da soma dos fluxos originários da 
origem s da rede. 
 
2. Baseado no resultado do Algoritmo 1, como seria possível conseguir um corte mínimo? 
 
 
Algorítimo de Ford­Fulkerson [http://pt.wikipedia.org/wiki/Algoritmo_de_Ford­Fulkerson] 
O algoritmo de Ford­Fulkerson calcula o fluxo máximo numa rede de fluxos. 
Funciona pela definição de um caminho de aumento de fluxo num grafo. Ao acrescentarmos o caminho de aumento ao fluxo 
já existente no grafo, o fluxo máximo é atingido quando não for possível descobrir mais caminhos de aumento. Contudo, não 
há qualquer certeza que se chegue a esta situação – o mais que se pode garantir é que a resposta estará correcta se o 
algoritmo terminar. No caso de este algoritmo manter­se com iterações sucessivas ad infinitum, o fluxo poderá nunca 
convergir para um fluxo máximo. Todavia, esta situação ocorre apenas para valores de fluxo irracionais. 
 
função Ford-Fulkerson(G, s, t) 
 para cada (u, v) em E[G] 
 fluxo(u, v) := 0 
 fluxo(v, u) := 0 
 enquanto existir caminho de aumento p de s para t na rede residual 
 Cf(p) := capacidade do arco de menor capacidade em p 
 para cada (u, v) em p 
 fluxo(u, v) := fluxo(u, v) + Cf(p) 
 fluxo(v, u) := -fluxo(u, v) 
 faça a rede residual Gf(Vf,Ef), em que Cf(u,v) := c(u,v) - fluxo(u,v) 
 
Em cada iteração buscamos um caminho por onde podemos passar fluxo. Passamos o fluxo por aí e montamos uma rede 
residual (que, de forma também simplificada, é uma rede equivalente à original com aquele caminho revertido). O que muda 
nos diversos algoritmos que se baseiam no Método de Ford­Fulkerson é o modo de achar o "augmenting path". A idéia é 
fazer uma busca no subgrafo de G formado pelas arestas onde f(u,v) < c(u,v). O algoritmo usando DFS tem complexidade 
O(E.maxflow), o algoritmo usando BFS (conhecido como Algoritmo de Edmonds­Karp) tem complexidade O(V E^2). Outra 
alternativa é usar o PFS (Priority First Search), que busca os caminhos com maior capacidade. 
 
 
 
 
Aula 22: Coloração de Vértices 
Algoritmo 1: Heurística gulosa para a coloração de vértices. 
Entrada: Um grafo G=(V(G),E(G),ΨG (e)). 
Saída: Uma coloração num vetor κ. 
Auxiliares: Vértices v, v', vetor c 
SetaVetor(K, 0) 
para todo v ∈ V(G) faça 
SetaVetor(c, 'disponivel') 
c[0] ← 'indisponivel' 
para todo v' ∈ ΓG(v) faça 
c[κ[v']] ← 'indisponivel' 
κ[v] ← MenorCorDisponivel( c ) 
retorne K 
 
1. Prove que se H é um subgrafo de G então χ(H)≤ χ(G). 
(um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G 
e o conjunto de arestas é um subconjunto do conjunto de arestas de G. A quantidade de cores está restrita à 
quantidade de vértices e arestas do grafo G, e as relações de adjacência envolvidas. Como H é subconjunto 
de G, então o menor número de cores estará limitado à quantidade admitida em G.) 
 
2. Prove que χ(Kn) = n.  
(pode usar o argumento que todo vértice é vizinho de todos os outros, a vizinhança tem comprimento (n­1), 
dai tu precisa de n­1 cores e contando a do próprio vértice n) 
 
3. Descubra três classes de grafos para as quais a heurística gulosa retorna a coloração com o 
mínimo de cores. 
Grafo em forma de caminho, Completo e Conexo sem ciclo (não sei se está certo) 
 
 
 
Aula 23: Coloração de Arestas e Coloração Total 
1. Prove que se H é um subgrafo de G então χ'(H)≤ χ'(G). 
(um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G 
e o conjunto de arestas é um subconjunto do conjunto de arestas de G. A quantidade de cores está restrita à 
quantidade de vértices e arestas do grafo G, e as relações de adjacência envolvidas. Como H é subconjunto 
de G, então o menor número de cores estará limitado à quantidade admitida em G.) acredito ser o mesmo 
principio, mas confirmem 
 
2. Descreva um método para colorir as arestas um grafo Kn com o mínimo de cores. 
 
3. Descubra três classes de grafos para as quais a heurística gulosa retorna a coloração com o 
mínimo de cores. 
Algoritmo 1: Heurística gulosa para a coloração de vértices. 
Entrada: Um grafo G=(V(G),E(G),ΨG (e)). 
Saída: Uma coloração num vetor κ. 
Auxiliares: Vértices v, v', vetor c 
SetaVetor(K, 0) 
para todo v ∈ V(G) faça 
SetaVetor(c, 'disponivel') 
c[0] ← 'indisponivel' 
para todo v' ∈ ΓG(v) faça 
c[κ[v']] ← 'indisponivel' 
κ[v] ← MenorCorDisponivel( c ) 
retorne K 
pq esse algoritmo tá aki? 
a. Classe de Grafos de Árvore (isso pode ser uma classe? alguém confirma?) 
 
 
4. Descubra o número mínimo de cores para a coloração total dos grafos K2, K3, K4 e K5. Justifique. 
 
Aula 24: Conjuntos Estáveis, Cliques, Coberturas 
1. Verifique qual é o maior conjunto, maior clique e menor cobertura para: 
1. Um grafo formado por um ciclo ímpar. 
2. Um grafo formado por um ciclo par. 
3. O grafo de Petersen. 
 
Aula 25: Emparelhamentos 
1. Prove que um grafo bipartido possui em emparelhamento perfeito se e somente se |Γ(V'(G))| >                               
|V'(G)| para qualquer V'(G) ⊂ V(G). [este simboloΓ(V’(G)) denota conjunto de vertices adjacentes /                             
vizinhança] 
 
2. Mostre que para um grafo não bipartido a afirmação acima não é válida. 
 
3. Mostre que todo n­cubo possui um emparelhamento completo. 
 
Aula 26: Grafos Planares 
 
1. Prove o Teorema 2: O grafo K3,3 não é planar. 
 
 
 
k3,3  k2,2 
 
Como qualquer grafo bipartido completo Kn,n , com n ∈ N e sendo n>2 , existe sempre um cruzamento entre                                       
as arestas. Para que um grafo seja planar, então não pode haver este cruzamento. 
 
2. Prove os Lemas 1 e 2. 
Lema 1: Se G não é planar, então H ⊃ G também não é planar. 
Lema 2: Se G é planar, então H ⊂ G também é planar. 
 
3. Prove que o grafo de Petersen não é planar. 
4. Mostre que K3,3 – e é planar para qualquer e ∈ E(K3,3). Defina também o valor de φ(K3,3 – e). 
 
 
Aula 27: Lista de Exercícios para Revisão 3 
 
1. Seja a rede capacitada, composta pelo grafo abaixo, juntamente com as capacidades das arestas,                             
sendo s o vértice fonte e t o sorvedouro. Desenhe o grafo indicando uma possível solução de fluxo                                   
máximo e uma solução de corte mínimo. 
ℂ=(C,s,t); C=(G, c(e)); 
G=(V(G),E(G),PG(e)); 
V(G)={s, v2, v3, v4, v5, t}; 
E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15}; 
PG(e1)=(s, v2); PG(e2)=(s, v3); PG(e3)=(s, v4); PG(e4)=(s, v5); 
PG(e5)=(s, t); PG(e6)=(v2, v3); PG(e7)=(v2, v4); PG(e8)=(v2, v5); 
PG(e9)=(v2, t); PG(e10)=(v3, v4); PG(e11)=(v3, v5); PG(e12)=(v3, t); 
PG(e13)=(v4, v5); PG(e14)=(v4, t); PG(e15)=(v5, t); 
c(e1)=2; c(e2)=3; c(e3)=3; c(e4)=2; c(e5)=4; c(e6)=3; c(e7)=4; c(e8)=3; 
c(e9)=2; c(e10)=5; c(e11)=3; c(e12)=2; c(e13)=3; c(e14)=4; c(e15)=2; 
 
bw(t) = 13    ­ alguem mais achou esse valor??? 
 
 
2. Uma indústria precisa armazenar um certo conjunto de reagentes químicos. Por razões de                           
segurança, alguns reagentes não devem ficar num mesmo compartimento do armazém. Como você                         
modelaria este problema utilizando grafos? Qual seria o número mínimo de compartimentos para                         
armazenar os reagentes? Justifique. 
 
 
 
3. Verifique se χ(G) > Δ(G) para todo grafo G. 
 
4. Defina uma relação entre χ(G) e χ''(G). Justifique. 
 
5. Defina uma relação entre χ'(G) e χ''(G). Justifique. 
 
6. Mostre que toda floresta é um grafo planar. 
Mostra que uma árvore (conexa e sem ciclos), pode ser representada na curva de Jordan (contém uma única                                   
face), dai tu fala que uma Floresta contém o conjunto A1, A2, A3, ... , An , sendo árvores e que cada uma está                                               
em uma curva de Jordan, logo a floresta é planar. 
 
7. Verifique se todo grafo k­regular possui um emparelhamento perfeito. 
 
8. Mostre que um emparelhamento perfeito possui um número par de vértices. 
 
9. Mostre que o problema de coloração de arestas pode ser reduzido para o problema de coloração                                 
de vértices. 
 
10. Mostre que o problema de coloração total de grafos pode ser reduzido para o problema de                                 
coloração de vértices. 
 
11. Verifique se em um ciclo todo emparelhamento maximal é máximo. E em uma árvore? 
Resolvido por Begot ( minha idéia ) : Para um ciclo, como qualquer início do emparelhamento é igual, definir                                       
um grafo com ciclo par e impar e e para cada um mostrar que iniciando de qualquer aresta o seu                                       
emparelhamento não irá poder mais expandir, e como ele é um ciclo não importa da onde começar e então vc                                       
prova que em ciclos todo emparelhamento máximal é máximo. 
 
Na arvore, eu fiz por construção, iniciei com uma uma árvore trivial, só a raiz, e fui adicionando um vertice e                                         
aresta de cada vez na raiz, na primera adição, vc só tem uma aresta, logo é faicl mostrar que ela é maxima,                                           
maximal e completa, na adição do segundo vertice, por ter duas aretas, ainda é facil mostrar que as duas                                     
opções de emparelhamento são iguais e o maximal é o máximo, na adição do terceiro vertice, podemos                                 
encontrar dois possíveis emparelhamentos e mostrar que um deles não é máximo apesar de ser maximal. A                                 
construção foi feita fazendo uma árvore do tipo q é feito um só caminho da raiz até sua folha.  
 
12. Relacione o número de faces de um grafo com o seu número de ciclos. Justifique. 
 
13. Defina sobre quais condições um conjunto estável é um clique. Justifique. 
 
14. Defina sobre quais condições um conjunto estável é uma cobertura. Justifique. 
 
15. Defina sobre quais condições uma clique é uma cobertura. Justifique.