StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I have a theory, but I don't have mathematica to test it with, so here goes. (And please excuse my mistakes in terminology, I'm not really familiar with graph theory.)</p> <p>I agree that there are 2^(n*(n-1)/2) different directed Kn graphs. The question is how many of those contain a path A->B. Call that number S(n).</p> <p>Suppose we know S(n) for some n, and we want to add another node, X, and calculate S(n+1). We will look for paths X->A.</p> <p>There are 2^n ways to connect X to the preexisting graph.</p> <p>The edge X-A might point in the "right" direction (X->A); there are 2^(n-1) ways to connect X this way, and it will lead to a path for any of the 2^(n*(n-1)/2) different Kn graphs.</p> <p>If X-A points to X, try the edge X-B. If X-B points to B (and there are 2^(n-2) such ways to connect X) then some Kn graphs will give a path B->A, S(n) of them in fact.</p> <p>If X-B points to X, try X-C; there are 2^(n-3)S(n) successful graphs there.</p> <p>If my math is correct, S(n+1) = 2^((n+2)(n-1)/2) + (2^(n-1)-1)S(n)</p> <p>So this gives the following:</p> <pre> S(2) = 1 S(3) = 5 S(4) = 47 S(5) = 841 S(6) = 28999 </pre> <p>Can someone check this? Or give a closed form for S(n)?</p> <p><b>EDIT:</b><br> I see now that the hard part is this P[A !-> B && C !-> D]. But I think the recursion approach will still work: start with {A,B,C,D}, then keep adding points, keeping track of the number of graphs in which A->(a points), (b points)->B, C->(c points) and (d points)->D, keeping the desired constraint. Ugly, but tractable.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload