Re: Formula for counting cycles in complete graphs

In article <1147376733.211088.74450@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"jsher" <josh.sher@xxxxxxxxx> wrote:

Am I missing something? I may be mis-remembering definitions but I
thought
a. a complete graph is a graph where every vertex is connected to every
other vertex (is this correct?)
so
b. every subset forms a cycle
so
c. the number of subsets of size k out of a set of size n = n choose k
= n! / (k! * (n-k)!)
and the total number of subsets is
d. total subsets=total cycles (including "1 cycles")= 2^n

If you don't want to count 1 cycles or 2 cycles subtract them off:
2^n- n choose 2 - n choose 1=2^n-n(n-1)/2 -n

What you are missing is that for each subset there are many cycles,
e.g., for the subset {a, b, c} OP is counting a to b to c to a
as different from b to c to a to b, or b to a to c to b.

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages

  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Elecsol batteries (again)
    ... Look at the graph at the bottom. ... D.O.D. means Depth of Discharge. ... cycles for various D.O.D.s between 50% and 100%. ... sense in that the deeper the discharge, the less life cycles each ...
    (uk.rec.waterways)
  • Re: Algorithm for breaking cycles in directed graph by edge removal
    ... It is clear to me that a DFS (depth first search) can find all cycles in a directed graph. ... DFS will label some edges as "BACK" edges; these back edges connect a node U to an ancestor node V in the traversal tree. ...
    (comp.theory)
  • Re: Algorithm for breaking cycles in directed graph by edge removal
    ... DFS will label some edges as "BACK" edges; ... Obviously, by removing the back edges, all cycles in the graph will be ... Maybe try constructing a dynamic programming algorithm to solve the ...
    (comp.theory)
  • Re: Graph to regions algorithm
    ... > My problem is that I need an algorithm witch will construct all regions ... The graph is convex and convex. ... To find cycles in a graph, you compute the "minimum spanning tree". ...
    (comp.graphics.algorithms)
Quantcast