Otimização em Grafos e Digrafos - Definições, Buscas e Algoritmos

Otimização em Grafos Digrafos Bruno Masquio 2 Definições Básicas Digrafos Um digrafo é um par DVE V é um conjunto de vértices E é um conjunto de pares ordenados de vértices V 1 2 3 4 5 6 E 1 2 1 3 2 5 3 5 4 2 5 4 5 6 1 2 3 5 4 6 Digrafos A representação computacional é análoga à de grafos só que cada aresta é representada apenas uma vez 3 Buscas em Digrafos Buscas em ProfundidadeLargura 1 2 3 5 4 6 Usamse os mesmos algoritmos mostrados para grafos simples Analogamente às buscas em grafos simples também temos árvores florestas de Profundidade e de Largura Mas novos tipos de arestas surgem as arestas de avanço e de cruzamento As arestas são então arestas de árvore arestas de retorno arestas de avanço arestas de cruzamento Digrafos 4 Buscas em Digrafos Buscas em ProfundidadeLargura 1 2 3 5 4 6 Aresta vw aresta de árvore aresta de retorno w é ancestral de v aresta de avanço v é ancestral de w mas não pai de w aresta de cruzamento w não é descendente e nem ancestral de v Digrafos 5 Buscas em Digrafos Busca em Profundidade 1 2 3 5 4 6 Floresta de Profundidade do digrafo 2 5 3 4 1 6 Digrafos 6 Buscas em Digrafos Busca em Profundidade 1 2 3 5 4 6 2 5 3 4 1 2 5 3 4 1 6 6 Aresta de avanço Aresta de retorno Aresta de cruzamento Digrafos Floresta de Profundidade do digrafo 7 Digrafos Busca em Profundidade DFS MA dfsuv se u v escreveraresta de árvoreuv prev cpre para w 1 até n incl se Evw 1 se prew 0 dfsvw senão se posw0 escreverretorno v w senão se prev prew escreveravanço vw senão escrevercruzamento v w posv cpos pre 0 cpre 0 pos 0 cpos 0 para i 1 até n incl se prei 0 dfsii Digrafos Complexidade θn2 8 Buscas em Digrafos Busca em Profundidade 1 2 3 5 4 6 Digrafos 1 2 3 4 1 5 2 6 3 4 5 6 Valores de pre e pos 9 Grafos Busca em Digrafos EXS8 Mostrar a árvore de profundidade da busca começando em um vértice com a letra mais próxima de seu nome L W X R M K F B J Z Digrafos 10 Grafos DAG Digrafos Acíclicos 1 2 3 5 4 6 Em um digrafo acíclico existem pelo menos uma fonte vértice com graus de entrada 0 e um sumidouro vértice com grau de saída 0 BP em um DAG Não existem arestas de retorno Digrafos 11 Ordenação Topológica num DAG 1 2 3 5 4 6 Uma ordenação topológica é uma ordenação dos vértices tal que se vi vem antes de vj então não existe aresta de vj para vi 1 2 3 5 4 6 Corresponde a colocar os vértices em uma linha tal que todas as arestas estejam orientadas da esquerda para a direita Digrafos 12 Grafos Ordenação Topológica num DAG con DFS 1 2 3 5 4 6 Floresta de Profundidade do digrafo e ordem de saída da busca 5 4 2 6 1 3 1 3 2 4 5 6 1 2 3 4 5 6 ot 1 3 5 6 4 2 A idéia é numerar os vértices de acordo com a saída da busca em profundidade e considerar o reverso dessa numeração 1 2 3 4 5 6 Digrafos 13 1 2 3 5 4 6 6 5 3 4 2 1 Digrafos Ordenação Topológica num DAG 1 2 3 5 4 6 14 dfsuv marcar v para vizinhos w de v se w não marcado dfsvw ordenacaoTopologicacontadorInv v contadorInv contadorInv n desmarcar vértices para i 1 até n incl se i não marcado dfsii 1 2 3 5 4 6 6 5 3 4 2 1 Digrafos Ordenação Topológica num DAG 15 Ordenação Topológica num DAG Solução II 1 2 3 5 4 6 esvaziar q enfilar vértices com grau de entrada 0 enquanto Q não vazia v qfrente colocar v na ordenação para vizinhos w de v diminuir 1 do grau de entradaw se grau de entradaw 0 qenfilaw qdesenfila Uma ordenação topológica é uma ordenação dos vértices tal que se vi vem antes de vj então não existe aresta de vj para vi Digrafos 16 1 2 3 5 4 6 Demonstração da sequência de entrada na Fila v GE grau de entrada 1 0 2 3 2 2 1 0 3 1 0 4 1 1 1 0 5 1 1 0 6 1 1 1 0 Fila 1 3 5 4 6 2 Situação da Fila da Ordenação topológica 1 3 5 6 4 2 Digrafos Ordenação Topológica num DAG Solução II 17 1 2 3 5 4 6 Situação da Fila da Ordenação topológica 1 3 5 6 4 2 Digrafos Ordenação Topológica num DAG Solução II 0 3 1 1 1 1 1 Graus Entrada 1 2 3 4 5 6 Fila 0 2 0 1 1 1 1 3 0 2 0 1 0 1 1 3 5 0 1 0 0 0 0 1 3 5 4 6 0 0 0 0 0 0 1 3 5 4 6 2 0 0 0 0 0 0 1 3 5 4 6 2 0 0 0 0 0 0 1 3 5 4 6 2 18 Grafos Ordenação Topológica num DAG 1 2 3 5 4 EXS10 Mostrar uma ordenação topológica para o grafo abaixo usando as duas soluções 6 7 8 9 1 0 Digrafos 19 Digrafos Ordenação Topológica num DAG Caminho máximo em um DAG A partir da ordenação topológica podese obter o maior caminho em um DAG determinando de forma gulosa na ordem inversa da ordenação qual a distância máxima de cada vértice a um sumidouro do digrafo 1 3 5 4 2 6 Digrafos No digrafo acima da direita para a esquerda determinamos gulosamente as distâncias máximas de cada vértice a um sumidouro ot 1 3 5 4 2 6 Dm 4 3 2 1 0 0 20 Digrafos Ordenação Topológica num DAG maior caminho imprimeCaminho u ot1 escreveru repita u proxu escrever u enquanto proxu 1 ordTopuv marcar v para vizinhos w de v se w não marcado ordTopvw se Dmw1 Dmv Dmv Dmw1 proxv w otos v mc maxmc Dmv atualiza melhor caminho os n mc 0 desmarcar vértices Dm 0 prox 1 para i 1 até n incl se i não marcado ordTopii imprimeCaminho Digrafos Dmi maior caminho começando no vértice i proxi próximo vértice de i no maior caminho contendo i mc comprimento do maior caminho ot ordenação topológica os contador invertido da ordenação topológica Digrafos Ordenação Topológica num DAG Caminho máximo em um DAG 1 3 5 4 2 6 Digrafos ot 1 3 5 4 2 6 Dm 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 2 1 0 0 1 3 2 1 0 0 4 3 2 1 0 0 4 3 2 1 0 0 Após terminar a busca de 6 Após terminar a busca de 2 Após terminar a busca de 4 Após terminar a busca de 5 Após terminar a busca de 3 Após terminar a busca de 1 4 0 1 2 3 5 4 6 Digrafos Digrafos Ordenação Topológica num DAG maior caminho 2 0 0 1 1 3 0 5 012 6 0 3 4 1 23 Digrafos Ordenação Topológica num DAG 1 2 3 5 4 EXS11 Aplicar o algoritmo de determinação do maior caminho ao digrafo 6 7 8 9 1 0 Digrafos 24 Digrafos Ordenação Topológica num DAG Aplicação Dado um conjunto de caixotes todos de mesma altura e dimensões l x c determinar a pilha de maior altura colocando um caixote totalmente sobre o outro l c 1 5 4 2 8 3 3 9 5 4 7 1 5 10 4 6 12 5 7 6 6 8 4 3 Solução Criar um DAG representando as relações de sobreposição determinar uma ordenação topológica e encontrar o maior caminho no DAG a partir da ordenação de trás para frente Digrafos 25 Grafos Ordenação Topológica num DAG Aplicação Dado um conjunto de caixotes todos de mesma altura e dimensões l x c determinar a pilha de maior altura colocando um caixote totalmente sobre o outro l c 1 5 4 2 8 3 3 9 5 4 7 1 5 10 5 6 12 5 7 6 6 8 4 3 OrdenTop 6 7 5 3 2 1 4 8 1 2 3 5 4 6 7 8 Maior cam 5 3 4 3 2 2 1 1 Digrafos Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Há várias ferramentas para controle de projetos onde a rede de atividades é descrita por um DAG onde os vértices são as tarefas a serem realizadas as arestas as dependências entre as tarefas e para cada tarefa é dada sua duração O método CPM responde a várias perguntas do tipo a Qual a duração mínima do projeto b Quando cada tarefa deve ser iniciada para não atrasar o projeto Digrafos 1 4 2 6 5 7 3 5 0 2 5 3 3 4 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Para o DAG criado determinamse TMC tempos mais cedo TMT tempos mais tarde e F Folga É criado um vértice artificial com duração 0 para indicar o fim do projeto Digrafos Passo 1 Fazse a ordenação topológica 1 4 2 6 5 7 3 5 0 2 5 3 3 4 1 4 3 2 6 57 1 2 5 7 6 3 4 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Digrafos TMC tempos mais cedo para começar as atividades são calculados usando diretamente a ordenação topológica para os vértices v fonte TMCv 1 para os demais vértices v TMCv maxTMCz Cz para z dos quais v é vizinho Obs para os vértices sumidouros só há interesse em calcular tempos de término que devem ser considerados como um dia a menos que os de começo v TMC 1 4 2 6 5 7 3 5 0 2 5 3 3 4 1 1 4 13 4 3 13 4 2 13 4 6 max42 44 8 5 max42 44 45 9 7 max85 93 13 29 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Digrafos TMT tempos mais tarde para começar as atividades são calculados usando inversamente a ordenação topológica Para o vértices s sumidouro TMTs TMCs Para os demais vértices v TMTv minTMTz Cv para vizinhos z de v 0 1 1 4 2 6 5 7 3 2 5 3 3 4 5 4 9 13 4 8 4 v TMT 7 13 5 13310 6 1358 2 min10 82 6 3 min10 84 4 4 105 5 1 min6 4 5 3 1 30 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Digrafos As Folgas são dadas pelas diferenças entre os TMT e os TMC 110 1 4 2 6 5 7 3 0 2 5 3 3 4 5 451 9101 13130 462 880 440 31 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Digrafos O Caminho crítico é formado pelos vértices v com Folga 0 Neste projeto o caminho crítico é dado por 1 3 6 7 A duração mínima do projeto é 12 13 1 Obs O Caminho crítico é um subgrafo do digrafo original não necessariamente um caminho 110 1 4 2 6 5 7 3 0 2 5 3 3 4 5 451 9101 13130 462 880 440 32 Digrafos Ordenação Topológica num DAG Aplicação controle de projetos usando CPM Critical Path Method Digrafos O Caminho crítico é formado pelos vértices v com TMCv TMTv A folga é a diferença entre esses valores Neste projeto o caminho crítico é dado por 1 3 6 7 A duração mínima do projeto é 12 13 1 Obs O Caminho crítico é um subgrafo do digrafo original não necessariamente um caminho 110 1 4 2 6 5 7 3 0 2 5 3 3 4 5 451 9101 13130 462 880 440 33 Digrafos CPM preencheTMC para i 1n incl v oti TMCv 1 para z 1n incl se v é vizinho de z TMCv maxTMCv TMCzCz preencheTMT para i n1 incl v oti TMTv Infinito para z 1n incl se z é vizinho de v TMTv minTMTv TMTz se TMTv Infinito TMTv TMCv senão TMTv TMTvCv folgav TMTv TMCv ordTop preencheTMC preencheTMT escreveCaminhoMinimo Digrafos Digrafos Ordenação Topológica num DAG 1 3 2 EXS12 Mostrar em três etapas a determinação do Caminho Crítico na rede de atividades abaixo 6 4 7 5 Digrafos 4 3 0 2 4 5 7 35 Digrafos Componentes fortemente conexos 1 2 3 5 4 6 Conectividade em digrafos A conectividade em digrafos muda em relação a grafo simples porque não temos simetria No exemplo mostrado o vértice 1 alcança todos os demais e não é alcançado por nenhum deles Componentes fortemente conexos cfc Subdigrafos maximais tal que todos vértices de cada componente alcançam os demais vértices desse componente No digrafo do exemplo os 4 componentes fortemente conexos são 1 3 2 4 5 6 Há vários algoritmos lineares para se determinar os cfc Apresentaremos dois algoritmos Tarjan e Kosaraju Digrafos Alcançabilidade em digrafos 1 2 3 5 4 6 A potência p da matriz de adjacências mostra todos os caminhos de tamanho p 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 Matriz de Ajacências E Digrafos A Alcançabilidade em um digrafo é bem diferente daquela em grafos simples Um digrafo é fortemente conexo quando há caminhos de u para v e de v para u para qualquer par de vértices u v Alcançabilidade em digrafos 1 2 3 5 4 6 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 E2 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 E 1 2 3 5 4 6 Elevandose a matriz de adjacências à potência 2 obtemse um digrafo relativo aos caminhos de tamanho 2 Digrafos Alcançabilidade em digrafos 1 2 3 5 4 6 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 E2 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 E 1 2 3 5 4 6 Preenchendo a diagonal com 1s e elevandose a matriz de adjacências à potência 2 obtemse um digrafo relativo aos caminhos de tamanhos 1 e 2 Digrafos Fechamento transitivo em digrafos 1 2 3 5 4 6 O fechamento transitivo de um digrafo dá a alcançabilidade de todos os vértices Corresponde a elevar a matriz modificado à potência n 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 Digrafos 40 Fechamento transitivo representado do lado direito 1 2 3 5 4 6 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 1 Digrafos 1 2 3 5 4 6 41 1 2 3 5 4 6 O fechamento transitivo é equivalente a se adicionar todas as arestas entre vértices alcançáveis autoloops 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 1 Digrafos Fechamento transitivo em digrafos Um algoritmo com complexidade On3 Digrafos 1 2 3 5 4 6 k 1 k 2 Fechamento transitivo em digrafos para i 1 até n incl Ai i 1 para k 1 até n incl para i 1 até n incl se Ai k 1 para j 1 até n incl se Ak j 1 Ai j 1 Algoritmo de Warshall 43 Um algoritmo com complexidade On3 Digrafos 1 2 3 5 4 6 k 1 k 2 k 3 k 4 Fechamento transitivo em digrafos para i 1 até n incl Ai i 1 para k 1 até n incl para i 1 até n incl se Ai k 1 para j 1 até n incl se Ak j 1 Ai j 1 Algoritmo de Warshall 44 Um algoritmo com complexidade On3 Digrafos 1 2 3 5 4 6 k 1 k 2 k 3 k 4 k 5 k 6 Fechamento transitivo em digrafos para i 1 até n incl Ai i 1 para k 1 até n incl para i 1 até n incl se Ai k 1 para j 1 até n incl se Ak j 1 Ai j 1 Algoritmo de Warshall 1 2 3 5 4 6 Um algoritmo com complexidade On3 A cada passo do loop em k determina caminhos entre i e j que só utilizam vértices até o índice k excetuandose i e j Digrafos Fechamento transitivo em digrafos para i 1 até n incl Ai i 1 para k 1 até n incl para i 1 até n incl se Ai k 1 para j 1 até n incl se Ak j 1 Ai j 1 Algoritmo de Warshall 46 1 2 3 5 4 6 EXS9 Mostrar o digrafo do fechamento transitivo e a matriz do fechamento para o digrafo acima Digrafos Fechamento transitivo em digrafos Digrafos Componentes fortemente conexos 1 2 3 5 4 6 Algoritmo p determinação dos componentes forte conexos 1 BP determinação de low e pre e empilhamento 2 Retirada da pilha quando low pre Algoritmo de Tarjan Digrafos 1 2 3 5 4 6 7 low pre vis 0 esvaziar pilha cpre 0 para i 1 até n incl se prei 0 cfci Digrafos CFC Tarjan Digrafos Externamente cfcv prev cpre lowv cpre visv 1 qempilhav para vizinhos w de v se prew0 cfcw se visw1 lowv minlowv loww se lowv prev escrever Novo componente enquanto 1 p qfrente qdesempilha escreverp visp 0 se p v parar loop Digrafos CFC Tarjan 1 2 3 5 4 6 7 Digrafos Digrafos CFC Tarjan P L V P L V P L V P L V P L V P L V P L V v 1 1 1 1 2 1 1 1 2 2 1 3 1 1 1 2 2 1 3 3 1 4 1 1 1 2 2 1 3 3 1 4 4 1 4 1 1 1 2 2 1 3 3 1 4 2 1 3 1 1 1 2 2 1 3 2 1 4 2 1 2 1 1 1 2 2 0 3 2 0 4 2 0 5 1 1 1 5 5 1 6 1 1 1 5 5 1 6 6 1 7 1 1 1 5 5 1 6 6 1 7 7 1 1 2 3 5 4 6 7 Digrafos C14 3 2 Digrafos CFC Tarjan P L V P L V P L V P L V P L V P L V P L V 7 1 1 1 5 5 1 6 6 1 7 5 1 6 1 1 1 5 5 1 6 5 1 7 5 1 5 1 1 1 5 5 0 6 5 0 7 5 0 1 1 1 1 1 2 3 5 4 6 7 Digrafos C31 C27 6 5 Componentes1 2 3 4 5 6 7 52 Digrafos Componentes Fortemente Conexos 1 5 2 Exercício Aplicar o algoritmo de Tarjan ao digrafo abaixo 3 6 4 7 Digrafos Porque o algoritmo de Tarjan funciona Todos os vértices de um CGC são descendentes na árvore de profundidade do primeiro vértice v do componente que entra na busca Consequentemente todos os vértices w do componente terão loww lowv prev Se v tiver como descendentes apenas vértices do componente todos estarão na pilha no momento da saída de v na pilha e o componente será relatado corretamente Se v tiver apenas um outro componente como descendente cujo primeiro vértice a entrar na busca foi u então os vértices desse componente eentrarão na busca e na pilha imediatamente após u Quando u sair da busca os vértices correspondente também saem da pilha restando apenas os vértices do componente de v Portanto quando v sair da busca estarão na pilha apenas os vértices do componente E Assim sucessivamente Digrafos CFC Tarjan 1 2 3 5 4 6 7 Digrafos 54 Digrafos Componentes fortemente conexos 1 2 3 5 4 6 Esboço do algoritmo de Kosaraju 1 Ordenação Topológica no digrafo obtendo vetor ot 2 Busca em Profundidade no digrafo transpostoDT obedecendo a ordem de ot 3 Cada árvore de profundidade obtida é um cfc Algoritmo de Kosaraju Faz BP no digrafo e no digrafo transpostoO digrafo transposto é o digrafo original com todas as arestas invertidas Daí obtemse os componentes fortemente conexoscfc Digrafos 55 Grafos Componentes fortemente conexos 1 2 3 5 4 6 Obs ot é o resultado da ordenação topológica vetor de vértices com ordem inversa da saída na busca 2 5 4 6 3 1 1ª etapa OT no digrafo v 1 2 3 4 5 6 ot 1 3 2 5 6 4 Digrafos 56 Grafos Componentes fortemente conexos 1 3 5 4 6 3 2 6 4 5 2 2ª etapa BP no digrafo transposto seguindo a ordem de ot Componentes 1 3 2 4 5 6 Obs O digrafo transposto não precisa ser criado quando a representa ção é por matriz de adjacência Basta percorrer a coluna da matriz Digrafos v 1 2 3 4 5 6 ot 1 3 2 5 6 4 1 57 Grafos Componentes fortemente conexos otuv marcar v para vizinhos w de v se w não marcado otvw otos v bptuv desmarcar v escreverv para w vizinho de v no digrafo transposto se w marcado bptvw 1 2 3 5 4 6 Ord Top e BP no digrafo transposto Digrafos 58 Grafos Componentes fortemente conexos os n comp 0 desmarcar vértices para i 1 até n incl se i não marcado otii para i 1 até n incl se oti marcado escreverComponente comp bptotioti 1 2 3 5 4 6 Externamente Complexidade θnm ou θn2 Digrafos DT 59 Grafos Componentes fortemente conexos Para provar que o algoritmo é correto temos que provar que se os vértices r e s pertencem ao mesmo cfc em D então vão estar na mesma árv profund de DT Temos tb que provar o inverso ou seja se r e s estão na mesma árv profund de DT então pertencem ao mesmo cfc de D a Suponhamos r e s pertencentes a um mesmo cfc em D Suponhamos r o vértice com menor ordem de entrada na busca em DT Como existe o caminho de s a r em D então s será descendente de r nessa árvore b Suponhamos s e r na mesma árv prof de DT Seja t a raiz dessa árvore Então existe caminho de s para t em D Mas também tem que ter caminho de t para s pois t tem ordem de saida maior que s na busca em D Então s tem que ser descendente de t nessa árvore já que existe caminho de s a t Logo existe caminho de t para s em D Portanto t e s estão no mesmo cfc em D De forma análoga t e r estão no mesmo cfc em D Logo s e r estão no mesmo cfc em D 1 2 3 5 4 6 Porque o algoritmo de Kosaraju funciona Digrafos 60 Digrafos Componentes Fortemente Conexos 1 5 2 Exercício Aplicar o algoritmo de Kosaraju ao digrafo abaixo 3 6 4 7 Digrafos 61 Grafos Componentes Fortemente conexos Problema DOMINÓS Dado um grupo de dominós com a indicação de qual dominó é derrubado por um outro essas relações estão em um digrafo determinar o número mínimo de dominós que têm que ser empurrados à mão para que todo o conjunto caia Solução DOMINÓS Determinar cfc Criar DAG relativo aos cfc Determinar fontes no DAG 1 2 3 5 4 6 Digrafos 62 Grafos Componentes Fortemente conexos Problema MÃO DUPLA I Dado o mapa do trânsito de uma cidade representado como um digrafo onde os vértices são as esquinas e as arestas orientadas são os trechos de rua entre esquinas indicar se é possível atribuir mão dupla a alguns dos trechos de ruas de mão única tal que toda esquina seja atingível a partir de qualquer outra Solução MÃO DUPLA I Basta verificar se o grafo subjacente é conexo 1 2 3 5 4 6 Digrafos 63 Grafos Componentes Fortemente conexos Problema MÃO DUPLA II Dado o mapa do trânsito de uma cidade representado como um digrafo onde os vértices são as esquinas e as arestas orientadas são os trechos de rua entre esquinas indicar se é possível atribuir mão dupla a alguns dos trechos de ruas de mão única tal que toda esquina seja atingível a partir de qualquer outra Quando for indicar o número mínimo de trechos que devem ser colocados em mão dupla para conseguir isso Indicar também quais são esses trechos 1 2 3 5 4 6 Digrafos 64 PROBLEMA SATISFATIBILIDADE Problema Satisfatibilidade Dada uma expressão booleana E na forma normal conjuntiva E é satisfatível Expressão na forma normal conjuntiva Sejam e1en variávies booleanas Cada ei é denominado literal Uma cláusula é uma disjunção isto é uma expressão da forma e1 e2 ek só usa OU literais ei ou sua negação ei Uma expressão na forma normal conjuntiva é um conjunto de cláusulas ligadas por AND Ex E e1 e3 e1 e2 e3 Uma expressão E é satisfatível quando existe uma atribuição aos literais que torna a expressão verdadeira No exemplo dado E é satisfatível bastando fazer e1 V e2 V e3 F Satisfatibilidade NP Digrafos 65 PROBLEMAS 23SAT Problema 2SAT3SAT Dada uma expressão booleana E na forma normal conjuntiva onde cada cláusula tem exatamente 23 literais E é satisfatível 2SAT3SAT NP Certificado Uma atribuição de valores para os literais Os problemas são um caso particular de Satisfatibilidade Digrafos 66 Exercício Escrever uma fórmula na FNC com 2 variáveis booleanas que não seja satisfatível Digrafos 67 SUBCLASSES DE Satisfatibilidade TRATÁVEIS Algumas subclasses de Satisfatibilidade têm algoritmo polinomial 2SAT a expressão só contém cláusulas Krom ie com no máximo 2 literais HornSAT a expressão só contém cláusulas Horn ie com no máximo um literal positivo Subclasses triviais p ex cláusulas positivas ou negativas onde todos os literais são ou positivos ou negativos Digrafos 68 ALGORITMOS POLINOMIAIS PARA 2SAT Entrada Uma expressão C na 2FNC Decisão Existe uma atribuição que satisfaz C Métodos de Solução 1 Resolução de cláusulas reduz 2 cláusulas do tipo ab bc a ac 2 DPLL Backtracking fixase uma variável simplificase a fórmula e resolvese recursivamente o novo problema 3 Algoritmo Aspvall gera e analisa um digrafo Digrafos 69 ALGORITMO ASPVALL Entrada Uma expressão C na 2FNC Decisão Existe ma atribuição que satisfaz C 1 Criar um digrafo D correspondente à expressão Para cada literal dois vértices positivo e negativo Para cada cláusula duas arestas baseadas na seguinte identidade 2 Analisar se existe em D ciclo passando pelos 2 vértices de um mesmo literal Isso significa contradição entre as cláusulas Então basta verificar se os dois vértices de um mesmo literal estão na mesma componente fortemente conexa de D x y x y x y y x xyxyyx 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 Digrafos 70 ALGORITMO ASPVALL Exemplo C x y y z z x a b a b x a y b Grafo D de Implicações x y y z a a b b x z Digrafos 71 ALGORITMO ASPVALL Exemplo C x y y z z x a b a b x a y b Componentes Fortemente Conexos de D x y y z z a a b b x Conclusão C é satisfatível pois nenhum literal e sua negação estão no mesmo cfc Digrafos 72 Exercício Aplicar o algoritmo de Aspvall à seguinte fórmula C x y y z x z z y Digrafos 73 ALGORITMO ASPVALL ATRIBUIÇÃO Exemplo C x y y z z x a b a b x a y b Se fundirmos cada cfc obtemos um DAG D x y y z z a a b b x xyz a b a b xyz Digrafos 74 ALGORITMO ASPVALL ATRIBUIÇÃO Exemplo C x y y z z x a b a b x a y b Se fundirmos cada cfc obtemos um DAG D xyz a b a b xyz Atribuição 1 Fazer a ordenação topológica de D 2 Dada um literal x seja fx a posição de x na ordenação 3 Se fx fx Então atrx V Senão atrx F Digrafos 75 ALGORITMO ASPVALL ATRIBUIÇÃO Exemplo C x y y z z x a b a b x a y b Possíveis ordenações xyz a b a b xyz Possíveis atribuições Alternativa 1 xyz F a V b F Alternativa 2 xyz F a F b V 1 1 2 3 3 2 4 4 Digrafos Externamente gerar grafo low pre vis co 0 atr 1 esvaziar pilha cpre 0 nco 0 para i 1n incl se prei 0 k 1 para i 1n incl se coi coNegi k 0 se k1 escrever S Imprimir atr senão escrever N Digrafos ALGORITMO ASPVALL IMPLEMENTAÇÃO A implementação pode ser simplificada fazendo a determinação dos CFCs e a ordenação topológica simultâneamente pelo algoritmo de Tarjan Após a execução desse algoritmo é que se testa se houve conflito ou não Negi é uma função que retorna o número do vértice correpondente à negação de i CFCOT v prev cpre lowv cpre visv 1 PUSHv para vizinhos w de v se prew0 CFCOTw se visw1 lowv minlowv loww se lowv prev nco enquanto 1 p POP visp 0 cop nco se atrNegp 1 atrp 1 senão atrp 0 se p v parar loop Digrafos ALGORITMO ASPVALL IMPLEMENTAÇÃO 78 Exercício Indicar as atribuições possíveis de satisfatibilidade da seguinte fórmula C x y y z x z z y Digrafos 79 Problema 10319 Manhattan Descrição Dado um grid s ruas x a avenidas e dados m pares de pontos querse saber se é possível orientar as direções do trânsito em mão única para que haja sempre um caminho simples para os m pares de pontos dados Solução criar uma expressão 2FNC para a situação e usar o algoritmo de 2SAT para verificar se a expressão é satisfatível As cláusulas a serem criadas para cada um dos m pares s1 a1 s2 a2 dados são as seguintes a se o trajeto não é reto criar o trajeto ciassociando a ci uma atribuição para s e para a de acordo com o trajeto a ser feito 1 para a direita 0 para a esquerda 1 pcima 0 pbaixo Para essa condição criar a cláusula ci ou ci criar 2 vértices v e w v e colocar a aresta w v Digrafos 80 Problema 10319 Manhattan Descrição Dado um grid s ruas x a avenidas e dados m pares de pontos querse saber se é possível orientar as direções do trânsito em mão única para que haja sempre um caminho simples para os m pares de pontos dados Solução b caso contrário criar duas condições cj e ck uma para cada percurso possível associando a cjk uma atribuição para s e para a como no caso anterior Criar dois vértices para cada condição v w v p qp e criar a cláusula cj ou ck colocando no grafo as arestas w v e q p c verificar para cada condição se há alguma incompatibilidade com condições já criadas anteriormente incompatibilidade entre ci e cj criar a cláusula cj ou ck e duas arestas no grafo correspondentes Finalmente rodar CFC do digrafo e verificar se há vértice e sua negação no mesmo CFC Entrada 7 7 4 1 1 1 6 6 1 6 6 6 6 1 1 4 3 5 1 Cond s vs a va clausulas c1 1 1 0 1 c1 ou c1 c2 6 1 0 1 c2 ou c2 c3 6 0 1 0 c4 1 0 6 0 c3 ou c4 c3 ou c2c4 ou c1 c5 4 0 1 1 c6 5 0 4 1 c5 ou c6 Digrafos 81 Problema 10319 Manhattan Descrição Dado um grid s ruas x a avenidas e dados m pares de pontos querse saber se é possível orientar as direções do trânsito em mão única para que haja sempre um caminho simples para os m pares de pontos dados Solução Entrada 7 7 4 1 1 1 6 6 1 6 6 6 6 1 1 4 3 5 1 c3 c3 c4 c5 c6 c1 c2 c1 c2 x c5 c6 Saída No c1 e c1 estão nomesmo CFC Cond s vs a va clausulas c1 1 1 0 1 c1 ou c1 c2 6 1 0 1 c2 ou c2 c3 6 0 1 0 c4 1 0 6 0 c3 ou c4 c3 ou c2c4 ou c1 c5 4 0 1 1 c6 5 0 4 1 c5 ou c6 Digrafos 82 Problema Banquete 11294 Wedding Descrição Querse arrumar n casais em uma mesa de banquete com o casal anfitrião na posição 1 os casais sentados um em frente ao outro São dados m pares de inimigos diferentes sexos ou não Do lado da mesa onde está o anfitrião não pode haver nenhum par de inimigos Indicar como a distribuição deve ser feita Solução Entrada 10 6 dez casais 6 pares de inimigos anfitrião 0 3h 7h 5w 3w 7h 6w 8w 3w 7h 3w 2w 5h Saída 1h 2h 3w 4h 5h 6h 7h 8h 9h Digrafos 83 Problema Banquete Exemplo Exemplo 3 2 1h 2w 1h 2h a o anfitrião sentase na posição 1 e as expressões referemse q quem senta do seu lado na mesa b Variáveis a homem do casal 1 sentase do mesmo lado do anfitrião b mulher do casal 1 sentase do mesmo lado do anfitrião c homem do casal 2 sentase do mesmo lado do anfitrião d mulher do casal 2 sentase do mesmo lado do anfitrião c Éxpressão que obriga cada componente do casal sentarse em lados opostos a ba bc dc d d Expressão que proibe dois inimigos sentaremse do lado do anfitrião a ca d e Expresfinala ba bc dc da ca d Digrafos 84 Problema Banquete Exemplo e Expresfinala ba bc dc da ca d Digrafos a a b b c d d c Componentes ua b vdc wc d xb a 85 Problema Banquete Exemplo Expresfinala ba bc dc da c a d Possíveis ordenações ab c d c d ab Possíveis atribuições Alternativa 1 a F b V c F d V Alternativa 2 a F b V c V d F 1 1 2 3 3 2 4 4 Digrafos 86 Problema 2886 Xmart Descrição Um supermercado quer reduzir os produtos através de uma pesquisa junto aos clientes Eles indicam 2 produtos para ficarem e dois para sairem Dados os votos querse saber se é possível satisfazer a todos os clientes um produto escolhido para ficar fica e um para sair sai Solução Entrada 4 4 clientes e produtos 1 2 3 4 3 4 1 0 1 3 2 4 2 4 0 3 Saída n Digrafos 87 httpsleetcodecomproblemscourseschedule httpsleetcodecomproblemscoursescheduleii httpsleetcodecomproblemslargestcolorvalueinadirectedgraph httpsleetcodecomproblemsmaximumemployeestobeinvitedtoameeting Exercícios Digrafos FIM