ALLgoritmos - Tudo sobre Algoritmos e Programação

Microsoft vs Google, a guerra dos buscadores continua

2009-11-18T01:01:00.002-03:00

Novo buscador da Microsoft, o Bing, aumentou a sua fatia no mercado de busca Norte-Americano em outubro, com crescimento de 0,5% o Bing está muito próximo dos 10% segundo a empresa de monitoramento online da comScore.

Foi o quinto mês consecutivo de ganhos modestos por parte do Bing, que a Microsoft lançou em junho acompanhado por cerca de U$ 100 em campanha publicitária a fim de desafiar a gigante Google.

Este crescimento deve-se a várias inovações e ajustes que a Microsoft realizou no Bing nos últimos meses.

O buscador da Google teve crescimento de 0,5% também em Outubro e quem saiu perdendo foi a parceira da Microsoft, a Yahoo, que teve declínio de 0,8%.

O mercado dos buscadores cada dia mais agitado e nós, utilizadores, é que ganhamos com isso, cada dia teremos serviços de busca mais precisos.

Navegador Google Maps para Android

2009-11-12T11:52:00.000-03:00

O blog do Google anunciou que o Navegador Google Maps estará disponível no Android 2.0.

O primeiro telefone celular que vem com o Android 2.0 é o Motorola Droid.

"Esta nova funcionalidade vem com tudo que você esperaria encontrar em um sistema de navegação GPS, como visualizações em 3D, orientação passo-a-passo por voz e reencaminhamento automático. Mas, ao contrário da maioria dos sistemas de navegação, o Navegador Google Maps foi construído a partir do solo em relação a ligação do seu telefone com a Internet ". E ao contrário de outros sistemas de navegação, é grátis.

Algumas fotos:

Fonte

Windows 7 vs. Mac Snow Leopard: Debate entre Executivos

2009-10-20T00:54:00.000-03:00

Dois executivos um de cada sistema operacional se enfrentam neste debate virtual

Você já imaginou o que seria se você pudesse ver os executivos de ambas as empresas (Microsoft e Apple) discutindo sobre estes produtos? Não através de comerciais, mas sim com um debate honesto mostrando as vantagens de cada produto?

Isso provavelmente nunca irá acontecer porém o site PCMag entrevistou dois grandes executivos: Brian Crollum da Apple e Jay Paulus da Microsoft.

Os dois responderam perguntas sobre seus produtos e o site PCMag intercalou as respostas e criou um debate virtual.

Configura as principais perguntas:

Tema: Qual é o seu Diferencial?
Entrevistador: Na corrida para construir o melhor sistema operacional, onde cada um pensa que está? O que o diferencia? Sr. Croll?

Brian Crollum (Apple): Mac OS X é muito mais simples do que o Windows. Nós estamos mais avançados do ponto de vista tecnológico. Windows 7 ainda tem DLL’s, registros, ainda tem a desfragmentação, ainda precisa de ativação. Nós não fazemos nossos usuários entrarem com códigos de ativação.

Entrevistador: A Microsoft fez muitas coisas para o Windows 7, mas não conseguiu alterar alguns dos fundamentos como a DLL e o Registro.

Jay Paulus (Microsoft): Então o quê? Sim, temos o registro e a DLL, mas isso não é algo que falamos. Nós focamos nosso trabalho em torno de confiabilidade e desempenho.

Entrevistador: E sobre a ativação?

Jay Paulus (Microsoft): A Apple tem um modelo diferente. Eles ganham um monte de dinheiro no hardware e ganham novamente no sistema operacional. Estamos vendendo o sistema operacional. Usamos a ativação para garantir que tenhamos versões originais rodando fora dos EUA.

Tema: Preços
Entrevistador: Vamos falar sobre os preços. Há sistemas operacionais livres por aí, como o Linux, mas, como podemos ver partes de mercado livre não se traduz necessariamente em massa e grande adoção pelo mercado. Como vocês vêem a questão do preço?

Brian Crollum (Apple): Com o Snow Leopard, o preço de upgrade é de $29 para usuários do Leopard ou $49 para um pacote familiar com cinco licenças. Com o Windows 7 Ultimate, a atualização é de $119 para o Home Premium e $199 para profissionais de software, o que é realmente caro.

Entrevistador: Jay, eu sei que a Microsoft tem um plano de $30 para estudantes. O que mais você tem a dizer sobre os preços?

Jay Paulus (Microsoft): Snow Leopard é muito mais parecido com um pacote de serviços (um upgrade) e a Apple está cobrando $29 por ele. Nós não fazemos isso. Windows 7 demonstra grande valor para o cliente e com preços bastante atraentes. Com a Apple você vai ter que comprar o seu caro hardware só para entrar no “jogo”.

Veja a entrevista completa

[Personagens da Computação] Turing, Alan Mathison

2009-10-15T13:45:00.000-04:00

O que dizer de um homem que criou a teoria da computação e, não satisfeito, arregaçou as mangas e assumiu um papel central na construção dos primeiros computadores? De um matemático que venceu com cálculos as bombas de Hitler? No mínimo, que merecia uma estátua no Vale do Silício, um enterro com glórias de herói, que seu nome deveria virar nome de ruas, avenidas, universidades. Mas esse homem morreu esquecido.

Sua história só é conhecida graças à biografia monumental, escrita em 1983 pelo matemático Andrew Hodges. Mas estou me adiantando. Comecemos do começo.

História do grande Alan Mathison Turing (1912-1954)

Alan Turing nasceu em 1912, em Londres. Era um garoto tímido, sem muito talento para o convívio social e sem muito cuidado com a aparência. Na escola, destacava-se apenas por ser esquisito introvertido, irônico, pouco disposto a respeitar regras. Um cara tão estranho que, no futebol, gostava de ser bandeirinha.

Aos 16 anos, conheceu um garoto muito inteligente chamado Christopher Morcom. Naquele momento, Turing descobriu um fato que mudou sua vida (e, novamente me adiantando, aproximou sua morte): ele era gay. Chris morreu em 1930 de pneumonia bovina (transmitida pelo leite). Essa primeira paixão marcaria Alan para sempre. Foi em parte devido à vontade de continuar o legado intelectual do amigo que Turing se aplicou nos estudos, na faculdade de Matemática, e tornou-se conhecido dos professores de Cambridge por seu raciocínio brilhante.

Em 1937, publicou um artigo Sobre as Máquinas Computáveis que teve uma importância enorme para a matemática pura: nele, provava que existiam cálculos impossíveis de serem feitos. Mas também trazia uma aplicação prática que ninguém, na época, percebeu. Turing imaginara uma máquina capaz de fazer todos os cálculos possíveis, desde que lhe dessem as instruções adequadas. O artigo não fazia menção a chips ou processadores continha apenas fórmulas matemáticas. Mas a descrição era exatamente daquilo que, mais tarde, mudaria o mundo com o nome de computador.

Por falar em mudar o mundo, naquele momento surgia um austríaco obcecado por impor suas idéias ao planeta: Adolf Hitler. Um de seus trunfos era uma máquina chamada Enigma um sistema de engrenagens capaz de embaralhar as letras das mensagens antes da transmissão por telégrafo. Os alemães consideravam esse código indecifrável. Caberia a Turing, convocado em 1939 pelo exército britânico, decifrá-lo.

Um ano mais tarde, a guerra parecia uma barbada para Hitler. A Europa continental havia caído e as ilhas britânicas estavam, bem, ilhadas dependiam dos navios que cruzavam o Atlântico com armas e mantimentos americanos. Os submarinos alemães afundavam 200.000 toneladas de embarcações todo mês e o único jeito de descobrir a posição dos submarinos era decifrar suas mensagens.

Turing tirou a cabeça das máquinas teóricas e sujou as mãos na graxa de engenhocas reais. Uma delas, o Colossus, é tataravó do PC no qual digito agora. No começo, elas demoravam semanas para tornar uma mensagem compreensível. Mas, em 1942, os ingleses já decodificavam 50 000 mensagens por mês, uma por minuto. Os submarinos alemães eram abatidos como moscas. O preconceituoso Hitler, cuja equipe olímpica tinha sido derrotada em 1936 pelo atleta negro americano Jesse Owens, perdia a guerra para um intelectual homossexual.

O ditador nunca soube disso. Aliás, nem a mãe de Turing. Sua participação na guerra permaneceu secreta por décadas. Tanto que, quando a polícia o prendeu em 1952 por grande indecência em outras palavras, homossexualismo , ninguém o defendeu dizendo que se tratava de um herói de guerra. Para enfrentar o julgamento, teve que se afastar de suas pesquisas sobre inteligência artificial Turing é inventor de um teste até hoje usado para decidir se uma máquina pensa. Acabou condenado a um tratamento com hormônios que arruinou seu físico.

Na noite de 7 de junho de 1954, atormentado, o matemático deitou-se na cama e mordeu uma maçã. Na manhã seguinte, não acordou. A fruta havia sido mergulhada numa jarra de cianeto.

Autor: Editor da revista Superinteressante

Finalmente em 2009 o Reino Unido pede desculpas póstumas a Alan Turing

O primeiro-ministro britânico, Gordon Brown, ofereceu um pedido póstumo de desculpas ao matemático Alan Turing, pelo tratamento "desumano" que recebeu das autoridades britânicas e que o levou ao suicídio em 1954. Turing atuou com a equipe responsável por quebrar o código secreto Enigma, usado pelos alemães na II Guerra Mundial, e produziu trabalhos teóricos que estão na base de boa parte da informática moderna e das pesquisas sobre inteligência artificial.

Homossexual, Turing foi processado numa época em que essa conduta era considerada crime no Reino Unido, e forçado a se submeter a um tratamento com hormônios.

Em 1952, Turing foi condenado por indecência, por ter mantido relações sexuais com outro homem, e teve de optar entre ir para a cadeia ou sofrer "castração química" - a injeção de hormônios para suprimir a libido. Seus privilégios de segurança foram revogados ele foi impedido de continuar a trabalhar para o governo.

Dois anos depois, cometeu suicídio, comendo uma maça envenenada.

No momento em que o Reino Unido marca dos 70 anos do início da guerra em 1939 - lembrada como "a melhor hora" do povo britânico - Brown disse que Turing "merecia algo muito melhor" do que o tratamento que recebeu da sociedade no pós-guerra.

"Não é exagero dizer que, sem sua contribuição extraordinária, a história da II Guerra Mundial poderia ter sido muito diferente", afirmou o primeiro-ministro. "Ele realmente foi um dos indivíduos para quem podemos apontar e dizer que suas contribuições únicas ajudaram a virar a maré da guerra".

Brown disse que Turing foi "de fato, julgado por ser gay". A homossexualidade continuou a ser ilegal no Reino Unido até 1967.

"A dívida de gratidão para com ele torna ainda mais horrível, portanto, que tenha sido tratado de modo tão desumano", disse Brown. "Sentimos muito, você merecia algo muito melhor".

As desculpas de Brown seguem-se a uma petição online que atraiu mais de 30.000 assinaturas, incluindo o romancista Ian McEwan e o cientista Richard Dawkins.

O cientista John Graham-Cumming disse ter começado a campanha porque "Turing não era tão conhecido no Reino Unido quanto acho que deveria ser, como um herói da guerra um grande matemático". Graham-Cumming disse ainda que não seria um exagero chamar Turing de "pai da computação".

Fontes:
[1] Alan Turing (link)
Perfil e biografia do inventor do computador
[2] Reino Unido pede desculpas póstumas a Alan Turing (link)
Homossexual, o gênio da matemática foi processado numa época em que essa conduta era considerada crime

Google Wave é mais seguro que e-mail

2009-10-15T11:13:00.000-04:00

Google Wave, a plataforma de colaboração em tempo real da Google atualmente em fase beta é mais segura que o tradicional e-mail, afirma a empresa.

De acordo com Greg D’alesandre, gerente do Google Wave, essa segurança é produto da concentração da Google em enfrentar questões de privacidade e segurança. Pensando nisso o sistema está sendo construído já pensando nestas características, o que pode fazer o desenvolvimento ser mais lento, mas irá prover maior segurança a seus usuários.

Greg D’alesandre detalhou diversas características de segurança do Wave. As três principais características são:

Características para evitar falsificação

Wave tem vários níveis de segurança que são projetados para evitar a falsificação de e-mail. Spoofing, ou seja, quando você recebe um e-mail que afirma ser de uma pessoa ou empresa que você conhece, mas é na verdade de outra pessoa - um hacker na maioria dos casos.

"Você sabe que você está recebendo a onda da pessoa que está enviando a você e não nada foi alterado pelo caminho. Este é um problema muito presente nas tecnologias de comunicação atual - os dados podem ser alterados durante fluxo e você nunca irá saber", disse D’alesandre.

HTTPS ativado por padrão

Para uma camada adicional de segurança, todo o tráfego de onda é por padrão codificado via HTTPS, um protocolo para comunicações seguras.

Lista Branca

Usuários do Wave serão capazes de selecionar as pessoas que querem colaborar e colocá-los em uma lista branca de pessoas aprovadas. Somente aqueles que estão na lista terão a possibilidade de contatá-los através das ondas e todos os outros serão ignorados.

As duas primeiras características já estão em funcionamento e a terceira estará em breve.

Fonte: RWW

[Personagens da Computação] Dijkstra, Edsger Wybe

2009-10-14T14:11:00.001-04:00

Com este artigo início uma série sobre grandes personagens da história da computação.

Sugestões de personagens podem ser feitas através dos comentários e eu farei o possível para encontrar algumas informações sobre o mesmo e postar aqui.

Creio que seja importante valorizar o nosso passado e entender de onde vieram esses conceitos que conhecemos e usamos hoje em dia.

Começaremos pela história do Dijkstra [pronuncie algo entre "Dêcstra" e "Dêicstra"]:

A história do grande Edsger Wybe Dijkstra (1930-2002)

"A arte de programar consiste em organizar e dominar a complexidade" - Edsger W. Dijkstra

O professor Edsger Wybe Dijkstra, um pioneiro notável da ciência e da indústria da computação, faleceu após uma longa luta contra o câncer, em 6 de agosto de 2002 em Nuenen, nos Países Baixos.

Dijkstra nasceu em 1930 em Rotterdam, filho de um pai químico e uma mãe matemática. Graduou-se no Gymnasium Erasmianum em Rotterdam e obteve graduações na matemática e na física teórica da universidade de Leyden, e um Ph.D. em ciência da computação da universidade de Amsterdã. Trabalhou como programador no centrum de Mathematisch, Amsterdã, 1952-1962; era professor de matemática, universidade de Eindhoven de tecnologia, 1962-1984; e era um companheiro da pesquisa da corporação de Burroughs, 1973-1984. Deteve a cadeira centennial de Schlumberger em ciências da computação na universidade de Texas em Austin, 1984-1999, e aposentou-se como professor Emeritus em 1999.

A Dijkstra foi concedido em 1972 o prêmio ACM Turing, visto freqüentemente como o prêmio Nobel para a computação. Era membro da academia real de artes e ciências dos Países Baixos, da academia de artes e ciências americana, e um distinto companheiro da sociedade britânica de computação. Recebeu em 1974 o prêmio AFIPS Harry Goode, em 1982 o prêmio de pioneiro da computação do IEEE, e em 1989 o prêmio ACM SIGCSE para contribuições proeminentes à instrução da ciência da computação. A universidade de Atenas de economia concedeu-lhe um doutorado honorário em 2001. Em 2002, a fundação de C&C do Japão reconheceu Dijkstra "por suas contribuições abrindo caminho ao estabelecer base científica para o software de computador com a pesquisa criativa da teoria básica do software, da teoria do algoritmo, da programação estruturada, e dos semáforos".

Dijkstra é reconhecido por suas contribuições à metodologia matemática. É responsável pela idéia de construção de sistemas operacionais como processos seqüenciais explicitamente sincronizados, pelo desenvolvimento formal de programas de computador, e para as fundações intelectuais para o controle disciplinado do não determinismo. É bem conhecido por seu algoritmo de caminho mais curto surpreendentemente eficiente e por ter projetado e codificado o primeiro compilador do Algol 60. Era notoriamente o líder da abolição do comando GOTO na programação.

Dijkstra era um escritor prodígio. Sua coleção inteira de mais de mil e trezentos trabalhos manuscritos foi digitalizada e estão acessíveis em
http://www.cs.utexas.edu/users/EWD. Correspondeu-se também regularmente com as centenas dos amigos e dos colegas através dos anos, não por email, mas por cartas convencionais, as quais tinha maior gosto.

Dijkstra era notório por sua sagacidade, eloqüência, e a intimidade com palavras, como em sua observação "a pergunta de se os computadores podem pensar é como a pergunta de se os submarinos podem nadar"; seu conselho a um pesquisador promissor, que perguntou como selecionar um tópico para a pesquisa: "faça somente o que somente você pode fazer"; e sua observação em sua palestra da concessão de Turing "em sua capacidade como uma ferramenta, computadores serão mais uma ondulação na superfície de nossa cultura. Em sua capacidade como o desafio intelectual, são sem precedentes na história cultural da humanidade".

Dijkstra enriqueceu a língua da computação com muitos conceitos e frases, como a programação estruturada, separação dos interesses, sincronização, deadlock, jantar dos filósofos, a precondição mais fraca, o comando "stored", o milagre excluído, e os famosos "semáforos" para controlar processos de computador. O dicionário inglês de Oxford cita seu uso das palavras "vetor" e "pilha" em um contexto de computação.

Dijkstra apreciava tocar Mozart para seus amigos em seu piano Boesendorfer. Ele e sua esposa tinham um gosto por explorar os parques nacionais em sua caminhonete Volkswagen, chamada a "máquina de Turing", na qual escreveu muitos trabalhos técnicos.

Durante toda sua carreira científica, Dijkstra formulou e perseguiu ideais acadêmicos de mais elevados rigores científicos, desvinculado de
considerações comerciais ou políticas. Simplicidade, beleza, e eloqüência eram seus pontos fortes, e sua insistência na elegância na programação e na matemática eram uma inspiração a milhares. Julgou seu próprio trabalho por padrões mais elevados e lançou um desafio a seus muitos amigos para fazerem o mesmo.

Na passagem de Dijkstra, deixe-nos recordar a observação da divisão de Phaedo sobre Sócrates: "nós podemos verdadeiramente dizer que de todos os homens de seu tempo, ele era o mais sábio, o mais justo e o melhor".

Autor: Desconhecido

Algoritmo de Dijkstra

2009-10-14T12:49:00.002-04:00

"A arte de programar consiste em organizar e dominar a complexidade" - Edsger W. Dijkstra

Este artigo discute um algoritmo eficiente para o Problema de Caminho de Custo Mínimo a partir de uma origem:

Dado um digrafo com custos não-negativos nos arcos e um vértice s, encontrar um caminho de custo mínimo com raiz s no digrafo.
O algoritmo foi inventado por Dijkstra [pronuncie algo entre "Dêcstra" e "Dêicstra"] e publicado em 1959. O algoritmo pode ser usado, em particular, para encontrar um caminho de custo mínimo de um dado vértice a outro.

O algoritmo

A estrutura do algoritmo de Dijkstra é muito parecida com a do algoritmo de Prim. (Embora o algoritmo de Dijkstra, ao contrário do algoritmo de Prim, só se aplique a custos não-negativos.)

No início de cada iteração, temos uma arborescência T com raiz s. Para qualquer vértice w fora de T, o custo de w em relação a T é, por definição,

a distância de s a w no digrafo T+F,

sendo F a franja de T. Aqui, a franja de T é o conjunto de todos os arcos que saem de T. Em outras palavras, o custo de um vértice w que está fora de T é o custo de um caminho mínimo dentre os que começam em s, terminam em w, e só têm um arco — o último — fora de T. Diremos que o último arco de um tal caminho mínimo é o arco-pai de w.

Cada iteração do algoritmo de Dijkstra consiste no seguinte:

1. se a franja de T não é vazia
1.1 então seja w um vértice fora de T que tem custo mínimo
1.2 seja e o arco-pai de w
1.3 comece nova iteração com T+e no papel de T
2. senão pare

Nas implementações abaixo, a arborescência T será representada por um vetor pai. O custo de cada vértice w será armazenado em cst[w] e a ponta inicial do arco-pai de w será armazenada em fr[w].

As implementações que examinaremos abaixo têm uma peculiaridade: no início da primeira iteração, a árvore (representada pelo vetor pai) está vazia. Somente a partir do início da segunda iteração a implementação passa a se comportar de acordo com o algoritmo.

Implementação para digrafos densos

Suponha que nosso digrafo está representado por sua matriz de adjacência. Como de hábito, se v-w não é arco então G[v][w] vale maxCST. Supõe-se que o valor de maxCST é tão grande que não se confunde com o custo de um caminho simples.

/* Recebe digrafo G com custos não-negativos nos arcos e um vértice s. Calcula uma arborescência de caminhos mínimos com raiz s. A arborescência é armazenada no vetor pai. As distâncias em relação a s são armazenadas no vetor cst. */

/* A função supõe que a soma dos custos de todas os arcos é estritamente menor que maxCST.  Supõe também que o digrafo tem no máximo maxV vértices. */

void dijkstraV1(int s) { 
   int w, w0, fr[maxV];
   for (w = 0; w < n; w++) { 
      pai[w] = -1; 
      cst[w] = maxCST; 
   }
   fr[s] = s;
   cst[s] = 0.0;
   while (1) {
      double mincst = maxCST;
      for (w = 0; w < n; w++) {
         if (pai[w] == -1 && mincst > cst[w])
               mincst = cst[w0=w]; 
      if (mincst == maxCST) break;
      pai[w0] = fr[w0];
      for (w = 0; w < n; w++) 
         if (cst[w] > cst[w0] + G[w0][w]) {
            cst[w] = cst[w0] + G[w0][w]; 
            fr[w] = w0; 
         }
   }
}

Note que essa implementação é quase idêntica à implementação correspondente do algoritmo de Prim.

Duas observações técnicas:
1. Observe como a comparação de cst[w] com cst[w0] + G[w0][w] trata corretamente do caso em que w0 e w não são adjacentes e portanto G[w0][w] vale maxCST.
2. Estamos supondo, implicitamente, que maxCST é menor que a metade de DBL_MAX, de modo que a expressão cst[w0] + G[w0][w] não produz overflow.

No começo de cada iteração (a partir da segunda) temos uma arborescência com raiz s, representada pelo vetor pai. No início de cada iteração, as seguinte propriedades valem para cada vértice v:

1. se v está na arborescência então cst[v] é a distância de s a v,
senão, cst[v] é o custo do vértice v em relação à arborescência;

2. se v está fora da arborescência e cst[v] < maxCST então
fr[v] é o penúltimo vértice de um caminho simples de custo cst[v] que liga s a v.

A operação mais característica do algoritmo de Dijkstra é a relaxação de um arco:

         if (cst[w] > cst[w0] + G[w0][w]) {
             cst[w] = cst[w0] + G[w0][w]; 
         }

Essa operação aparece em toda implementação do algoritmo.

Implementação para digrafos esparsos

A implementação para digrafos representados por vetor de listas de adjacência usa uma fila de prioridades, tal como a correspondente implementação do algoritmo de Prim.

/* Recebe digrafo G com custos não-negativos nos arcos e um vértice s. Calcula uma SPT com origem s. A SPT é armazenada no vetor pai. As distâncias em relação a s são armazenadas no vetor cst. */

/* A implementação supõe que a soma dos custos de todos os arcos é estritamente menor que maxCST.  Supõe também que o digrafo tem no máximo maxV vértices. */

void dijkstraEsparso (int s) { 
   int w, w0, fr[maxV], p;
   PQinit(); 
   for (w = 0; w < n; w++) 
      pai[w] = fr[w] = -1; 
   fr[s] = s; 
   cst[s] = 0.0; 
   PQinsert(s);
   while (!PQempty()) {
      w0 = PQdelmin(); 
      pai[w0] = fr[w0]; 
      for (p = 0; p < grau[w0]; p++) {
         w = G[w0][p].w;
         if (fr[w] == -1) { 
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQinsert(w); 
            fr[w] = w0; 
         } 
         else if (cst[w] > cst[w0] + G[w0][p].cst) {
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQdec(w); 
            fr[w] = w0; 
         }
      }
   }
}

(Note a operação de relaxação if (cst[w] > cst[w0]+G[w0][p].cst) { cst[w] = cst[w0]+G[w0][p].cst; } característica do algoritmo de Dijkstra.)

A função dijkstraEsparso usa uma fila de vértices com prioridades definidas pelo vetor cst. A fila é manipulada pelas seguintes funções:

PQinit(): inicializa uma fila de vértices em que todo vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(v): reorganiza a fila depois que o valor de cst[v] foi decrementado.
A implementação clássica da fila de prioridades usa uma estrutura de heap.

Tal como fizemos com o algoritmo de Prim, podemos organizar a implementação do algoritmo de Dijkstra de maneira um pouco diferente, inserindo todos os vértices na fila de prioridades antes mesmo do início do processo iterativo:

void dijkstraV2 (int s) { 
   int w, w0, p;
   PQinit(); 
   for (w = 0; w < n; w++) { 
      pai[w] = -1; 
      cst[w] = maxCST; 
      PQinsert(w); 
   }
   pai[s] = s;
   cst[s] = 0.0; 
   PQdec(s);
   while (!PQempty()) {
      w0 = PQdelmin();
      if (cst[w0] == maxCST) break;
      for (p = 0; p < grau[w0]; p++) {
         w = p->w;
         if (cst[w] > cst[w0] + G[w0][p].cst) { 
            cst[w] = cst[w0] + G[w0][p].cst; 
            PQdec(w); 
            pai[w] = w0; 
         }
      }
   }
}

Fonte: IME

Caminhos de custo mínimo

2009-10-13T17:46:00.000-04:00

Este artigo introduz o problema dos caminhos de custo mínimo em digrafos com custos nos arcos. Vamos supor que todos os custos são não-negativos (o problema faz sentido sem essa hipótese, mas fica bem mais difícil).

Caminhos mínimos e distâncias

Num digrafo com custos nos arcos, o custo de um caminho é a soma dos custos dos arcos do caminho. Um caminho C é mínimo se não existe outro caminho com mesma origem e mesmo término que C, mas mais barato que C. Por causa da presença dos custos, este conceito é mais geral que o conceito de caminho mínimo definido em outro artigo.

A distância de um vértice s a um vértice t é o custo de um caminho mínimo de s a t. Em outras palavras, a distância de s a t é d se e somente se
(1) existe um caminho de custo d de s a t; e
(2) nenhum caminho de s a t tem custo menor que d.

Se o digrafo é um grafo, a distância de s a t é igual à distância de t a s. Portanto, podemos usar a expressão "distância entre s e t" nesse caso.

Vamos supor, ao tratar de caminhos mínimos e distâncias, que o custo de cada arco é um número não-negativo.

Assim, a distância de um vértice s a um vértice t fica bem definida sempre que existe algum caminho de s a t. (Se não existe caminho algum, podemos dizer que a distância de s a t é infinita.) [O problema do caminho mínimo em digrafos que têm arcos de custo negativo é muito importante, mas bem mais difícil. No caso de digrafos simétricos, ele está relacionado com o célebre problema do caminho hamiltoniano.]

Digrafos com custos não-negativos têm a seguinte propriedade crucial: qualquer segmento de um caminho mínimo é um caminho mínimo.

Outro aspecto dessa mesma propriedade: a menos que o digrafo tenha um ciclo de custo nulo, todo caminho mínimo é simples. Mesmo que o digrafo tenha ciclos de custo nulo, é verdade que para todo vértice s e todo vértice t

existe um caminho simples de s a t cujo custo é igual à distância de s a t

(desde que essa distância seja finita). Podemos nos restringir, portanto, a caminho mínimos que são simples.

O problema do caminho mínimo

Nosso problema básico é o seguinte:

Problema do Caminho Mínimo com Origem e Término Fixos (Source-sink Shortest Path Problem): Dados vértices s e t de um digrafo com custos não-negativos nos arcos, encontrar um caminho mínimo simples de s a t.
(É claro que o problema só tem solução se t pode ser alcançado a partir de s, ou seja, se existe um caminho de s a t.)

A experiência mostra que é mais prático tratar de um problema mais geral:

Problema dos Caminhos Mínimos com Origem Fixa (Single-source Shortest Paths Problem): Dado um vértice s de um digrafo com custos não-negativos nos arcos, encontrar, para cada vértice t que pode ser alcançado a partir de s, um caminho mínimo simples de s a t.

Todos os algoritmos para esses problemas exploram a seguinte propriedade básica:

Propriedade Triangular: Para quaisquer vértices x, y e z de um digrafo com custos não-negativos nos arcos, tem-se
d(x,z) ≤ d(x,y) + d(y,z) ,

sendo d(i,j) a distância de i a j.

Arborescência de caminhos mínimos

Dado um vértice s de um digrafo G com custos não-negativos nos arcos, uma arborescência de caminhos mínimos (= shortest-paths tree = SPT) com raiz s é uma arborescência em G que tem a seguinte propriedade: para todo vértice t de G que pode ser alcançado a partir de s,

o único caminho de s a t na arborescência é um caminho mínimo em G.

Vou usar a sigla em inglês — SPT — para me referir a uma arborescência de caminhos mínimos. É claro que qualquer SPT pode ser representada por um vetores de pais.

Uma SPT pode ser vista como uma solução do Problema dos Caminhos Mínimos Com Origem Fixa. Por isso mesmo, esse problema pode ser reformulado assim:

Problema da SPT: Dado um vértice s de um digrafo com custos não-negativos nos arcos, encontrar uma SPT com raiz s no digrafo.
Exemplo

A tabela define um digrafo com custos nos arcos.

0-1 .41
1-2 .51
2-3 .50
4-3 .36
3-5 .38
3-0 .45
0-5 .29
5-4 .21
1-4 .32
4-2 .32
5-1 .29
A tabela abaixo dá a distância de 0 a cada um dos demais vértices. Também especifica caminhos mínimos de 0 a cada um dos demais vértices.

0 .0 0
1 .41 0-1
2 .82 0-5-4-2
3 .86 0-5-4-3
4 .50 0-5-4
5 .29 0-5
Eis uma SPT com origem 0 representados por um vetores de pais:

v 0 1 2 3 4 5
pai[v] 0 0 4 4 5 0

Fonte: IME

Algoritmo de Prim

2009-10-13T15:36:00.002-04:00

Nosso problema neste artigo é o mesmo do anterior: encontrar uma MST (árvore geradora mínima) de um grafo G com custos nas arestas.

O algoritmo

O algoritmo de Prim (publicado em 1961) se apoia nas condições de otimalidade de MSTs para encontrar uma MST de um grafo G com custos nas arestas.

Para descrever o algoritmo, convém recorrer ao conceito de franja. A franja (= fringe) de uma subárvore não-geradora T de G é o conjunto de todas as arestas de G que têm uma ponta em T e outra ponta fora. Se denotarmos por X o conjunto dos vértices de T e por Y o conjunto dos vértices fora de X, podemos dizer que a franja é o conjunto das arestas que pertencem ao corte (X,Y).

No início de cada iteração do algoritmo de Prim temos uma árvore T. (No início da primeira iteração, T consiste em um único vértice.) Cada iteração consiste no seguinte:

1. se a franja de T não é vazia
1.1 então seja e uma aresta de custo mínimo na franja
1.2 comece nova iteração com T+e no papel de T
2. senão pare

Se G for conexo, o algoritmo produz uma MST de G. Caso contrário, o algoritmo produz uma MST de uma das componentes de G.

Implementação grosseira do algoritmo

Nossa primeira implementação do algoritmo de Prim é simples e óbvia mas ineficiente. A função abaixo recebe um grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A MST é tratada como uma arborescência com raiz 0 e armazenada no vetor de pais pai.

A função supõe que o grafo é representado por sua matriz de adjacência e o custo de cada aresta é estritamente menor que maxCST.

void primForcaBruta() { 
   int v, w; 
   for (w = 0; w < n; w++) pai[w] = -1; 
   pai[0] = 0; 
   while (1) {
      double mincst = maxCST;
      int v0, w0;
      for (w = 0; w < n; w++) 
         if (pai[w] == -1) 
            for (v = 0; v < n; v++)
               if (pai[v] != -1 && mincst > G[v][w]) 
                  mincst = G[v0=v][w0=w];
      if (mincst == maxCST) break; 
      /* A */
      pai[w0] = v0;
   }
}

No ponto A, v0-w0 é uma aresta de custo mínimo dentre as que estão na franja da árvore. O custo da aresta v0-w0 é mincst.

Implementações eficientes

Toda implementação eficiente do algoritmo de Prim depende do conceito de custo de um vértice em relação a uma árvore. Dada uma árvore não-geradora do grafo, o custo de um vértice w que está fora da árvore é o custo de uma aresta mínima dentre as que incidem em w e estão na franja da árvore. Em outras palavras, o custo de w é o custo de uma aresta mínima dentre as que têm uma ponta na árvore e outra em w. Se nenhuma aresta da franja incide em w, o custo de w é maxCST (que é maior que o custo de qualquer aresta e portanto tem o sabor de ∞).

Nas implementações que examinaremos abaixo, os custos dos vértices e as arestas que justificam esses custos são representados pelos vetores

cst e fr.

O custo do vértice w em relação à árvore é cst[w]. Para cada vértice w fora da árvore, o vértice fr[w] está na árvore e a aresta que liga w a fr[w] tem custo cst[w]. Cada iteração do algoritmo de Prim escolhe um vértice w fora da árvore e adota fr[w] como valor de pai[w].

As implementações que examinaremos abaixo têm uma peculiaridade: no início da primeira iteração, a árvore (representada pelo vetor pai) está vazia. Durante a primeira iteração a árvore adquire seu primeiro vértice e a partir da segunda iteração a implementação passa a se comportar como o algoritmo descrito acima.

Implementação eficiente para grafos densos

A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência:

/* Recebe grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0. A função armazena a MST no vetor pai, tratando-a como uma arborescência com raiz 0. */

/* O grafo G é representado por sua matriz de adjacência. A função supõe que e.cst < maxCST para cada aresta e. Supõe também que o grafo tem no máximo maxV vértices. */



void primDenso() { 

double cst[maxV]; 

int v0, w, fr[maxV];

for (w = 0; w < n; w++) {
      pai[w] = -1; 
      cst[w] = maxCST; 
   }
   v0 = 0;
   fr[v0] = v0;
   cst[v0] = 0.0;
   while (1) {
      double mincst = maxCST; 
      for (w = 0; w < n; w++) 
         if (pai[w] == -1 && mincst > cst[w]) 

mincst = cst[v0=w]; 

if (mincst == maxCST) break;

pai[v0] = fr[v0];

for (w = 0; w < n; w++) 
         if (pai[w] == -1 && cst[w] > G[v0][w]) {

cst[w] = G[v0][w]; 

fr[w] = v0; 

}

}

}

O fragmento de código

if (cst[w] > G[v0][w]) {
                cst[w] = G[v0][w]; 
            }

é característico do algoritmo de Prim. A operação que ele executa é conhecida como relaxação (da aresta v0-w). Essa operação aparece em toda implementação do algoritmo.

Desempenho: No pior caso, o consumo tempo da função primDenso é proporcional a V^2.

Portanto, a função primDenso é linear para grafos densos (pois o tamanho de tais grafos é proporcional a V^2).

Implementação eficiente para grafos esparsos

Esta seção discute uma implementação mais sofisticada do algoritmo de Prim. Ela usa uma fila de prioridades (= priority queue) para escolher, eficientemente, a próxima aresta a ser acrescentada à árvore.

static double cst[maxV];
/* Recebe grafo G com custos nas arestas e calcula uma MST da componente de G que contém o vértice 0.  A função armazena a MST no vetor pai, tratando-a como uma arborescência com raiz 0. */

/* O grafo G é representado por listas de adjacência. */

void primEsparso() { 
   int v0, w, fr[maxV], p; 
   PQinit(); 
   for (w = 0; w < n; w++) 
      pai[w] = fr[w] = -1; 
   v0 = 0;
   fr[v0] = v0; 
   cst[v0] = 0.0; 
   PQinsert(v0);
   while (!PQempty()) {
      v0 = PQdelmin(); 
      pai[v0] = fr[v0]; 
      for (p = 0; p < grau[v0]; p++) {
         w = g[v0][p].w;
         if (pai[w] == -1) {
            if (fr[w] == -1) { 
               cst[w] = g[v0][p].cst; 
               PQinsert(w); 
               fr[w] = v0; 
            } 
            else if (cst[w] > g[v0][p].cst) {
               cst[w] = g[v0][p].cst; 
               PQdec(w); 
               fr[w] = v0; 
            }
         }
      }
   }
}

(Note a operação de relaxação if (cst[w] > g[v0][p].cst) { cst[w] = g[v0][p].cst; } característica do algoritmo de Prim.)

A função primEsparso usa uma fila com prioridades. A fila é manipulada pelas seguintes funções:

PQinit(): inicializa uma fila de vértices em que cada vértice v tem prioridade cst[v].
PQempty(): devolve 1 se a fila estiver vazia e 0 em caso contrário.
PQinsert(v): insere o vértice v na fila.
PQdelmin(): retira da fila um vértice de prioridade mínima.
PQdec(w): reorganiza a fila depois que o valor de cst[w] foi decrementado.

A implementação clássica da fila de prioridades usa uma estrutura de heap. O heap é armazenado num vetor pq[1..N] (a posição 0 do vetor não é usada). A prioridade de um vértice pq[k] no heap é cst[pq[k]]. Propriedade fundamental do heap:

cst[pq[k/2]] ≤ cst[pq[k]]

para k=2,..,N. Portanto, o vértice pq[1] minimiza cst.

/*Supõe-se que N ≤ maxV. */

/* O vetor qp é o "inverso" de pq:  para cada vértice v, qp[v] é o único índice tal que pq[qp[v]] == v.  É claro que qp[pq[i]] == i para todo i. */

static Vertex pq[maxV+1]; 
static int N;
static int qp[maxV]; 

void PQinit(void) { 
  N = 0; 
}
int PQempty(void) { 
   return N == 0; 
}
void PQinsert(Vertex v) { 
   qp[v] = ++N; 
   pq[N] = v; 
   fixUp(N); 
}
Vertex PQdelmin(void) { 
   exch(1, N); 
   --N; 
   fixDown(1); 
   return pq[N+1]; 
}
void PQdec(Vertex w) { 
   fixUp(qp[w]); 
}
static void exch(int i, int j) {
   Vertex t;
   t = pq[i]; pq[i] = pq[j]; pq[j] = t;
   qp[pq[i]] = i;
   qp[pq[j]] = j;
}
static void fixUp(int k) {
   while (k > 1 && cst[pq[k/2]] > cst[pq[k]]) {
      exch(k/2, k);
      k = k/2;
}
static void fixDown(int k) { 
   int j;
   while (2*k <= N) { 
      j = 2*k;
      if (j < N && cst[pq[j]] > cst[pq[j+1]]) j++;
      if (cst[pq[k]] <= cst[pq[j]]) break;
      exch(k, j); 
      k = j;
   }
}

(O código de primEsparso pode parecer um pouco assustador porque depende de um grande número de funções auxiliares. Pode ser um bom exercício escrever uma versão "compacta" da função primEsparso, que incorpore, tanto quanto razoável, o código das funções de manipulação da fila de prioridades.)
Desempenho: Eis uma estimativa do consumo de tempo no pior caso de cada uma das funções de manipulação da fila de prioridades quando aplicada a um grafo com V vértices:

PQinit: constante, ou seja, não depende de V;
PQempty: constante, ou seja, não depende de V;
PQinsert: proporcional a lg(V);
PQdelmin: proporcional a lg(V);
PQdec: proporcional a lg(V).
Assim, o consumo de tempo da função primEsparso é proporcional a V lg(V) + E lg(V) no pior caso. Para grafos conexos, essa expressão se reduz a
E lg(V).

Portanto, a função primEsparso é um pouco pior que linear. Mesmo assim, esse desempenho é melhor que o da função primDenso quando os grafos são esparsos.
Outra implementação para grafos esparsos

O código abaixo é uma variante da função primEsparso. Nessa variante, os vértices são todos colocados na fila de prioridades antes do início do processo iterativo. O vetor pai usurpa o papel de fr e fr é dispensado. Com isso, o valor de cada elemento de pai pode ser alterados várias vezes ao longo do processo iterativo (ao contrário do que acontece em primEsparso).

O código dessa variante é mais curto que o de primEsparso (embora não seja mais eficiente). Por isso, há quem considere essa variante mais atraente.

static double cst[maxV];

void primSimples() { 
   int v0, w, p;
   PQinit(); 
   for (w = 0; w < n; w++) { 
      pai[w] = -1;
      cst[w] = maxCST; 
      PQinsert(w); 
   }
   v0 = 0;
   pai[v0] = v0;
   cst[v0] = 0.0; 
   PQdec(v0);
   while (!PQempty()) {
      v0 = PQdelmin();
      if (cst[v0] == maxCST) break;
      for (p = 0; p < grau[v0]; p++) {
         w = g[v0][p].w;
         if (cst[w] > g[v0][p].cst) { 
            cst[w] = g[v0][p].cst; 
            PQdec(w); 
            pai[w] = v0; 
         }
      }
   }
}

Exercícios para Fixação
1. Qual a diferença entre grafos esparsos e grafos densos?
2. Esta afirmação: "A implementação abaixo é ótima para grafos densos. É apropriado, portanto, representar o grafo por uma matriz de adjacência." está correta? Porque?
3. Qual a vantagem de se saber se o grafo é esparso ou denso quando precisamos saber sua árvore geradora mínima?
4. Porque usar uma fila de prioridade ao invés de utilizar uma fila comum?
Fonte: IME

Árvores geradoras de custo mínimo - MST

2009-10-13T11:28:00.002-04:00

Iremos introduzir alguns conceitos ao decorrer deste artigo até chegarmos a árvore geradora mínima em si. E também iremos falar de algumas de suas propriedades.

Subgrafo de custo mínimo

Seja G um grafo com custos nas arestas (os custos podem ser positivos, negativos, ou nulos). O custo de um subgrafo T de G é a soma dos custos das arestas de T. Se U é uma coleção de subgrafos de G, um elemento T de U tem custo mínimo se o custo de T é menor ou igual [note o "ou igual"] que o custo de qualquer outro elemento de U.

Em outras palavras, T tem custo mínimo se nenhum elemento de U tem custo estritamente menor que o de T.

Árvore geradora mínima

Uma árvore geradora mínima (= minimum spanning tree), ou MST, de um grafo com custos nas arestas é qualquer árvore geradora do grafo que tenha custo mínimo.

Problema: Encontrar uma MST de um grafo G com custos nas arestas.

É claro que o problema tem solução se e somente se o grafo G é conexo. Boa pergunta: como encontrar uma MST de um grafo conexo se todas as suas arestas têm o mesmo custo?

A propriedade dos ciclos

A Primeira Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:

Condição de Otimalidade: Se T é uma MST de um grafo então toda aresta e fora de T tem custo máximo dentre as arestas do único ciclo não-trivial em T+e.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)

Exemplo: Seja T a árvore geradora definida pelas 5 arestas "internas" da figura. Seja e a aresta "horizontal" "superior". Como e não é máxima no ciclo não-trivial de T+e, a árvore T não é uma MST.

A propriedade dos cortes

A Segunda Propriedade da Troca, discutida no artigo anterior, leva à seguinte condição de otimalidade:

Condição de Otimalidade: Se T é uma MST de um grafo então cada aresta t de T é uma aresta mínima dentre as que atravessam o corte determinado por T–t.
(A recíproca dessa proposição é verdadeira, mas sua demonstração é um pouco mais complexa.)

Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta "horizontal" no meio da figura. Como t não é mínima no corte determinado por T–t, a árvore T não é uma MST.

Fonte: IME

Trocando a senha do Gmail

2009-10-06T12:20:00.000-04:00

Como trocar sua senha do Gmail ?

Siga os passos:

1. Entre no site do Gmail

2. No menu superior direito clique em CONFIGURAÇÕES.

3. Depois clique em CONTAS E IMPORTAÇÃO.

4. Depois lá embaixo clique em CONFIGURAÇÕES DA CONTA GOOGLE.

5. Agora você verá suas informações e clique em ALTERAR SENHA.

6. Agora insira sua senha antiga.

7. Agora insira sua senha nova duas vezes.

8. Clique em Salvar.

Pronto, sua senha atualizada!

Trocando a senha do Hotmail

2009-10-06T12:14:00.001-04:00

Como trocar sua senha do Hotmail ?

Siga os passos:

1. Entre no site do HOTMAIL

2. No menu superior direito clique em OPÇÕES.

3. Depois clique em MAIS OPÇÕES.

4. Depois clique em Exibir e editar suas informações pessoais.

5. Agora você verá suas informações e clique em ALTERAR (ao lado de senha *******).

6. Agora insira sua senha antiga.

7. Agora insira sua senha nova duas vezes.

8. Clique em Salvar.

Pronto, sua senha atualizada!

Senhas Roubadas do Gmail, Hotmail e Yahoo

2009-10-06T10:53:00.004-04:00

Grupo de Hackers roubou logins e senhas de mais de 20.000 usuários da Google, Yahoo e Hotmail.

O canal de tv BBC em seu noticiário nesta terça-feira (06/10) recomendou aos seus telespectadores que troquem suas senhas pois os logins e senhas foram divulgadas na internet por alguns instantes e os hackers continuam em posse das mesmas. E estima-se que eles tenham roubado mais de 20.000 pois estes eram somente os iniciados em A ou B.

Então o ALLgoritmos.com também alerta sobre esse fato e pede que seus leitores alterem suas senhas para que não sejam lesados por essa invasão.

APRENDA a trocar sua senha do GMAIL ou do HOTMAIL!
Clique acima no e-mail que voce usa e aprenda agora como trocar sua senha.

Dicas para criação de senha:

- Não utilize seu nome;
- Não use datas;
- Não use coisas muito lógicas (como o nome do seu filho/cachorro/mãe);

- Use caracteres normais e especiais;
- Use senhas aleatórias;
- Use pelo menos 8 caracteres;

Um bom jeito de criar uma senha:
- Digite qualquer coisa no teclado (com números e letras), decore e use como senha;

Obs: Para este tipo de invasão ter uma boa senha não ajuda em nada, mas quando alguém quer descobrir sua senha isso dificulta bastante.

Qualquer novidade sobre o caso estarei atualizando neste post.

Árvore Geradora em Grafos

2009-10-05T11:19:00.004-04:00

Árvore geradora

Uma subárvore de um grafo G é qualquer árvore T que seja subgrafo de G. Em outras palavras, um árvore T é subárvore de G se todo vértice de T é vértice de G e toda aresta de T é aresta de G.

Uma subárvore geradora ou árvore geradora (= spanning tree) de um grafo G é qualquer subárvore de G que contenha todos os vértices de G.

É claro que somente grafos conexos têm árvores geradoras. Reciprocamente, todo grafo conexo tem uma árvore geradora. (Em geral, um grafo conexo tem muitas árvores geradoras diferentes.)

Algoritmos que calculam árvores geradoras

É fácil calcular uma árvore geradora de um grafo conexo: a busca em profundidade e a busca em largura fazem isso. Mais precisamente, qualquer das duas buscas calcula uma arborescência que contém um dos arcos de cada aresta de uma árvore geradora do grafo.

Primeira propriedade da troca de arestas

Seja G um grafo e H um subgrafo gerador de G. Para qualquer aresta h de H, vamos denotar por H–h o grafo que se obtém quando h é removida de H. Para qualquer aresta e de G, vamos denotar por H+e o grafo que se obtém quando e é inserida em H.

Primeira Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta e de G que não esteja em T, o grafo T + e tem um único ciclo não-trivial. Para qualquer aresta t desse ciclo, o grafo T + e – t é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja e a aresta 0-1. O único ciclo não-trivial de T+e é 0-1-5-4-0. Para qualquer aresta t desse ciclo, T+e–t é uma árvore geradora.

Segunda propriedade da troca de arestas

Seja T uma árvore geradora de um grafo G. Para toda aresta t de T, as duas componentes de T–t definem um corte em G. Diremos que esse é o corte determinado por T–t. A única aresta de T que atravessa o corte é t.

Segunda Propriedade da Troca: Seja T uma árvore geradora de um grafo G. Para qualquer aresta t de T e qualquer aresta e de G que atravesse o corte determinado por T–t, o grafo T – t + e é uma árvore geradora de G.
Exemplo: Seja T a árvore geradora definida pelas cinco arestas "internas" da figura. Seja t a aresta 4-5. O corte determinado por T–t tem três arestas: 0-1, 4-5 e 3-2. Se e é uma qualquer dessas arestas então T–t+e é uma árvore geradora.

Fonte: IME

Caminhos mínimos

2009-10-05T08:07:00.001-04:00

Caminhos mínimos

Distância

Um caminho C num digrafo é mínimo se não existe outro caminho com mesma origem e mesmo término que C mas comprimento menor que o de C. É claro que todo caminho mínimo é simples.

A distância de um vértice s a um vértice t num digrafo é o comprimento de um caminho mínimo de s a t. Se não existe caminho algum de s a t, a distância de s a t é infinita. A distância de s a t é d se e somente se (1) existe um caminho de comprimento d de s a t e (2) nenhum caminho de s a t tem comprimento menor que d.

Em geral, a distância de um vértice s a um vértice t é diferente da distância de t a s. Num grafo, entretanto, as duas distâncias são iguais.

Busca em largura e distâncias

O algoritmo de busca em largura foi concebido sob medida para calcular distâncias a partir de um vértice s. Ele visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante.

int dist[maxV];
/* A função distDigrafo armazena no vetor dist a distância do vértice s a cada um dos demais vértices do digrafo G: dist[v] é a distância de s a v. Distância infinita é representada por -1.*/

void distDigrafo (int s) { 
    int v, w;
    int ini,fim;
    for (v = 0; v < n; v++) dist[v] = -1;
    ini = fim = 0;
    dist[s] = 0;
    fila[ini++] = s;
    while (ini > fim) {
       v = fila[fim++]; 
       for (w = 0; w < n; w++)
          if (g[v][w] == 1)
             if (dist[w] == -1) { 
                dist[w] = dist[v] + 1;
                fila[ini++] = w; 
             }
    }
}

No início de cada iteração, a fila consiste em

1. zero ou mais vértices à distância d de s,
2. seguidos de zero ou mais vértices à distância d+1 de s,
para algum d. Essa propriedade permite concluir que, no início de cada iteração, para todo vértice x, se dist[x] é diferente de -1 então dist[x] é a distância de s a x.

Exemplo

Considere o grafo (digrafo simétrico) definido pelo conjunto de arestas abaixo.
Represente o grafo por sua matriz de adjacência.

0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5

Agora use a função distDigrafo para calcular as distâncias a partir do vértice 0.
Eis o estado do vetor dist no início de sucessivas iterações (com "*" no lugar de "-1"):

0 1 2 3 4 5 6 7
---------------
0 * * * * * * *
0 * 1 * * 1 * 1
0 * 1 * * 1 2 1
0 * 1 2 2 1 2 1
0 2 1 2 2 1 2 1

Caminhos mínimos e arborescência de distâncias

Se acrescentar ao código de distDigrafo o cálculo de um vetor de pais pai, teremos uma representação da arborescência de busca em largura.
No presente contexto, essa árvore pode ser chamada arborescência das distâncias: para cada vértice x tal que dist[x] é diferente de -1, o único caminho de s a x na arborescência é um caminho mínimo no digrafo. O fragmento de código abaixo imprime o inverso desse caminho:

for (v = x; v != s; v = pai[v])
    printf("%d-", v)
printf("%d\n", s)

Desempenho

A função distDigrafo é linear: ela consome tempo proporcional a V2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.

A versão de distDigrafo que calcula a arborescência de distâncias também é linear.

Digrafos com custos nos arcos

Muitas aplicações associam um número a cada arco de um digrafo. Diremos que esse número é o custo da arco. Vamos supor, em geral, que esses números são do tipo double, podendo ser positivos, negativos, ou nulos. Essa associação de custos aos arcos pode ser entendida como uma função que leva o conjunto de arcos num conjunto de números.

Dependendo da aplicação, pode ser mais apropriado dizer "peso" ou "comprimento" no lugar de "custo". [Sedgewick diz weight no lugar do nosso "custo". Mas isso aumenta o número de variáveis cujo nome começa "w", o que torna os programas menos legíveis.]

Grafos com custos nas arestas

Grafos com custos nas arestas têm uma peculiaridade previsível: os dois arcos que constituem cada aresta têm o mesmo custo. O custo de uma aresta, nesse caso, é o custo de qualquer dos dois arcos que constituem a aresta.

Exercícios para Fixação

1. O código distDigrafo utiliza matriz ou lista de adjacências para representar o grafo? Implemente o mesmo código para o outro tipo de representação.
2. Como ficaria esse código com o cálculo do vetor de pais?
3. Qual é o resultado de trocarmos a bfs por dfs neste código?

Fonte: IME

Busca em Largura

2009-10-05T00:08:00.003-04:00

A busca em largura, também conhecida como busca BFS (= breadth-first search), está intimamente relacionada com o conceito de distância entre vértices. Quando aplicada a uma arborescência, a busca BFS faz uma varredura "por níveis".

BFS versus DFS

A diferença mais marcante entre a busca em largura e a busca em profundidade está na estrutura de dados auxiliar empregada por uma das estratégias e pela outra. A busca em largura usa uma fila (de vértices), enquanto a busca em profundidade usa uma pilha. (Na versão recursiva da busca em profundidade, a pilha não aparece explicitamente pois é administrada pelo mecanismo de recursão.) Mas há várias outras diferenças, mais superficiais, entre os dois algoritmos:

- na busca em profundidade, o próprio algoritmo escolhe o vértice inicial, enquanto a busca em largura começa tipicamente num vértice especificado pelo usuário;
- a busca em profundidade visita, tipicamente, todos os vértices do digrafo, enquanto a busca em largura visita apenas os vértices que podem ser atingidos a partir do vértice inicial;
- a busca em profundidade é descrita, usualmente, em estilo recursivo, enquanto a busca em largura é descrita em estilo iterativo.

O fato é que, apesar da semelhança entre a siglas, a busca DFS e a busca BFS são muito diferentes e têm aplicações muito diferentes.

Busca em largura

A busca em largura começa por um vértice, digamos s, especificado pelo usuário. O algoritmo visita s, depois visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante.

Para implementar essa idéia, o algoritmo usa uma fila de vértices. Essa fila contém todos os vértices já visitados cujos vizinhos ainda não foram visitados.

A ordem em que os vértices são visitados é registrada num vetor ordemvisit indexado pelos vértices, à semelhança do que fizemos ao estudar busca em profundidade.

#define MAXV 10000
int cnt, ordemvisit[MAXV];
int fila[MAXV];
int ini,fim;
/* A função bfsDigrafo visita todos os vértices do digrafo G que podem ser alcançados a partir do vértice s. A ordem em que os vértices são visitados é registrada no vetor ordemvisit. */

void bfsDigrafo (int s) { 
   int v, w;
   cnt = 0;
   for (v = 0; v < n; v++) ordemvisit[v] = -1;
   ordemvisit[s] = cnt++;
   ini = fim = 0;
   fila[ini++] = s; 
   while (ini > fim) {
       v = fila[fim++]; 
       for (w = 0; w < n; w++)
           if (g[v][w] == 1)
              if (ordemvisit[w] == -1) { 
                 ordemvisit[w] = cnt++; 
                 fila[ini++] = w; 
             }
   }
}

No início de cada iteração valem as seguinte propriedades: 1. todo vértice que está na fila já foi visitado; 2. se um vértice v já foi visitado mas algum de seus vizinhos ainda não foi visitado, então v está na fila. (Um vértice x já foi visitado se e somente se ordemvisit[x] é diferente de -1.) Cada vértice entra na fila no máximo uma vez. Portanto, basta que a fila tenha espaço suficiente para V vértices.

Arborescência de busca em largura

A busca em largura a partir de um vértice s descreve, implicitamente, uma arborescência com raiz s. Essa arborescência é conhecida como arborescência de busca em largura (= BFS tree). Podemos representar essa arborescência explicitamente por um vetor de pais pai.

[Muita gente diz "árvore de busca" no lugar do meu "arborescência de busca". Infelizmente, a palavra "árvore" também é usada para designar um outro conceito, o que pode causar confusão.]

No início de cada iteração, cada vértice que está na fila é uma folha da arborescência representada por pai.

Desempenho

A função bfsDigrafo é linear: ela consome tempo proporcional a V^2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.

Exercícios para Fixação

1. O código bfsDigrafo utiliza matriz ou lista de adjacências para representar o grafo?
2. Como ficaria esse código com o cálculo do vetor de pais?
3. O que a bfs faz que a dfs não pode fazer?
4. Faça um algoritmo que determine o caminho mínimo entre dois vértices usando bfs, o peso de todas as arestas é o mesmo.

Fonte: IME

Busca Google com Novas Funcionalidades

2009-10-01T14:21:00.001-04:00

Melhorias interessantes são anunciadas pela Google para o painel lateral de seu mecanismo de busca, lançado no início deste ano. No total são 9 novas funcionalidades:
publicações apenas da última hora, por um intervalo de datas específico, mais sites de compras, menos sites de compra, páginas já visitadas, páginas ainda não visitadas, livros, blogs e notícias.

Graças a isso, agora você pode, por exemplo, restringir os resultados da pesquisa para sites que foram atualizados na última hora, ou você pode dizer ao Google para ajustar o número de sites de compras que aparecem em uma página de resultados de pesquisa.

A Google irá começar a publicar essas novas funcionalidades durante o dia de hoje (01/10/2009) e pretende disponibilizar todas elas até o fim deste dia (pelo menos em inglês).

Resultados de pesquisa
Agora você poderá pesquisar apenas páginas não visitadas, para isso basta estar logado em sua conta Google e possuir histórico de web ativado.

Livros, blogs e notícias
Essa funcionalidade de pesquisa por livros e blogs já existe, mas agora você poderá filtrar suas buscas por blogs e notícias também.

Compras
Limitar o número de sites de compras talvez seja a funcionalidade mais agradável. Muitas vezes não queremos comprar nada e agora poderemos minimizar o número de sites de compras que serão apresentado:

Fonte 1

Maratona de Programação, Ao Vivo

2009-09-18T23:07:00.004-04:00

Está chegando a hora, hoje (19/09) todo Brasil estará participando da Maratona de Programação (ACM-ICPC) etapa sub-regional.

Confira a lista de Vagas previstas para a Final Brasileira!

Infelizmente esse ano em minha sede, UEMS (Dourados/MS), não temos uma vaga garantida e teremos que disputar com a UnB além da FIP Anhanguera que virá participar aqui em Dourados.

Assim que tivermos os resultados estarei divulgado aqui no blog. Mas você poderá acompanhar AO VIVO o score da sede de Dourados/MS.

A competição irá começar as 14:00 horário de Brasília. Fique ligado!

Acesso: http://200.181.125.91/boca/
Usuário e senha: score

Então fica a torcida, boa sorte a todos maratonistas (inclusive eu).

Orkut divulgando nossos eventos/vendas de graça

2009-09-18T14:09:00.003-04:00

Depois de muito tempo de espera, finalmente a funcionalidade do orkut chamada de "Promote" ou Promova em português está começando a ser disponibilizada nos perfis do Orkut.

A função do Promova que assemelha-se com o Twitter, ou mais similar até com o Yahoo! Meme onde é possível compartilhar textos longos, imagens e vídeos sendo restrito apenas as imagens hospedadas no álbum de fotos do orkut e vídeos do YouTube. Quando o conteúdo é postado, um gerenciado permite visualizar quantas pessoas visualizaram, clicaram ou promoveram, e ainda, uma escala mede o alcance que teve a sua promoção.

Confira o vídeo que explica essa nova função:

Fonte: Google Discovery

Articulações e Biconexão

2009-09-08T22:20:00.003-04:00

Aqui trataremos de grafos que deixam de ser conexos quando perdem um de seus vértices. Ela se restringe a grafos (embora o conceito também faça sentido em digrafos não-simétricos).

Articulações em grafos

Uma articulação (= articulation point) ou vértice de corte (= cut vertex) de um grafo é um vértice cuja remoção aumenta o número de componentes do grafo.

Algoritmo
código

Biconexão

Um grafo é biconexo (= biconnected) ou 2-conexo se é conexo e não tem articulações. Portanto, é preciso remover pelo menos 2 vértices de um grafo biconexo para que ele deixe de ser conexo.

Fato básico importante: Um grafo é biconexo se e somente se, para cada par (s,t) de seus vértices, existem (pelo menos) dois caminhos de s e t sem vértices internos em comum (ou seja, s e t são os únicos vértices comuns aos dois caminhos).

Exercícios para Fixação

1. Faça esse algoritmo para lista de adjacências.
2. Mostre que todo grafo biconexo é aresta-biconexo.
3. Qual o número mínimo de arestas que um grafo biconexo com V vértices deve ter?
4. Porque é importante identificar pontos de articulação? Dê uma situação prática.
5. Explique com suas palavras o que é um grafo biconexo.
6. Qual a diferença entre pontes e articulações?
7. Modifique o algoritmo acima para que ele somente diga se existe ponto de articulação ou não.

Referência: IME

Pontes em grafos e aresta-biconexão

2009-09-08T18:55:00.002-04:00

Aqui tratamos de grafos que deixam de ser conexos quando perdem uma de suas arestas. Ela se restringe a grafos, pois os conceitos discutidos não fazem sentido em digrafos não-simétricos.

Pontes em grafos

Uma aresta de um grafo é uma ponte (= bridge = separation edge) se ela é a única aresta que atravessa algum corte do grafo. [Pontes são também conhecidas com arestas de corte, mas nós não vamos usar essa terminologia.]

Em outras palavras, uma ponte é uma aresta cuja remoção aumenta o número de componentes do grafo.

Problema: Encontrar as pontes de um grafo dado.

Poderíamos aplicar cegamente a definição de ponte para resolver o problema, mas é possível fazer coisa melhor.

Pontes e busca em profundidade

É possível encontrar as pontes de um grafo de maneira muito eficiente. O ponto de partida é o seguinte fato básico: em qualquer grafo, uma aresta é uma ponte se e somente se não faz parte de um ciclo não-trivial. (Em outras palavras, toda aresta é de um e apenas um de dois tipos: ou ela é uma ponte ou pertence a um ciclo não-trivial.)

Se fizermos uma busca em profundidade no grafo, um dos dois arcos que constituem qualquer ponte será necessariamente um arco de arborescência (por que?). Agora observe a seguinte

Propriedade: Em qualquer busca em profundidade, um arco v-w da floresta DFS faz parte (juntamente com w-v) de uma ponte se e somente se não existe arco de retorno que ligue um descendente de w a um ancestral de v.
(Os descendentes e ancestrais de que trata a propriedade não são necessariamente próprios.) Para tirar proveito dessa propriedade, vamos calcular, para cada vértice v, o menor número de pré-ordem (= lowest preorder number) que pode ser alcançado a partir de v. Esse número será denotado por

menorpre[v].

Explico melhor: Digamos, só para efeito desta explicação, que um caminho é interessante se

- começa em v,
- "desce" pela arborescência de busca em profundidade,
- e finalmente percorre no máximo um arco de retorno.

(Por exemplo, todo caminho de comprimento 0 que começa em v é interessante. Outro exemplo: um caminho de comprimento 1 que começa em v e percorre um só arco de retorno é interessante.) Digamos que o valor de um caminho interessante é lbl[z], sendo z o último vértice do caminho. Então low[v] é, por definição, o valor de um caminho interessante de valor mínimo.

É claro que menorpre[v] ≤ ordemvisit[v] para todo vértice v. Digo mais: para todo arco v-w do grafo,

- se v-w é um arco de arborescência (e portanto v é pai de w) então menorpre[v] ≤ menorpre[w];
- se v-w é uma arco de retorno (e portanto ordemvisit[v] > ordemvisit[w]) então menorpre[v] ≤ ordemvisit[w].

Algoritmo das pontes

A propriedade acima pode ser reformulada assim: em qualquer floresta de busca em profundidade de um grafo, um arco de arborescência v-w faz parte de uma ponte se e somente se menorpre[w] == ordemvisit[w].

#define MAXV 100 //número máximo de vértices
int G[MAXV][MAXV]; //grafo representado por matriz de adjacência
int ordemvisit[MAXV]; //marca a ordem de visitação dos vértices
int menorpre[MAXV]; //menor o menor número de pré-ordem que pode ser alcançado a partir de v
int pai[MAXV]; //vetor de pai, pai de X é pai[X]
int n; //número de vértices neste grafo
int count; //contador
int countpontes; //contador de pontes

//A função abaixo calcula o número de pontos, countpontes, do grafo G e imprime todas as pontes
void todasPontes(){
 int v;
 for( v = 0 ; v < n ; ++v ){
  ordemvisit[v] = -1;
 }
 for( v = 0 ; v < n ; ++v ){
  if(ordemvisit[v] == -1){
   pai[v] = v;
   ponte(v);
  }
 }
}

void ponte(int v){
 int p, v;
 ordemvisit[v] = count++;
 menorpre[v] = ordemvisit[v];
 for( p = 0 ; p < n ; ++p ){
  if(ordemvisit[p] == -1){
   pai[p] = v;
   ponte(p);
   if ( menorpre[v] > menorpre[p])
    menorpre[v] = menorpre[p];
   if ( menorpre[p] == ordemvisit[p]){
    countpontes++;
    printf("%d-%d\n", v, p);
   }
  }
  else if( p != pai[v] && menorpre[v] > ordemvisit[p] )
   menorpre[v] = ordemvisit[p];
 }
}

O teste "if (p != pai[v])" garante que v-w é um arco de retorno (e não um arco-pai).

A função todasPontes é linear: ela consome tempo proporcional a V+E. A variante dessa função para matrizes de adjacência consome tempo proporcional a V².

Aresta-biconexão

Um grafo é aresta-biconexo (= edge-connected) ou 2-aresta-conexo se for conexo e não tiver pontes. Portanto, é preciso remover pelo menos duas arestas de um grafo aresta-biconexo para que ele deixe de ser conexo.

Fato básico importante: Um grafo é aresta-biconexo se e somente se, para cada par (s,t) de seus vértices, existem (pelo menos) dois caminhos de s a t sem arestas em comum.

Uma componente aresta-biconexa (= edge-connected component) de um grafo é qualquer componente do grafo que se obtém depois que todas as pontes são removidas.

Exercícios para Fixação

1. Mostre que todas as arestas de qualquer floresta são pontes. A recíproca é verdadeira?
2. Escreva uma função que calcule menorpre[v] para cada vértice v de um grafo dado.
3. Diga o que a função ponte faz.
4. Execute a função todasPontes para encontrar as pontos dos grafos da figura abaixo:

5. Escreva uma função que receba um grafo G e devolva 1 se o grafo é aresta-biconexo e devolva 0 em caso contrário. (Sugestão: modifique os códigos já apresentados nesta aula)
6. Qual o número mínimo de arestas de um grafo aresta-biconexo que tem V vértices?

Referência: IME

Conexão: digrafos conexos

2009-09-08T18:37:00.000-04:00

A grosso modo, um digrafo é conexo se for "união disjunta" de dois digrafos menores. A definição precisa do conceito depende da idéia de corte. No caso de grafos (ou seja, digrafos simétricos), a caracterização da conexão envolve a idéia de caminho.

Cortes

Um corte (= cut) de um digrafo é uma bipartição do conjunto de vértices do digrafo. Em outras palavras, um corte é um par de conjuntos de vértices, ambos não-vazios, tal que todo vértice do digrafo pertence a um e apenas um dos conjuntos do par.

Dado um corte (X,Y) de um digrafo, dizemos que um arco pertence ao corte, ou atravessa o corte, se tiver uma ponta em X e outra em Y. Um corte é vazio se não for atravessado por nenhum arco.

Digrafos conexos

Um digrafo é fracamente conexo (= weakly connected) se não tem cortes vazios. [A propósito, o conceito de digrafo fortemente conexo é mais complexo e será discutido em outra ocasião.] Portanto, um digrafo é fracamente conexo se, para toda bipartição (X,Y) de seu conjunto de vértices, algum arco tem uma ponta em X e outra em Y.

Grafos conexos

O conceito de conexão é particularmente importante em digrafos simétricos. Nesse caso, o "fracamente" é omitido: se um grafo não tem cortes vazios, dizemos simplesmente que ele é conexo (= connected). Assim, se X é um conjunto de vértices de um grafo conexo G então alguma aresta de G tem uma ponta em X e outra fora de X, a menos que X seja vazio ou contenha todos os vértices de G.

Referência: IME

Grafos bipartidos e ciclos ímpares

2009-09-06T16:24:00.001-04:00

Aqui tratamos de grafos bipartidos, uma espécie simples, mas muito útil de grafos.

Bipartição

Um grafo é bipartido (= bipartite) se existe uma bipartição do seu conjunto de vértices tal que cada aresta tem uma ponta em uma das partes da bipartição e a outra ponta na outra parte.

Outra maneira de formular a definição: um grafo é bipartido se for possível atribuir uma de duas cores a cada vértice de tal forma que as pontas de cada aresta tenham cores diferentes.

Um grafo bipartido:

Ciclos ímpares

É fácil verificar que grafos que têm ciclos de comprimento ímpar não são bipartidos. É um pouco mais difícil provar que:
todo grafo sem ciclos ímpares admite bipartição.

A função abaixo (junto com a prova de sua correção) constitui uma prova dessa fato fundamental.

A estrutura da função é de uma busca em profundidade.

int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
int cor[MAXV];

//A função devolve 1 se o grafo  G é bipartido e devolve 0 em caso contrário. Além disso, se G é bipartido, a função atribui uma "cor" a cada vértice de G de tal forma que toda aresta tenha pontas de cores diferentes. As cores dos vértices, 0 e 1, são registradas no vetor cor indexado pelos vértices. 
int coloreGrafo(){
 int v;
 int c = 0; //representa a "cor"
 for( v = 0 ; v < n ; ++v ) cor[v] = -1;
 for( v = 0 ; v < n ; ++v )
  if(cor[v] == -1)
   if(dfsCor(v, 0) == 0) return 0;
 return 1;
}

int dfsCor(int v, int c){
 int p;
 cor[v] = 1-c; //???
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && cor[p] == -1){ //existe aresta e ainda não tem cor
   if(dfsCor(p,1-c) == 0) return 0;
  }
  else if (cor[p] == 1-c) return 0;
 }
 return 1;
}

Exercícios para Fixação

1. O que faz esta linha: "cor[v] = 1-c"?
2. Quais dos dois grafos abaixo são bipartidos? Para o grafo bipartido mostre as duas partições!
a) 0-1 1-2 2-3 3-0 0-4 4-5 5-2
b) 0-1 1-2 2-3 3-0 4-6 0-5 5-2
3. Diga o que a função dfsCor faz.
4. Mostre que se a função coloreGrafo devolve 0 então G tem um ciclo de comprimento ímpar.
5. Escreva essas duas funções para um grafo representando por lista de adjacências.
6. Execute o algoritmo coloreGrafo e mostre os principais passos para o grafo a seguir:

Referência: IME

Florestas e árvores

2009-09-06T14:58:00.002-04:00

Uma árvore é o grafo que se obtém quando acrescentamos um arco anti-paralelo a cada arco de uma arborescência. Embora correta, essa caracterização de árvores não é conveniente como definição. É melhor adotar uma definição mais tradicional.

O primeiro passo da definição introduz um outro tipo de grafo: a floresta.

Florestas

Uma floresta (= forest) é um grafo sem ciclos não-triviais.

Para cada arco v-w da floresta, o caminho v-w-v é um ciclo, mas esse ciclo é trivial.

Por exemplo, o grafo definido pelo conjunto de arestas abaixo é uma floresta.
0-1 0-5 1-2 1-3 1-4 6-7 6-8

Florestas também são conhecidas como grafos acíclicos. Uma folha (= leaf) de uma floresta é qualquer vértice de grau 1.

Árvores

Uma árvore (= tree) é uma floresta conexa. Portanto, cada componente de uma floresta é um árvore.

Por exemplo, o grafo definido pelo conjunto de arestas 0-1 0-5 1-2 1-3 1-4 é uma árvore.

Não confunda árvores com arborescências. Uma árvore é um digrafo simétrico, enquanto uma arborescência é um digrafo não-simétrico. As palavras "raiz", "pai" e "filho" não fazem sentido numa árvore.

Propriedade 1: Para cada par s,t de vértices de uma árvore existe um e um só caminho simples de s a t.
Propriedade 2: Toda árvore com V vértices tem exatamente V-1 arestas.

Exercícios para Fixação
1. Essa afirmação está correta: "Toda árvore com V vértices tem exatamente V-1 arestas."? Porque?
2. Mostre que toda floresta com V vértices e C componentes tem exatamente V-C arestas.
3. Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas.
4. Escreva uma função que reconheça florestas. Ao receber um grafo G, a função deve devolver 1 se G é uma floresta e devolver 0 em caso contrário.
5. Escreva uma segunda versão para a função do exercício anterior, que imprima um ciclo não-trivial imediatamente antes de devolver 0.
6. Escreva uma função que reconheça árvores. Ao receber um grafo G, a função devolve 1 se G é uma árvore e devolve 0 em caso contrário.

Referência: IME

Ciclos em grafos e digrafos

2009-09-06T14:35:00.002-04:00

Ciclos são caminhos fechados quase simples de comprimento pelo menos 2. Em grafos, os ciclos de comprimento 2 não são considerados "válidos".

Ciclos

Um ciclo (= cycle) num digrafo é um caminho fechado de comprimento pelo menos 2, sem vértices repetidos, exceto o último (que coincide com o primeiro).

Dizemos que um arco v-w pertence a um dado ciclo se o vértice w é o sucessor de v no ciclo. Todos os arcos de um ciclo apontam no mesmo sentido, de um vértice do ciclo para o seu sucessor. Há quem goste de enfatizar esse fato dizendo "ciclo dirigido" em lugar do nosso "ciclo".

No digrafo 0-1 0-5 1-0 1-5 2-4 3-1 5-3, os caminhos

a) 1-5-3-1
b) 0-1-0
são ciclos. Já os caminhos abaixo, embora fechados, não são ciclos:

a) 1-5-3-1-0-1
b) 1

Ciclos em grafos

Um ciclo é trivial se tem comprimento 2. Num grafo, ciclos triviais são ignorados, pois usam os dois arcos de uma mesma aresta.

Procurando ciclos: primeiro algoritmo

A seguinte função implementa uma maneira óbvia mas pouco eficiente de encontrar um ciclo num digrafo. A idéia é procurar, para cada arco v-w, um ciclo que passe por v-w.

//Devolve 1 se tem ciclo no digrafo G, devolve 0 caso contrário.
int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
int cicloDigrafo(){
 int v, dest, saida;
 for( v = 0 ; v < n ; ++v ){
  for( dest = 0 ; dest < n ; ++dest ){
   if( G[v][dest] == 1 && Path(dest,v)){
    return 1;
   }
  }
 }
 return 0;
}

A função Path no código acima está implementada no artigo de caminhos em digrafos. A função análoga para grafos é bem mais complexa porque é preciso evitar os ciclos triviais.

int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
//A função a seguir remove uma Aresta
void removeAresta(int o,int d){
 G[o][d] = 0;
}

//A função a seguir insere uma Aresta
void insereAresta(int o,int d){
 G[o][d] = 1;
}

//A função a seguir devolve 1 se existe um ciclo não-trivial no grafo G, caso contrário devolve 0.
int cicloGrafo(){
 int v, w;
 int dest;
 int saida;

 for( v = 0 ; v < n ; ++v ){
  for( dest = 0 ; dest < n ; ++dest ){
   if( G[v][dest] == 1 ){
    if ( v < dest ){
     removeAresta(dest,v);
     saida = Path(dest,v);
     insereAresta(dest,v);
     if(saida == 1)
      return 1;
    }
   }
  }
 }
 return 0;
}

Procurando ciclos: algoritmo eficiente A estratégia da busca em profundidade permite encontrar ciclos de maneira muito eficiente.

O algoritmo abaixo tem por base a seguinte observação: em relação a qualquer floresta de busca em profundidade:

todo arco de retorno pertence a um ciclo e todo ciclo tem um arco de retorno. Função para Digrafos:

#define MAXV 100 //número máximo de vértices
int G[MAXV][MAXV]; //grafo representado por matriz de adjacência
int ordemvisit[MAXV]; //marca a ordem de visitação dos vértices
int n; //número de vértices neste grafo
int count; //contador

//A função abaixo devolve 1 se o digrafo G tem um ciclo, 0 caso contrário
int cicloDigrafo(){
 int v;
 for( v = 0 ; v < n ; ++ v )
  ordemvisit[v] = -1;
 count = 0;
 for( v = 0 ; v < n ; ++ v )
  if( ordemvisit[v] == -1 )
   if(cicloR(v) == 1)
    return 1;
 return 0;
}

//A função abaixo devolve 1 quando encontra um ciclo ao percorrer G a partir de v
int cicloR(int v){
 int p;
 ordemvisit[v] = count++;
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && ordemvisit[p] == -1){
   if(cicloR(p) == 1) return 1;
  }
  else if(ordemvisit[p] < ordemvisit[v]) return 1;
 }
 return 0;
}

A função cicloGrafo abaixo procura ciclos não-triviais em grafos. Para evitar ciclos triviais, a função precisa ter acesso à floresta DFS.

#define MAXV 100 //número máximo de vértices
int G[MAXV][MAXV]; //grafo representado por matriz de adjacência
int ordemvisit[MAXV]; //marca a ordem de visitação dos vértices
int pai[MAXV]; //vetor de pai, pai de X é pai[X]
int n; //número de vértices neste grafo
int count; //contador

//A função abaixo devolve 1 se o grafo G tem um ciclo não-trivial, 0 caso contrário
int cicloGrafo(){
 int v;
 for( v = 0 ; v < n ; ++ v )
  ordemvisit[v] = -1;
 count = 0;
 for( v = 0 ; v < n ; ++ v ){
  if( ordemvisit[v] == -1 ){
   pai[v] = v;
   if(ciclo3R(v) == 1)
    return 1;
  }
 }
 return 0;
}

//A função abaixo devolve 1 quando encontra um ciclo não-trivial ao percorrer G a partir de v
int cicloR(int v){
 int p;
 ordemvisit[v] = count++;
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && ordemvisit[p] == -1){
   pai[p] = p;
   if(cicloR(p) == 1) return 1;
  }
  else if(ordemvisit[p] < ordemvisit[v] && p != pai[v]) 
   return 1;
 }
 return 0;
}

Exercícios para Fixação
1. Escreva uma função que conte o número de ciclos em um grafo.
2. Escreva o algoritmo eficiente para digrafos usando lista de adjacências.
3. Escreva o algoritmo eficiente para grafos usando lista de adjacências.
4. Execute o algoritmo cicloDigrafo eficiente e marque os principais passos para o digrafo da figura:

5. Execute o algoritmo cicloGrafo eficiente e marque os principais passos para o grafo da figura:

6. Escreva a função removeAresta para lista de adjacências
7. Escreva a função insereAresta para lista de adjacências

Referência: IME