(para os meus leitores imaginários não computeiros, se você for computeiro pode pular essa parte e procurar os próximos parênteses)
A definição matemática de grafo é algo que vai além do escopo de qualquer blog, por mais que esse blog pertença a alguém que se acha intelectual. Então vamos direto ao ponto, aos pontos:
um grafo é um conjunto de coisas que chamamos vértices e linhas que ligam esses vértices. num papel representamos os vértices por pontos ou bolinhas e quando faz alguma diferença qual vértice está onde, colocamos "nomes" nos vértices.
A grande utilidade disso é a versatilidade: se imaginarmos os vértices como pessoas e as arestas como amizade, temos o orkut um exemplo explícito de grafo. ou ainda pode-se tomar estações de ônibus como vértices e linhas de ônibus como arestas.
(/para os meus leitores imaginários não computeiros.)
Numa primeira aproximação grotesca dos relacionamentos, temos os humanos como vértices e arestas entre qualquer par de humanos que acham um ao outro atraentes. O algoritmo de quem programou a terra seria escolher um número x de arestas tal que o máximo de humanos tivesse em exatamente uma aresta escolhida. Como uma simplificação inicial, todos os vértices são heterossexuais. (essa simplificação será removida em uma aproximação futura, não tenho preconceitos contra homossexuais) Esse problema já tem solução conhecida. Mas, ao invés de descrever como ensinar (programar) um computador para calcular isso, vou mostrar um jeito prático de "construir" a solução numérica (quantas arestas foram escolhidas) :
Represente os humanos por reservatórios fechados de água. Separe os em homens e mulheres. Represente as arestas por canos todos de mesmo diâmetro. Adicione mais dois reservatórios abertos, um "Origem" que se liga a todos os homens (ou mulheres, é simétrico) com tubos do mesmo diâmetro anterior, e um "Destino" que se liga a todas as mulheres. Ao se despejar uma vazão de água em Origem, uma vazão limitada pelos diâmetros dos canos irá sair em Destino e assim pode-se determinar que a quantidade de arestas escolhidas é igual à vazão que sai em Destino dividido pela vazão máxima de um dos canos. (para os computeiros: Esse algoritmo roda em O(n3), com n=6x109, demoraria 7x1012 anos para se chegar à resposta em um computador pessoal)
Nesse exemplo, as leis físicas forçam as escolhas de arestas, mas como o programador faz com que certas pessoas escolham umas arestas em vez de outras? uma resposta bem simplória seria que ele faz as pessoas gostarem e deixar de gostar quando é conveniente trocar uma aresta.
Agora vamos remover as simplificações... Considere um conjunto de vértices que têm arestas entre si sem nenhuma restrição. (não faz mais sentido separar em homens e mulheres pois há arestas ligando elementos do mesmo grupo.) Agora esse algoritmo não funciona mais, pois não tem como definir uma origem e um destino. Outra complicação dos humanos é que alguns vértices podem ter mais de uma aresta, dependendo de a quais outros vértices ele está ligado e isso perde completamente qualquer analogia com fluxo em canos. Esse problema agora sem as devidas simplificações é classificado como NP-Completo o que para os computeiros significa que não existe (ainda?) como resolvê-lo em tempo polinomial e para os não computeiros significa que ele pode ser interpretado como qualquer outro que também seja NP-Completo. Assim, um ser de outro planeta pode estar usando a terra e sua imensa capacidade de processamento (milhares de relacionamentos iniciam e terminam todos os dias) para calcular a sua rota de viagens, ou quem sabe Deus quis contar quantas cores ia precisar pra pintar todos os planetas. (para os computeiros: O único jeito que conheço de calcular isso seria tentar todos os conjuntos de arestas e verificar qual deles tem o máximo de arestas e satisfaz todas as condições. O(2M*N), sendo M o número de arestas e N o número de vértices, não tenho nem como estimar quanto tempo isso demoraria num computador pessoal.
)
Nenhum comentário:
Postar um comentário