Anzahl der Zyklen in einem Diagramm

Wie viele Zyklen gibt es in einem Scheitelpunktgraphen, so dass der Graph keinen Zyklus . $C_k$ $(k \geq 3)$ $n$ $C_m$ $(m>k)$

Zum Beispiel , , dann hat der Graph höchstens zwei , so dass kein $n=5$ $k=3$ $C_3$ $G$ $C_k (k > 3).$

Ich denke, dass es Zyklen gibt, die die oben genannten Bedingungen erfüllen. $O(n)$

Kann mir jemand helfen?

graph-theory graph-algorithms Kumar
quelle

Sprechen Sie über vertexinduzierte Zyklen? disjunkte Zyklen?

Igor Shinkar

Die Antwort kann von der Parität von

abhängen . Stellen Sie sich zum Beispiel ein ausgeglichenes Aufblasen eines 5-Zyklus vor. Dieser Graph enthält keine 6 Zyklen, aber er enthält

induzierte 5 Zyklen.

m - k

$m-k$

Θ (n^{5})

$\Theta(n^5)$

Igor Shinkar

@IgorShinkar Ich lese die Frage, „was die Anzahl der maximal

-Zyklen in einem

-eckiges Graph, der keine hat

für jede -Zyklus

?“ Also ist

kein Parameter, es ist universell quantifiziert

k

$k$

n

$n$

m

$m$

m > k

$m > k$

m

$m$

Sasho Nikolov

Ich nehme an, Sie sprechen von induzierten Zyklen (Löchern). Wenn Sie die Mindestanzahl möchten, ist es sicherlich 0, ein leeres Diagramm. Wenn Sie die maximale Anzahl möchten, ist es n ^ 3 für k = 3 (betrachten Sie einen vollständigen Graphen).

Yixin Cao

@YixinCao Für k = 3: Wenn Sie ein vollständiges Diagramm mit 'n' Eckpunkten betrachten, haben wir einen Zyklus mit einer Länge von mehr als 3. Ich suche nach einer maximalen Anzahl von Zyklen der Länge k in einem Diagramm, das das Diagramm nicht enthalten sollte Jeder Zyklus mit einer Länge von mehr als k

Kumar

Antworten:

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

Ja, Sie haben Recht :)

Virgi

Ich habe ein kurzes Clingo-Programm geschrieben, um die kleinen Werte zu überprüfen (es kann schnell Diagramme mit bis zu 7 Eckpunkten verarbeiten. Darüber hinaus kann die Erdung eine Weile dauern):

Ich habe diesen Tisch

                            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

Hier ist das Programm:

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
quelle