Google 2.0

A Google, apesar de seus muitos produtos (nem todos de sucesso), possui o seu mecanismo de busca ainda como seu carro chefe. Recentemente, a Google anunciou o seu novo projeto que pretende mudar a forma pela qual o seu algoritmo de buscas funciona.

O novo conceito de buscas da gigante se baseará no chamado knowledge graph. O intuito desse  novo sistema é não apenas usar como critério de seleção, na sua gigante base de dados, o termo informado pelo usuário, mas também a relação que este termo possui com outros termos/objetos ou, tecnicamente falando,com outros itens parte deste imenso grafo.

Basicamente o novo sistema objetiva obter um resultado de busca mais humano a partir de um tema. Sendo assim, a partir do tema Clarice Lispector, teriam resultados relacionados a pessoa e resultados relacionados as suas obras e características de sua obra, tendo assim uma busca mais ágil e intuitiva. Isto é apenas um exemplo simples das facilidades e de novas perspectivas.

O projeto de implementação do novo algoritmo passará por 3 etapas. A primeira seria eliminar resultados ambiguos que podem ser retornados. Desta forma, a pesquisar por São Paulo a Google perguntaria se o termo a ser pesquisado seria sobre a cidade ou o time com mesmo nome.

A segunda etapa seria mostrar alguns resultados resumo sobre o termo pesquisado como, por exemplo, data de nascimento, local e outros dados bibliográficos ao pesquisar sobre um autor, por exemplo.

A última etapa, seria efetivamente implementar o resultado do novo algoritmo com a nova busca em novo grafo formado pelas interligações entre o termo e de termos relacionados.

Google 2.0 e uma reformulação no sistema de buscas ou mais um projeto de nem tão sucesso e revolução da Google?2 A questão diferente dessa vez, é que não é uma simples nova aventura da Google mais sim uma alteração e projeto envolvendo o seu core principal: seu serviço de busca.

O Princípio da Casa dos Pombos – Aplicação em Grafos

Estava relendo o excelente artigo “O Princípio da Casa dos Pombos“, publicado pelo Reston aqui no blog e me lembrei de um problema em grafos que pode ser provado matemáticamente, de forma bastante elegante, utilizando-se este princípio.

Antes de falar sobre o problema, vamos primeiro recordar brevemente algumas definições sobre grafos (para maiores detalhes, existe um artigo que explora estas definições mais profundamente aqui):

Um grafo é um par ordenado (V,A), onde V e A são conjuntos disjuntos e cada elemento de A corresponde a um par não-ordenado de elementos (não necessariamente distintos) de V. Os elementos do conjunto V são chamados vértices e os elementos do conjunto A são chamados arestas.

Se G é um grafo, então denotamos seu conjunto de vértices por V(G), e o seu conjunto de arestas por A(G).

Além disso, vamos nos recordar brevemente do que é o princípio da casa dos pombos:

Imagine que você está sentado em um banco de praça, num belo domingo ensolarado. A certa altura, você percebe, e começa a contar, o número de pombos que está procurando comida na sua frente. Ao todo, você conta 10 pombos. Entretanto, uma motocicleta passa em alta velocidade e, com o barulho feito, assusta os dez pombos que voam para um pombal com 9 casas. Eles entram e se escondem por lá.

Sabendo que nenhum pombo desviou a direção, o que você pode concluir? Bem, se dez pombos entraram em 9 casas, podemos concluir que em pelos menos 1 casa esconderam-se 2 pombos!

Agora que refrescamos alguns princípios em nossa mente, vamos falar sobre o problema, que se resume a uma simples pergunta: “É verdade que todo grafo com pelo menos dois vértices tem dois vértices com o mesmo numero de vizinhos?”

A resposta é: Sim.

Prova por contradição: Suponha que exista um grafo G, com vértices {v1,v2,… vn}, tal que, os graus dos vértices em G sejam da seguinte forma: d(vn) = (n – 1), d(vn-1) = (n – 2), … , d(v1) = 0. Ora, isso é um absurdo, pois se d(vn) = (n – 1), vn tem vizinhança com todos os vértices em G, e, portanto v1 não pode ter grau 0.

Prova: todo grafo completo é conexo

Como vimos antoriormente (“Uma introdução à teoria dos grafos – Parte 1” e “Grafos – Algoritmo do Caminho Mínimo“), Grafos são estruturas muito interessantes para resolução de problemas, pois muitos destes podem ser reduzidos a um problema de grafos – como abordado no artigo “O uso da abstração para a resolução de problemas – Redutibilidade“.

Entretanto, os grafos, como estrutura, podem ser estudados teoricamente como um assunto próprio, separado de todos os demais. E esta é a proposta deste artigo.

Vamos começar com uma deinição simples: um grafo G é dito conexo se existe um caminho entre dois vértices u e v quaisquer. Em outras palavras, um grafo é conexo se não existe nenhum vértice com grau menor que um.

Agora, vamos partir para a diversão matemática. Primeiro, vamos provar, usando a técnica de contradição, que todo grafo completo é conexo.

As provas por contradição, apesar de não serem vistas com bons olhos por muitos matemáticos, são muito divertidas de se fazer e uma das minhas técnicas favoritas. Bom, mãos a obra:

Prova por contradição:

Suponha que exista um grafo G completo que seja desconexo.

Como G é completo, sabemos que possui pelo menos um vértice v com d(v) = n – 1. Sendo assim, não pode existir um outro vértice v com d(v) < 1, o que é uma contradição.

Fácil não? Vamos agora partir pra uma um pouco mais desafiadora: Mostrar que todo caminho é um
grafo conexo. Mais uma vez irei uma prova por contradição.

Suponha que existe um caminho C desconexo. Sejam v0 e vi os vértices nas extremidades de C. Como C é desconexo, então, partindo de v0 deve existir uma trilha que chega até um vértice u, onde d(u) = 0 e, partindo de u, chega até vi. Isto é um absurdo, pois um vértice u com d(u) = 0 não pode fazer parte de nenhum caminho.

Tão fácil quanto a outra, certo? A prova acima também pode ser aplicada para ciclos, bastaria que v0 = vi.

Agora, fica aqui o desafio: como transformar estas provas em um algoritmo eficiente para determinar se um grafo é conexo ou desconexo? (Não vale apelar para a força bruta, não é eficiente!).