Distância (teoria dos grafos)

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.

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.^[1] Em outras palavras, denomina-se distância d(v, w) de um grafo como sendo o comprimento do menor caminho entre v e w.^[2] Isso também é conhecido como distância geodésica^[3] porque é o comprimento do grafo geodésico entre os dois vértices.^[4] 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.^[5] 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.^[5]

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 ${\displaystyle \epsilon }$ de um vértice ${\displaystyle v}$ é a maior distância geodésica entre ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle v}$ tem a propriedade que para qualquer vértice ${\displaystyle u}$, se ${\displaystyle v}$ é tão longe quanto possível de ${\displaystyle u}$, então ${\displaystyle u}$ é tão longe quanto possivel de ${\displaystyle v}$. Formalmente, se a distância de ${\displaystyle u}$ a ${\displaystyle v}$ é igual à excentricidade de ${\displaystyle u}$, então é igual à excentricidade de ${\displaystyle 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 ${\displaystyle u}$.
2. Entre todos os vértices que estão distantes de ${\displaystyle u}$ o quanto possível, faça ${\displaystyle v}$ ser aquele com grau mínimo.
3. Se ${\displaystyle \epsilon (v)>\epsilon (u)}$ então faça u=v e repita o passo 2, senão ${\displaystyle 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.^[6]

Referências

1. «Distâncias». Consultado em 5 de novembro de 2010 
2. SZWARCFITER, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. p. 39. ISBN 85-7001-341-8 
3. BOUTTIER, Jérémie;DI FRANCESCO,P.; GUITTER, E. (2003). «Geodesic distance in planar graphs». Nuclear Physics B. 663 (3). pp. 535–567. doi:10.1016/S0550-3213(03)00355-9. Consultado em 23 de abril de 2008. Pela distância que quero dizer aqui distância geodésica ao longo do grafo, ou seja, o comprimento de qualquer caminho mínimo entre, digamos, duas faces dadas  !CS1 manut: Nomes múltiplos: lista de autores (link)
4. WEISSTEIN, Eric W. «Graph Geodesic». MathWorld--A Wolfram Web Resource. Wolfram Research. Consultado em 23 de abril de 2008. O comprimento do grafo geodésico entre esses pontos d (u, v) é chamado a distância do grafo entre u e v 
5. «Caminhos mínimos». Consultado em 5 de novembro de 2010 
6. SILVA, Lucicleide Ribeiro da; FERREIRA, Márcia M. C. «Estudo do coeficiente de partição octanol-água de bifenilas policloradas (PCBs) utilizando parâmetros topológicos». Consultado em 5 de novembro de 2010  !CS1 manut: Nomes múltiplos: lista de autores (link)