Liczba cykli na wykresie

Ile cykli $C_k$ $(k \geq 3)$ znajdują się na wykresie wierzchołków, tak że wykres nie ma żadnego cyklu . $n$ $C_m$ $(m>k)$

Na przykład , , wówczas wykres będzie miał najwyżej dwa , tak że nie będzie miał żadnego $n=5$ $k=3$ $C_3$ $G$ $C_k (k > 3).$

Myślę, że są $O(n)$ cykle będą tam spełniające powyższe warunki.

Czy ktoś może mi pomóc.

graph-theory graph-algorithms Kumar
źródło

czy mówisz o cyklach indukowanych wierzchołkami? rozłączne cykle?

Igor Shinkar

Odpowiedź może zależeć od parytetu

m - k

$m-k$ . Rozważmy na przykład zrównoważone powiększanie w 5 cyklach. Ten wykres nie zawiera 6 cykli, ale zawiera

Θ (n^{5})

$\Theta(n^5)$ indukowane 5 cykli.

Igor Shinkar

@IgorShinkar Przeczytałem pytanie jako „jaka jest maksymalna liczba

k

$k$ - motocykle w

n

$n$ -vertex wykres, który nie ma

m

$m$ -cykl dla każdego

m > k

$m > k$ ?" więc

m

$m$ nie jest parametrem, jest powszechnie obliczany ilościowo

Sasho Nikolov

Zakładam, że mówisz o cyklach indukowanych (dziurach). Jeśli chcesz minimalną liczbę, to z pewnością 0, pusty wykres. Jeśli chcesz uzyskać maksymalną liczbę, wynosi ona n ^ 3 dla k = 3 (rozważ kompletny wykres).

Yixin Cao,

@YixinCao Dla k = 3, jeśli weźmiesz pod uwagę pełny wykres z wierzchołkami 'n', to będziemy mieli cykl, którego długość jest większa niż 3. Szukam maksymalnej liczby cykli długości k na wykresie, tak że wykres nie powinien zawierać dowolny cykl o długości większej niż k

Kumar

Odpowiedzi:

Nie jest $O(n)$ chyba że $k=3$ . Dla $k$ nawet maksymalna długość cyklu na pełnym grafie dwustronnym $K_{n,k/2}$ jest $k$ oraz liczba długości $k$ cykli jest $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$ . Na przykład, $K_{2,n}$ ma kwadratową liczbę 4 cykli, ale nie ma cykli dłuższych niż 4.

Z drugiej strony, dla dowolnego stałego wiązania $k$ na długości najdłuższego cyklu liczba trójkątów jest naprawdę $O(n)$ . Oto szybki dowód: w głębokim pierwszym drzewie wyszukiwania każda krawędź przechodzi od dolnej z dwóch punktów końcowych do co najwyżej przodka $k-1$ cofa się, więc każdy liść drzewa ma co najwyżej stopień $k-1$ i należy do co najwyżej . Teraz usuń liść i indukuj. $\binom{k-1}{2}$

David Eppstein
źródło

tak, masz rację :)

virgi

Napisałem krótki program clingo, aby sprawdzić małe wartości (potrafi szybko obsłużyć wykresy do 7 wierzchołków. Poza tym uziemienie może zająć sporo czasu):

Mam ten stół

                            n (vertices)
                         3   4   5   6   7

                      3  1   1   2   2   3

                      4      3   3   6  10

k (cycle length)      5         12  12  12

                      6             60  60

                      7                360

Oto program:

num(1..n).
is_sym_order(empty,0).
ncontains(empty,K) :- num(K).
is_sym_order(cons(K,empty),1) :- num(K).
last(cons(K,empty), K) :- num(K).
is_sym_order(cons(K,S),M+1) :- is_sym_order(S,M), ncontains(S,K), last(S,L), K > L.
ncontains(cons(K,S), J) :- J != K, ncontains(S,J), is_sym_order(cons(K,S),_).
last(cons(K,S), L) :- last(S,L), is_sym_order(cons(K,S),_).
sec_last(cons(A,S),A) :- is_sym_order(cons(A,S),2).
sec_last(cons(K,S), SL) :- sec_last(S,SL), is_sym_order(cons(K,S),_).
is_sub_order(cons(A,S), M) :- A > SL, sec_last(S,SL), is_sym_order(cons(A,S), M).

vertex(1..n).
{is_edge(V,W)} :- vertex(V), vertex(W), V < W.
sym_edge(V,W;W,V) :- is_edge(V,W).

is_path(cons(V,empty)) :- vertex(V).

is_path(cons(A,cons(B,S))) :- is_path(cons(B,S)), sym_edge(A,B), is_sym_order(cons(A,cons(B,S)),_).
is_cycle(cons(A,S)) :- is_path(cons(A,S)), is_edge(V,A), last(S,V), is_sub_order(cons(A,S),M), M >= k.

:- is_cycle(S), is_sub_order(S,M), M > k.
prim_cycle(S) :- is_cycle(S), is_sub_order(S,k).
:~ not is_cycle(S), is_sub_order(S,k).[1,S]

num_cycs(C) :- C = #count{is_cycle(S):is_cycle(S)}.
#show is_edge/2.
#show num_cycs/1.
#show prim_cycle/1.

dspyz
źródło