Distância (teoria dos grafos)
comprimento do caminho mais curto entre dois nós de um grafo / De Wikipedia, a enciclopédia encyclopedia
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]