Número de ciclos em um gráfico

9

Quantos ciclos Ck (k3) existem em um gráfico de n vértices, de modo que o gráfico não possua nenhum ciclo Cm (m>k) .

Por exemplo n=5 , k=3 , em seguida gráfico terá no máximo dois C3 's de modo a que G não terá qualquerCk(k>3).

Penso que existem ciclos que satisfazem as condições acima.O(n)

Alguém pode me ajudar.

Kumar
fonte
2
você está falando de ciclos induzidos por vértices? ciclos disjuntos?
Igor Shinkar
11
A resposta pode depender da paridade de . Por exemplo, considere uma explosão equilibrada de 5 ciclos. Este gráfico não contém 6-ciclos, mas contém Θ ( n 5 ) induzida por 5-ciclos. mkΘ(n5)
Igor Shinkar
5
@IgorShinkar Li a pergunta como "qual é o número máximo de -cycles em um gráfico n -vertex que não possui m -cycle para qualquer m > k ?" então m não é um parâmetro, que é universalmente quantificadaknmm>km
Sasho Nikolov
Suponho que você esteja falando de ciclos induzidos (buracos). Se você deseja o número mínimo, certamente é 0, um gráfico vazio. Se você deseja o número máximo, é n ^ 3 para k = 3 (considere um gráfico completo).
Yixin Cao 28/09
@YixinCao Para k = 3, se você considerar um gráfico completo com vértices 'n', teremos um ciclo cujo comprimento é maior que 3. Estou procurando pelo número máximo de ciclos de comprimento k em um gráfico, para que o gráfico não deva conter qualquer ciclo de comprimento mais do que k
Kumar

Respostas:

5

Não é menos que k = 3 . Para k par, a duração máxima de um ciclo no gráfico bipartido completo K n , k / 2 é k , e o número de ciclos de comprimento k é ( kO(n)k=3kKn,k/2kk. Por exemplo,K2,ntem um número quadrático de 4 ciclos, mas não ciclos maiores que 4.(k21)!nk/2=Θ(nk/2)K2,n

Por outro lado, para qualquer limite constante na duração do ciclo mais longo, o número de triângulos é realmente O ( n ) . Aqui está uma prova rápida: em uma primeira árvore de pesquisa profunda, cada aresta vai da parte inferior de seus dois pontos de extremidade a um ancestral no máximo k - 1 passos para trás, de modo que qualquer folha da árvore tem grau no máximo k - 1 e pertence a no mais ( k - 1kO(n)k1k1 triângulos. Agora remova a folha e induza.(k12)

David Eppstein
fonte
sim, você é :) direita
virgi
1

Eu escrevi um pequeno programa clingo para verificar os valores pequenos (ele pode lidar rapidamente com gráficos de até 7 vértices. Além disso, o aterramento pode demorar um pouco):

Eu peguei essa mesa

                            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

Aqui está o programa:

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
fonte