Distância (teoria dos grafos)

No campo da matemática da teoria dos grafos, a distância entre dois vértices em um grafo é o número de arestas em um caminho mínimo conectando eles. Em outras palavras, denomina-se distância d(v, w) de um grafo como sendo o comprimento do menor caminho entre v e w. Isso também é conhecido como distância geodésica porque é o comprimento do grafo geodésico entre os dois vértices. A distância entre dois vértices v1 e v2 é d se e somente se existe um caminho de comprimento d de v1 a v2 e nenhum caminho de v1 a v2 tem comprimento menor que d. Se não existe caminho algum conectando dois vértices, ou seja, se eles pertencem a diferentes componentes conectados, então convencionalmente a distância entre eles é definida como infinita.

No grafo não orientado acima a distância d(1, 3) entre os vértices 1 e 3 é 2. A distância d(1, 7) entre os vértices 1 e 7 é 3.

Definições

O conjunto de vértices (de um grafo não-orientado) e a função de distância formam um espaço métrico, se e somente se o grafo é conexo.

Uma métrica definida sobre um conjunto de pontos em função das distâncias em um grafo definido sobre o conjunto é chamada uma métrica de grafo.

Medidas definidas em termos de distância

Há uma série de outras medidas definidas em termos de distância:

• A excentricidade $\epsilon$ de um vértice $v$ é a maior distância geodésica entre $v$ e qualquer outro vértice. Ela pode ser pensada como o quanto um nó é distante do nó mais distante dele no grafo.

• O raio de um grafo é a excentricidade mínima de qualquer vértice do grafo.

• O diâmetro de um grafo é a excentricidade máxima de qualquer vértice do grafo. Ou seja, ele é a maior distância entre qualquer par de vértices. Para achar o diâmetro de um grafo, primeiro encontre o caminho mínimo entre cada par de vértices. O maior comprimento de qualquer um desses caminhos é o diâmetro do grafo.

• Um vértice periférico em um grafo de diâmetro $d$ é aquele que dista de d de algum outro vértice, isto é, um vértice que alcança o diâmetro.

• Um vértice pseudo-periférico $v$ tem a propriedade que para qualquer vértice $u$, se $v$ é tão longe quanto possível de $u$, então $u$ é tão longe quanto possivel de $v$. Formalmente, se a distância de $u$ a $v$ é igual à excentricidade de $u$, então é igual à excentricidade de $v$.

Algoritmo para encontrar vértices pseudo-periféricos

Muitas vezes algoritmos de matrizes esparsas periféricas precisam de um vértice de partida com uma grande excentricidade. Um vértice periférico seria perfeito, mas é muitas vezes difícil de calcular. Na maioria dos casos um vértice pseudo-periférico pode ser utilizado. Um vértice pseudo-periférico pode ser facilmente encontrado com o seguinte algoritmo:

1. Escolha um vértice $u$.
2. Entre todos os vértices que estão distantes de $u$ o quanto possível, faça $v$ ser aquele com grau mínimo.
3. Se $\epsilon (v)>\epsilon (u)$ então faça u=v e repita o passo 2, senão $v$ é um vértice pseudo-periférico.

Aplicações

Existem numerosas aplicações na teoria dos grafos nas quais se considera o conceito de distância:

• O índice de Wiener foi introduzido em 1947, sendo o primeiro índice de grafo introduzido na química. Em seu cálculo utiliza a distância entre dois átomos i e j, que é dada pela distância entre os vértices v_i e v_j que é igual ao número de arestas(ligações) considerando-se o menor caminho que conecte v_i e v_j.