Gráficos em que todos os caminhos mais curtos são únicos

22

Estou procurando gráficos não direcionados, não ponderados, conectados , nos quais, para cada par , existe um único caminho que realiza a distância .G=(V,E)você,vVvocêvd(você,v)

Essa classe de gráficos é bem conhecida? Que outras propriedades possui? Por exemplo, toda árvore é desse tipo, assim como todo gráfico sem um ciclo par. No entanto, existem gráficos contendo ciclos pares desse tipo.

László Kozma
fonte

Respostas:

25

De acordo com o Sistema de Informação sobre Classes de Gráficos e suas Inclusões, esses gráficos são estudados sob o nome " gráficos geodésicos ".

Tsuyoshi Ito
fonte
10

Esses gráficos são de fato geodésicos. Um gráfico é bigeodético, se houver no máximo dois caminhos mais curtos entre qualquer par de vértices. Em geral, um gráfico é -ododético se houver no máximo caminhos mais curtos entre qualquer par de vértices.kk

Outro exemplo de um gráfico geodésico é um gráfico de blocos. Um gráfico é um gráfico de blocos se puder ser construído a partir de uma árvore, substituindo cada aresta por uma clique. Equivalentemente, isso é conhecido como gráfico de acordes sem diamantes. Um diamante é um menos uma aresta. Por exemplo, consulte o Teorema 1.1 em Le, Van Bang e Nguyen Ngoc Tuy. "O quadrado de um gráfico de blocos." Discrete Mathematics 310.4 (2010): 734-741.K4

Juho
fonte