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$ $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 ). $n$ $O(n)$ $\Theta(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. $O(n)$}

graphs combinatorics

— Gilles „SO- przestań być zły”
źródło

Fajne pytanie. Powinniśmy spróbować poprawić dolną lub górną granicę :).

— RB

12

Wykres unipatyczny może mieć krawędzie . Jest to dobrze znany rodzaj wykresu, które jest unipathic i ma krawędzi. $\Theta(n^2)$ $n^2/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ść . Ma wierzchołków i krawędzi. $\forall (i,j) \in [1,m]^2, a_i \rightarrow b_j$ $1$ $2m$ $m^2$

_{(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ść?

b_{1} \to a_{1}

$b_1 \rightarrow a_1$

— mitchus

@mitchus

a_{2} \to b_{1} \to a_{1} \to b_{2}

$a_2 \rightarrow b_1 \rightarrow a_1 \rightarrow b_2$

— 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

podwójnie połączona lista ma więcej krawędzi niż

.

n

$n$

n \in {2, 3, 4, 5, 6}

$n \in \{2,3,4,5,6\}$

n^{2} / 4

$n^2/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ż $\frac{n^2}{4}$ Możliwe sąkrawędzie: $\frac{n^2}{2}+3$

Załóżmy przez sprzeczność, że jest grafem unipatycznym takim, że $G=(V,E)$ . $|E|\geq \frac{n^2}{2}+3$

Zgodnie z zasadą szufladki istnieją takie, że $v\in V$

{re}_{w} (v) \geq \frac{n}{2)} + 1

$d_{\text{in}}(v)\geq \frac{n}{2}+1$

Oznacz $U=\{u\in V\mid (u,v)\in E\}$

Zauważ, że jeśli wierzchołek taki, że $x\in V\setminus \{v\}$

\exists u_{1} \neq u_{2)} \in U : (x, u_{1}), (x, u_{2)}) \in mi

$\exists u_1\neq u_2\in U:(x,u_1),(x,u_2)\in E$

$(x\to u_1\to v)$ $(x\to u_2\to v)$

$\{v\}\times U$

| mi \cap (V. \times U) | \leq 2) | U |

$|E\cap (V\times U)|\leq2|U|$

$U$

| mi | = | mi \cap (V. \times U) | + | mi \cap (V. \times (V. ∖ U)) |

$|E|=|E\cap (V\times U)|+|E\cap (V\times (V\setminus U))|$

\leq 2) | U | + n | V. ∖ U | \leq 2) (\frac{n}{2)} + 1) + n (\frac{n}{2)} - 1) < \frac{n^{2)}}{2)} + 3)

$\leq 2|U|+n|V\setminus U|\leq 2(\frac{n}{2}+1)+n(\frac{n}{2}-1)<\frac{n^2}{2}+3$

$\square$

— RB
źródło