Wykres unipatyczny jest wykresem ukierunkowanym, tak że istnieje co najwyżej jedna prosta ścieżka z jednego wierzchołka do dowolnego innego wierzchołka.
Wykresy unipatyczne mogą mieć cykle. Na przykład podwójnie połączona lista (nie okrągła!) Jest grafem unipatycznym; jeśli lista zawiera elementów, wykres ma cykli o długości 2, w sumie .n - 1 2 ( n - 1 )
Jaka jest maksymalna liczba krawędzi na wykresie unipathic z wierzchołkami? Zrobiłoby to asymptotyczne wiązanie (np. lub ).O ( n ) Θ ( n 2 )
Zainspirowany przez Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym ; w moim dowodzie początkowo chciałem twierdzić, że liczba krawędzi wynosi ale potem zdałem sobie sprawę, że ograniczenie liczby cykli było wystarczające.
graphs
combinatorics
Gilles „SO- przestań być zły”
źródło
źródło
Odpowiedzi:
Wykres unipatyczny może mieć krawędzie . Jest to dobrze znany rodzaj wykresu, które jest unipathic i ma n 2 / 4 krawędzi.Θ(n2) n2/4
(Dalsze pytanie: czy ten stosunek jest maksymalny? Prawdopodobnie nie, ale nie mam innego przykładu. Ten przykład jest maksymalny w tym sensie, że każda krawędź dodana między istniejącymi węzłami złamie właściwość unipathic.)
źródło
Nie wiem, czy istnieje wykres unipatyczny na więcej niż krawędzie, ale oto argument pokazujący, że nie więcej niżn2n2)4 Możliwe są 2 +3krawędzie:n2)2)+ 3
Załóżmy przez sprzeczność, że jest grafem unipatycznym takim, że | E | ≥ n 2G = ( V, E) .| mi| ≥ n2)2)+ 3
Zgodnie z zasadą szufladki istnieją takie, że d w ( v ) ≥ nv ∈ V
OznaczU= { u ∈ V∣ ( u , v ) ∈ E}
Zauważ, że jeśli byłby wierzchołek taki, że ∃ u 1 ≠ u 2 ∈ U : ( x , u 1 ) , ( x , u 2 ) ∈ Ex ∈ V.∖ { v }
źródło