Szukam nieukierunkowanych, nieważonych połączonych wykresów , w których dla każdej pary u , v ∈ V istnieje unikalna ścieżka u → v, która realizuje odległość d ( u , v ) .
Czy ta klasa grafów jest dobrze znana? Jakie inne właściwości ma? Na przykład każde drzewo jest tego rodzaju, a także każdy wykres bez równego cyklu. Istnieją jednak wykresy zawierające nawet takie cykle.
Odpowiedzi:
Zgodnie z systemem informacyjnym dotyczącym klas grafów i ich inkluzji wykresy te są badane pod nazwą „ grafy geodezyjne ”.
Takie wykresy są rzeczywiście geodezyjne. Wykres jest bigeodetyczny, jeśli istnieją co najwyżej dwie najkrótsze ścieżki między dowolną parą wierzchołków. Ogólnie wykres jest geodezyjny, jeśli istnieje co najwyżej k najkrótszych ścieżek między dowolną parą wierzchołków.
Innym przykładem wykresu geodezyjnego jest wykres blokowy. Wykres jest wykresem blokowym, jeśli można go zbudować z drzewa, zastępując każdą krawędź kliką. Odpowiednio jest to znane jako wykres akordowy bez diamentów. Diament to minus krawędź. Na przykład patrz Twierdzenie 1.1 w Le, Van Bang i Nguyen Ngoc Tuy. „Kwadrat wykresu blokowego”. Discrete Mathematics 310.4 (2010): 734–741.