Music that makes me happy.
From the movie “Mary and Max”, highly recommended.
Month: June 2010
Sobre equações diofantinas
Motivado pelo seguinte problema: http://ipsc.ksp.sk/contests/ipsc2010/real/problems/d.php
A minha modelagem pra esse problema chegou em uma quatro equações do tipo:
ax + by = c
No final das contas eu tinha que saber se essa equação tinha solução pra decidir quem ganhava a luta: o príncipe ou o dragão. E então? Como eu sei se uma equação dessa tem soluções inteiras?
Acontece que essa é uma equação diofantina linear, e ela só tem solução se c é o mdc(a, b) ou múltiplo do mdc(a, b). Bom resultado pra se lembrar.
Sobre grafos bipartidos
Uma rede de computadores pode ser facilmente representada por um grafo, no qual cada máquina representa um vértice e arestas são conexões entre essas máquinas. Nesse grafo, cada vértice possui um label que seria o endereço da máquina na rede. Mas esses labels podem ser mais que endereços, eles podem refletir diretamente a distância entre os vértices (máquinas). Em uma rede cujo endereçamento segue essa regra, o roteamento de pacotes pode ser feito de maneira ótima analisando somente informações locais (incrível, hein?? =P ). Basta fazer o seguinte: um pacote sabe sempre seu endereço de destino, quando ele alcança um vértice ele compara esse endereço com os vizinhos desse vértice e vai para o que está mais próximo do seu objetivo. Simples.
Um grafo que obviamente satisfaz essa propriedade é n-cubo. Nele, a distância entre os vértices é exatamente a distância Hamming (ou distância de edição) entre as sequências de bits atribuídas a cada vértice. Para construir uma rede dessa maneira (na qual os pacotes percorrem sempre o caminho ótimo) devemos saber que tipo de grafo pode ter seus vértices endereçados com strings de bits de modo que a distância de Hamming corresponda à distância entre os vértices no grafo.
Teorema (Djokovic – 1973):
Existe um esquema de endereçamento usando strings de binárias para os vértices de um grafo simples G tal que a distância Hamming das strings coincide com a distância dos vértices no grafo se, e somente se:
(i) G é bipartido.
(ii) G(a,b) é um conjunto fechado para toda aresta (a,b) em A(G).
OBS: G(a,b) = {x em V(G) | d(x,a) = d(x,b)-1}
Um subconjunto de vértices U de V(G) é dito fechado se para todo par a,b em U: x em V(G) e d(a,x) + d(b,x) = d(a,b) então x está em U.