Jumlah siklus dalam suatu Grafik

Berapa banyak siklus yang ada dalam grafik vertex sehingga grafik tidak memiliki siklus . $C_k$ $(k \geq 3)$ $n$ $C_m$ $(m>k)$

Misalnya , , maka grafik akan memiliki paling banyak dua sehingga tidak akan memiliki $n=5$ $k=3$ $C_3$ $G$ $C_k (k > 3).$

Saya berpikir bahwa ada siklus yang akan memenuhi kondisi di atas. $O(n)$

Bisakah seseorang membantu saya.

graph-theory graph-algorithms Kumar
sumber

Anda berbicara tentang siklus yang disebabkan oleh verteks? memisahkan siklus?

Igor Shinkar

Jawabannya mungkin tergantung pada paritas

m - k

$m-k$ . Sebagai contoh, pertimbangkan ledakan seimbang dari 5 siklus. Grafik ini tidak mengandung 6 siklus, tetapi mengandung siklus

Θ (n^{5})

$\Theta(n^5)$ .

Igor Shinkar

@IgorShinkar Saya membaca pertanyaan sebagai "berapakah jumlah maksimum

sepeda dalam grafik

-vertex yang tidak memiliki

siklus untuk

?" jadi

bukan parameter, ini secara universal dikuantifikasi

k

$k$

n

$n$

m

$m$

m > k

$m > k$

m

$m$

Sasho Nikolov

Saya berasumsi Anda sedang berbicara tentang siklus yang diinduksi (lubang). Jika Anda menginginkan angka minimum, itu pastinya 0, sebuah grafik kosong. Jika Anda menginginkan angka maksimum, n ^ 3 untuk k = 3 (pertimbangkan grafik lengkap).

Yixin Cao

@YixinCao Untuk k = 3, Jika Anda mempertimbangkan grafik lengkap dengan simpul 'n' maka kita akan memiliki siklus yang panjangnya lebih dari 3. Saya mencari jumlah siklus maksimum panjang k dalam grafik sehingga grafik tidak boleh mengandung setiap siklus dengan panjang lebih dari k

Kumar

Jawaban:

Ini bukan kecuali . Untuk genap, panjang maksimum siklus dalam grafik bipartit lengkap adalah , dan jumlah siklus panjang adalah $O(n)$ $k=3$ $k$ $K_{n,k/2}$ $k$ $k$ . Misalnya,memiliki jumlah kuadratik 4-siklus, tetapi tidak ada siklus lebih lama dari 4. $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$ $K_{2,n}$

Di sisi lain, untuk setiap ikatan konstan pada panjang siklus terpanjang, jumlah segitiga sebenarnya adalah . Berikut ini adalah bukti cepat: di pohon pencarian pertama yang mendalam, setiap sisi bergerak dari yang lebih rendah dari dua titik akhir ke leluhur paling banyak mundur, sehingga setiap daun pohon memiliki derajat paling banyak dan milik pada kebanyakan $k$ $O(n)$ $k-1$ $k-1$ segitiga. Sekarang lepaskan daun dan lantik. $\binom{k-1}{2}$

David Eppstein
sumber

ya, Anda benar :)

virgi

Saya menulis program clingo pendek untuk memeriksa nilai-nilai kecil (dengan cepat dapat menangani grafik hingga 7 simpul. Selain itu, proses pentanahan membutuhkan waktu cukup lama):

Saya mendapat meja ini

                            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

Inilah programnya:

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
sumber