Distância (teoria dos grafos)

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
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[editar | editar código-fonte]

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 é conectado.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 vi e vj que é igual ao número de arestas(ligações) considerando-se o menor caminho que conecte vi e vj[6] .

Referências

  1. Distâncias. Visitado em 2010-11-05.
  2. SZWARCFITER, Jayme Luiz. Grafos e algoritmos computacionais. Rio de Janeiro: Campus, 1988. p. 39. ISBN 85-7001-341-8
  3. BOUTTIER, Jérémie;DI FRANCESCO,P.; GUITTER, E.. (Julho 2003). "Geodesic distance in planar graphs". Nuclear Physics B 663 (3): 535–567. DOI:10.1016/S0550-3213(03)00355-9.
  4. WEISSTEIN, Eric W.. Graph Geodesic Wolfram Research.
  5. a b Caminhos mínimos. Visitado em 2010-11-05.
  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. Visitado em 2010-11-05.