Количество циклов в графике

Сколько циклов $C_k$ $(k \geq 3)$ есть в $n$ граф вершин такой, что у графа нет цикла $C_m$ $(m>k)$ ,

Например $n=5$ , $k=3$ тогда граф будет иметь не более двух $C_3$ так что $G$ не будет иметь $C_k (k > 3).$

Я думаю, что есть $O(n)$ там будут циклы, удовлетворяющие вышеуказанным условиям.

Кто-нибудь может мне помочь.

graph-theory graph-algorithms Кумар
источник

Вы говорите о вершинно-индуцированных циклах? непересекающиеся циклы?

Игорь Шинкарь

Ответ может зависеть от соотношения

m - k

$m-k$ , Например, рассмотрим сбалансированный взрыв в 5 циклах. Этот граф не содержит 6-циклов, но он содержит

Θ (n^{5})

$\Theta(n^5)$ индуцированные 5 циклов.

Игорь Шинкарь

@IgorShinkar Я читаю вопрос как "каково максимальное количество

k

$k$ -циклы в

n

$n$ вершинный граф, который не имеет

m

$m$ -цикл для любого

m > k

$m > k$ ?" так

m

$m$ это не параметр, это повсеместно определенное количество

Сашо Николов

Я предполагаю, что вы говорите об индуцированных циклах (дырах). Если вы хотите минимальное число, это, безусловно, 0, пустой график. Если вы хотите максимальное число, это n ^ 3 для k = 3 (рассмотрим полный график).

Исинь Цао

@YixinCao Для k = 3, если вы рассматриваете полный граф с 'n' вершинами, то у нас будет цикл, длина которого больше 3. Я ищу максимальное число циклов длины k в графе, чтобы граф не содержал любой цикл длиной больше k

Кумар,

Ответы:

Не то $O(n)$ если $k=3$ , За $k$ четная максимальная длина цикла в полном двудольном графе $K_{n,k/2}$ является $k$ и количество длин $k$ циклы $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$ , Например, $K_{2,n}$ имеет квадратичное число 4-циклов, но не более 4 циклов.

С другой стороны, для любой постоянной границы $k$ на длине самого длинного цикла число треугольников действительно $O(n)$ , Вот быстрое доказательство: в первом глубинном дереве поиска каждое ребро проходит от нижней его двух конечных точек до предка не более $k-1$ отступает, поэтому любой лист дерева имеет максимальную степень $k-1$ и принадлежит не более $\binom{k-1}{2}$ треугольники. Теперь удалите лист и введите.

Дэвид Эппштейн
источник

да, вы правы :)

virgi

Я написал короткую программу-клинго для проверки малых значений (она может быстро обрабатывать графики до 7 вершин. Кроме того, заземление может занять довольно много времени):

Я получил этот стол

                            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

Вот программа:

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
источник