1. LEMA: a adaptação abaixo do algoritmo de busca em profundidade para a detecção de CICLOS em grafos NÃO-DIRECIONADOS executa em tempo O(n). -------------------------------------------------- ALGORITMO: tem_ciclo ENTRADA: grafo NÃO-DIRECIONADO G SAÍDA: booleano -------------------------------- 01. para cada v \in V[G] 02. | cor[v] := branco // não atingido 03. para cada v \in V[G] 04. | se cor[v] = branco 05. | | se tem_ciclo_rec(G,v,cor) 06. | | | retorne verdadeiro 07. retorne falso -------------------------------------------------- -------------------------------------------------- ALGORITMO: tem_ciclo_rec ENTRADA: grafo NÃO-DIRECIONADO G, vértice u de G, informação "cor" para cada vértice de G. SAÍDA: booleano -------------------------------- 01. cor[u] := cinza // "descendência" em percurso 02. num_cinzas := 0 03. para cada v \in N(u) 04. | se cor[v] = cinza // logo, u tem pai! 05. | | se num_cinzas = 1 06. | | retorne verdadeiro 07. | | num_cinzas := 1 08. | senão 09. | | se tem_ciclo_rec(G,v,cor) 10. | | | retorne verdadeiro 11. cor[v] := preto // "descendência" percorrida 12. retorne falso -------------------------------------------------- ================================================== ------------------ PROVA LEMA 1 ------------------ Primeiramente recapitule que, exceto pelas instruções do laço da linha 3 da função "tem_ciclo_rec", todas as demais instruções executam em tempo total O(n), pois: ---------- 1. As instruções da função "tem_ciclo" custam Teta(n) (não incluído o custo das chamadas recursivas). 2. Há no máximo "n" chamadas à função "tem_ciclo_rec", o que implica que o custo total das linhas 1, 2, 11 e 12 da função "tem_ciclo_rec" é O(n). ---------- Resta, então, calcular o custo das iterações do laço em questão, levando-se em consideração todas as chamadas à função "tem_ciclo_rec". Observe então que, em cada iteração do laço em questão, uma chamada recursiva ao vizinho "v" é realizada se e somente se o vértice "v" em questão é branco (embora isso não esteja explícito no código do algoritmo, esse é o caso, pois um vértice "u" não pode estar tendo a sua vizinhança percorrida e ao mesmo tempo já ter um vizinho preto (pois, nesse caso, "u" já deveria ter sido pintado de preto também); logo, todo vizinho "v" de "u" que não é cinza é branco, e portanto para "v" ocorre uma chamada recursiva da função "tem_ciclo_rec"). Logo, nós podemos associar cada iteração do laço em questão a uma chamada à função "tem_ciclo_rec": ---------- 1. Se o vértice "v" da iteração em questão está cinza, então ou há um retorno de verdadeiro ou há uma atribuição à variável "num_cinzas"; em todo caso, nós associamos a iteração à chamada em questão, isto é, à chamada "tem_ciclo_rec(G,u,cor)". 2. Se o vértice "v" não está cinza, então ele está branco e então nós associamos a iteração à chamada recursiva "tem_ciclo_rec(G,v,cor)". ---------- Observe, que para cada chamada "tem_ciclo_rec(G,x,cor)", há no máximo duas iterações do tipo 1 associadas a essa chamada, pois no máximo em 1 iteração do laço dessa chamada há um retorno de verdadeiro, e no máximo em 1 iteração do laço dessa chamada há uma atribuição à variável "num_cinzas" (já que a descoberta de um segundo vizinho cinza leva ao retorno de "verdadeiro"). De forma semelhante, para cada chamada "tem_ciclo_rec(G,x,cor)", há no máximo 1 iteração do tipo 2 a ela associada, pois a função "tem_ciclo_rec" é chamada no máximo 1 vez para cada vértice do grafo. Logo, como há no máximo "n" chamadas à função "tem_ciclo_rec", então, durante toda a execução do algoritmo de detecção de ciclos em questão, há no máximo 3*n = O(n) iterações do laço da função "tem_ciclo_rec", o que completa a prova, CQD. ------------------ PROVA LEMA 1 ------------------ ==================================================