Ile krawędzi może mieć wykres unipatyczny?

19

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 )nn-12)(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 )nO(n)Θ(n2))

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.O(n)

Gilles „SO- przestań być zły”
źródło
Fajne pytanie. Powinniśmy spróbować poprawić dolną lub górną granicę :).
RB

Odpowiedzi:

12

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

Rozważmy pełny dwustronny wykres z zorientowanymi krawędziami . Ten wykres jest jednoznaczny i nie ma cyklu: wszystkie ścieżki mają długość 1 . Ma 2 m wierzchołków i 2 m krawędzi.(i,j)[1,m]2,aibj12mm2

(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.)

Gilles „SO- przestań być zły”
źródło
„jakakolwiek krawędź, którą dodasz między istniejącymi węzłami, złamie właściwość unipathic” Jak dodanie krawędzi złamie właściwość? b1a1
mitchus
@mitchus a2b1a1b2
Gilles 'SO- przestań być zły'
1
Wydaje mi się, że mój umysł był jakoś jednoznaczny tego dnia :) Jeśli chodzi o maksimum, stosunek może iść do 1/4 dla dużego , ale dla n { 2 , 3 , 4 , 5 , 6 } podwójnie połączona lista ma więcej krawędzi niż n 2 / 4 . nn{2),3),4,5,6}n2)/4
mitchus
0

Nie wiem, czy istnieje wykres unipatyczny na więcej niż krawędzie, ale oto argument pokazujący, że nie więcej niżn2n2)4Możliwe są 2 +3krawędzie:n2)2)+3)

Załóżmy przez sprzeczność, że jest grafem unipatycznym takim, że | E | n 2sol=(V.,mi).|mi|n2)2)+3)

Zgodnie z zasadą szufladki istnieją takie, że d w ( v ) nvV.

rew(v)n2)+1

Oznacz U={uV.(u,v)mi}

Zauważ, że jeśli byłby wierzchołek taki, że u 1u 2U : ( x , u 1 ) , ( x , u 2 ) ExV.{v}

u1u2)U:(x,u1),(x,u2))mi

(xu1v)(xu2)v)

{v}×U

|mi(V.×U)|2)|U|

U

|mi|=|mi(V.×U)|+|mi(V.×(V.U))|
2)|U|+n|V.U|2)(n2)+1)+n(n2)-1)<n2)2)+3)

RB
źródło