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.

[1] Bipartite Graphs and their Applications (Cambridge Tracts in Mathematics) – Armen S. Asratian