Notas de Aula - Teoria dos Grafos

Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Notas de aula da disciplina Teoria dos Grafos Esse material é um compilado dos seguintes Sedgewick R Algorithms in C part 5 graph algorithms 3rd ed AddisonWesley 2002 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics Springer New York 2008 Lintzmayer C N Mota G O Notas de aulas Análise de algoritmos e estruturas de dados Em construção 11 Aula 15 componentes fortemente conexas Em um grafo se há uvcaminho então há vucaminho Em um DAG se há uvcaminho então não há vucaminho Em um digrafo qualquer tudo pode acontecer Porém dentro de uma componente fortemente conexa se há uvcaminho então há vucaminho Algoritmos clássicos famosos que detectam componentes fortemente conexas Tarjan inventado em 1972 tempo OV E Kosajaru inventado em 1980 tempo OV E Gabow inventado em 1999 tempo OV E 0 1 2 3 4 5 6 7 8 9 10 11 12 111 Algoritmo de Kosajaru Seja D um digrafo e sejam D1 Dk todas as componentes fortemente conexas de D cada Di é um subdigrafo portanto Cada vértice de D pertence somente a uma componente e entre quaisquer duas componentes Di e Dj existem arcos em apenas uma direção pois caso contrário a união de Di com Dj formaria uma componente maior contendo Di e Dj Então sempre existe pelo menos uma componente Di que é um ralo não existe arco saindo de Di em direção a nenhuma outra componente Intuição começar uma busca em uma tal componente vai encontrar apenas os vértices dela 68 O algoritmo de Kosajaru tem essencialmente dois passos 1 Execute uma DFS sobre D e seja S v1 vn uma ordenação dos n vértices de D de forma decrescente de posordem 2 Execute uma DFS sobre D usando S para percorrer os vértices 1 Função KosajaruD 2 Para cada v V D faça 3 visitadov 0 4 predv 1 5 preordemv 1 6 posordemv 1 7 tempo 0 8 Para cada v V D faça 9 Se visitadov 0 então 10 DFS D s 11 seja v1 vn uma ordenação decrescente dos vértices por posordem 12 Para cada v V D faça 13 visitadov 0 14 predv 1 15 compv 1 16 ncomp 0 17 Para i 1 até n faça 18 Se visitadovi 0 então 19 compvi ncomp 20 DFS2D vi Alterar para atualizar comp 21 ncomp ncomp 1 1 Função DFS2D s 2 visitados 1 3 Para cada v N s faça 4 Se visitadov 0 então 5 predv s 6 compv comps 7 DFS2D v Claramente o algoritmo de Kosajaru leva tempo OV E pois é basicamente o tempo de realizar duas chamadas à DFS e construir D 69 Teorema 111 Seja D um digrafo Ao fim da execução de KosajaruD temos que para quaisquer u v V D os vértices u e v estão na mesma componente fortemente conexa se e somente se compu compv Demonstração Seja vi um vértice arbitrário de D para o qual a linha 20 foi executada e seja Di a componente fortemente conexa de D que contém vi Para provarmos o resultado do teorema note que basta mostrarmos que após a chamada a DFSD vi na linha 20 vale o seguinte v V D é visitado durante DFSD vi se e somente se v V Di 2 De fato se 2 é válida então após a execução de DFSD vi teremos que os únicos vértices com compv compvi são os vértices que estão em Di Assim podemos refrasear o enunciado do teorema para dois vértices estão na componente fortemente conexa Di se e somente se eles são visitados durante uma chamada DFSD vi Como o algoritmo KosajaruD só encerra sua execução quando todos os vértices são visitados provar 2 é suficiente para concluir o resultado do teorema Para provarmos 2 vamos primeiro mostrar a seguinte afirmação Afirmação 112 Se v V Di então v é visitado na chamada DFSD vi Demonstração Seja v V Di Como v está na mesma componente fortemente conexa de vi então existe um vivcaminho e um vvicaminho em D Se v já tivesse sido visitado no momento em que DFSD vi começa então como existe vvicaminho certamente o vértice vi seria visitado de modo que a chamada a DFSD vi nunca seria executada levando a um absurdo Portanto sabemos no início da execução de DFSD vi o vértice v ainda não foi visitado Logo como existe um vivcaminho o vértice v é visitado durante essa chamada Para completar a prova resta mostrar a seguinte afirmação Afirmação 113 Se v é visitado na chamada DFSD vi então v V Di Demonstração Seja v V D um vértice que foi visitado durante a chamada DFSD vi Então existe um vivcaminho em D e resta mostrar que existe um vvicaminho em D Como o laço para da linha 17 visita os vértices por ordem decrescente de posordem e como v foi visitado durante a chamada DFSD vi isso significa 70 que posordemu posordemv Portanto durante as chamadas de DFS sobre D vale que a chamada DFS D v termina antes do fim da execução de DFS D vi 3 Considere o momento do início da execução de DFS D vi Como existe vvicaminho em D pois existe vivcaminho em D sabemos que DFS D vi não pode ter sido iniciada após o término da execução de DFS D v pois nesse caso vi teria sido visitado durante a execução de DFS D v e por conseguinte DFS D v terminaria depois do fim da execução de DFS D u contrariando 3 Assim a chamada DFS D vi teve início antes de DFS D v e por 3 terminou depois do fim de DFS D v o que significa que existe um vivcaminho em D Portanto existe um vvicaminho em D 112 Algoritmo de Tarjan Seja D um digrafo e sejam D1 Dk todas as componentes fortemente conexas de D cada Di é um subdigrafo portanto Observe que em uma árvore de DFS uma componente fortemente conexa vai apa recer como uma subárvore Além disso não vai haver aresta de retorno de uma Di para uma Dj pode haver arestas de cruzamento ou de descida Intuição basta encontrar a raiz dessas subárvores Vamos manter qual é a menor ordem de um vértice que pode ser atingido por uma aresta de retorno com um extremo na subárvore enraizada em u em lowu Assim se lowu preordemu então não há aresta de um descendente de u para um ancestral de u e portanto u é raiz de uma componente fortemente conexa Vamos também manter uma pilha que irá armazenar os vértices que vão sendo alcançados mas que ainda não foram atribuídos a uma componente Claramente o algoritmo de Tarjan leva tempo OV E pois é basicamente o tempo de uma chamada à DFS note que leva tempo OV para desempilhar todos os vértices da pilha 71 1 Função TarjanD 2 Para cada v V D faça 3 predv preordemv compv lowv 1 4 visitadov estanapilha 0 5 tempo 0 6 seja P uma pilha vazia 7 ncomp 0 8 Para cada s V D faça 9 Se visitados 0 então 10 AuxTarjanD s 1 Função AuxTarjanD s 2 visitados 1 3 tempo tempo 1 4 preordems lows tempo 5 EmpilhaP s 6 estanapilhas 1 7 Para v N s faça 8 Se visitadov 0 então 9 predv s 10 AuxTarjanD v 11 Se lowv lows então 12 lows lowv 13 Senão Se estanapilhav 1 e lowv lows então 14 lows lowv 15 Se lows preordems então 16 faça 17 u DesempilhaP 18 estanapilhau 0 19 compu ncomp 20 Enquanto u s 21 ncomp ncomp 1 72