Paths in complete graph

Question

I have a friend that needs to compute the following:

In the complete graph Kn (k<=13), there are k*(k-1)/2 edges. Each edge can be directed in 2 ways, hence 2^[(k*(k-1))/2] different cases.

She needs to compute P[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X !-> Y means "there is no path from X to Y", and P[ ] is the probability.

So the bruteforce algorithm is to examine every one of the 2^[(k*(k-1))/2] different graphes, and since they are complete, in each graph one only needs to consider one set of A,B,C,D because of symmetry.

P[A !-> B] is then computed as "number of graphs with no path between node 1 and 2" divided by total number of graphs, i.e 2^[(k*(k-1))/2].

The bruteforce method works in mathematica up to K8, but she needs K9,K10... up to K13.

We obviously don't need to find the shortest path in the cases, just want to find if there is one.

Anyone have optimization suggestions? (This sound like a typical Project Euler problem).

Example:

The minimal graph K4 have 4 vertices, giving 6 edges. Hence there are 2^6 = 64 possible ways to assign directions to the edges, if we label the 4 vertices A,B,C and D.

In some graphs, there is NOT a path from A to B, (lets say X of them) and in some others, there are no path from C to D (lets say Y). But in some graphs, there is no path from A to B, and at the same time no path from C to D. These are W.

So P[A !-> B]=X/64, P[C !-> D]=Y/64 and P[A !-> B && C !-> D] = W/64.

Update:

• A, B,C and D are 4 different vertives, hence we need at least K4.
• Observe that we are dealing with DIRECTED graphs, so normal representation with UT-matrices won't suffice.
• There is a function in mathematica that finds the distance between nodes in a directed graph, (if it returns infinity, there is no path), but this is a little bit overkill since we dont need the distance, just if there is a path or not.

Answer 1

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.)

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).

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.

There are 2^n ways to connect X to the preexisting graph.

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.

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.

If X-B points to X, try X-C; there are 2^(n-3)S(n) successful graphs there.

If my math is correct, S(n+1) = 2^((n+2)(n-1)/2) + (2^(n-1)-1)S(n)

So this gives the following:

S(2) = 1
S(3) = 5
S(4) = 47
S(5) = 841
S(6) = 28999

Can someone check this? Or give a closed form for S(n)?

EDIT:
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.

Answer 2

I think that representing graph using matrix will be very helpful.

If A!->B put 0 in A th row and B th column.

Put 1 everywhere else.

Count no of 0s = Z.

then P[A!->B] = 1 / 2^Z

=> P[A!->B && C!->B] - P[A!-B].P[C!-D] = 1/2^2 - 1/ 2^(X-2) // Somthing wrong here I'm fixin it where X = k(k-1)/2

  A B C D
A . 0 1 1
B . . 1 1
C . . . 1
D . . . .

NOTE:We can use upper triangle without loss of generality.

Answer 3

The brute force approach of considering all graphs will not get you much further, you'll have to consider more than one graph at a time.

For 8 you have 2^28 ~ 256 million graphs.

9: 2^36 ~ 64 billion

10: 2^45 ~ 32 trillion

11: 2^55 > 10¹⁶

12: 2^66 > 10¹⁹

13: 2^78 > 10²³

For the purpose of finding paths the interesting part is the partial ordering on the strongly connected components of the graph. Actually the ordering must be total, because there is an edge between any two nodes.

So you could try to consider total orderings, there are certainly a lot fewer than graphs.