How to count cycles in a complete graph
The count of cycles (simple and not simple) of length n
or less for Kn
is given by the following function C(n)
.
The count consists of the count of cycles for each length 2 <= l <= n
given by C(n, l)
.
The count for a given length l
consists of the count of cycles (simple and not simple) from each vertex 1 <= i <= n
given by C(i, n, l)
.
C(n) = C(n, 2) + C(n, 3) + ... + C(n, n)
C(n, l) = C(1, n, l) + C(2, n, l) + ... + C(n, n, l)
C(i, n, l) = 0 if l < 2
C(i, n, l) = (n - i)^(l - 1) - C(i, n, l - 1) otherwise
The following OCaml program counts the number of cycles for complete graphs K2 to K20.
#!/usr/bin/env ocaml
#load "nums.cma"
include Big_int
let rec pow b e =
if e = 0 then unit_big_int
else mult_big_int (big_int_of_int b) (pow b (e - 1))
let rec c i n l =
if l < 2 then zero_big_int
else sub_big_int (pow (n - i) (l - 1)) (c i n (l - 1))
let rec iter n f acc =
if n = 0 then acc
else iter (n - 1) f (f n acc)
let c n l =
iter n (fun i acc -> add_big_int acc (c i n l)) zero_big_int
let c n =
iter n (fun l acc -> add_big_int acc (c n l)) zero_big_int
let rec upto m n f =
if m == n then f m
else begin f m; upto (m + 1) n f end
let rec format_number s =
let l = String.length s in
if l <= 3 then s
else
let prefix = String.sub s 0 (l - 3) in
let suffix = String.sub s (l - 3) 3 in
Printf.sprintf "%s,%s" (format_number prefix) suffix
let (>>) x f = f x
let count n =
let count = c n >> string_of_big_int >> format_number in
Printf.printf "K%2d %40s\n" n count
let _ = upto 2 20 count
To run the program in Linux or OSX, install the OCaml interpreter, save the program in a file, and grant execution permission to the file.
In OSX with Homebrew, when you save the program in file count-cycles.ml
you install and run the program as follows.
ruslan$ brew install ocaml
==> Downloading https://homebrew.bintray.com/bottles/ocaml-4.02.3.el_capitan.bottle.tar.gz
...
ruslan$ chmod a+x count-cycles.ml
ruslan$ ./count-cycles.ml
K2: 1
K3: 5
K4: 42
K5: 384
K6: 4,665
K7: 69,537
K8: 1,230,124
K9: 25,140,552
K10: 582,508,305
K11: 15,084,077,381
K12: 431,646,196,806
K13: 13,525,545,361,080
K14: 460,576,563,322,057
K15: 16,935,036,272,292,001
K16: 668,691,718,661,091,000
K17: 28,220,125,532,003,984,176
K18: 1,267,597,789,008,779,578,401
K19: 60,381,304,029,673,985,693,205
K20: 3,040,239,935,992,309,703,757,730