Nombre de cycles dans un graphique

Combien de cycles y a-t-il dans un graphe à sommets tel que le graphe n'a pas de cycle . $C_k$ $(k \geq 3)$ $n$ $C_m$ $(m>k)$

Par exemple , , alors le graphique aura au plus deux de sorte que n'aura pas de $n=5$ $k=3$ $C_3$ $G$ $C_k (k > 3).$

Je pense qu'il y a des cycles il y aura des conditions ci-dessus satisfaisantes. $O(n)$

Est-ce que quelqu'un peut m'aider.

graph-theory graph-algorithms Kumar
la source

parlez-vous des cycles induits par les sommets? cycles disjoints?

Igor Shinkar

La réponse peut dépendre de la parité de

. Par exemple, considérons une explosion équilibrée d'un cycle à 5 cycles. Ce graphique ne contient pas de 6 cycles, mais il contient 5 cycles induits par

m - k

$m-k$

Θ (n^{5})

$\Theta(n^5)$

Igor Shinkar

@IgorShinkar J'ai lu la question comme "quel est le nombre maximum de

cycles dans un graphe

-vertex qui n'a pas de

cycle pour tout

?" donc

n'est pas un paramètre, il est universellement quantifié

k

$k$

n

$n$

m

$m$

m > k

$m > k$

m

$m$

Sasho Nikolov

Je suppose que vous parlez de cycles induits (trous). Si vous voulez le nombre minimum, c'est sûrement 0, un graphique vide. Si vous voulez le nombre maximum, c'est n ^ 3 pour k = 3 (considérez un graphe complet).

Yixin Cao

@YixinCao Pour k = 3, si vous considérez un graphe complet avec 'n' sommets, alors nous aurons un cycle dont la longueur est supérieure à 3. Je recherche le nombre maximum de cycles de longueur k dans un graphe tel que le graphe ne devrait pas contenir tout cycle de longueur supérieure à k

Kumar

Réponses:

$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}$

$k$ $O(n)$ $k-1$ $k-1$ $\binom{k-1}{2}$

David Eppstein
la source

oui, vous avez raison :)

virgi

J'ai écrit un petit programme de clingo pour vérifier les petites valeurs (il peut gérer rapidement des graphiques jusqu'à 7 sommets. Au-delà, la mise à la terre peut prendre un certain temps):

J'ai cette table

                            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

Voici le programme:

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
la source