#OK to post
#Sam Minkin, 11/15, Assignment 18

QUESTION #1:

AllKcomponentsGraphs:=proc(n,K) local S,s,C:
S:=AllGraphs(n):
C:={}:

for s in S do
	if nops(CCs(s))=K then
		C:=C union {s}:
	fi:
od:

C:
end:

NuKcomponentsGraphs:=proc(N,K) local n1:
[seq(nops(AllKcomponentsGraphs(n1,K)), n1=1..N)]:
end:

Running evalb(seq(NuKcomponentsGraphs(n, 1), n = 1 .. 6) = seq(NuConG(n), n = 1 .. 6)), we get: true.

Running NuKcomponentsGraphs(5,2) gives:
[0, 1, 3, 19, 230]
- It is in the OEIS, with A-number: A323875, and it is described as the number of labeled graphs on n nodes with two connected components.

Running NuKcomponentsGraphs(5,3) gives:
[0, 0, 1, 6, 55]
- It is in the OEIS, with A-number: A323876, and it is described as the number of labeled graphs on n nodes with three connected components.


QUESTION #2:

AveNuCC:=proc(n,K,M) local i,s:
s:=0:

for i from 1 to M do
	s:=s+nops(CCs(RandGr(n,K))):
od:

s/M:

end:

Running, seq(AveNuCC(30,15,1000),i=1..6) we get:
15.26900000, 15.27500000, 15.25400000, 15.25000000, 15.25300000, 15.26700000.
These answers are fairly close.
Trying with a larger M=1500, running seq(AveNuCC(30, 15, 1500), i = 1 .. 3) gives:
15.26400000, 15.26000000, 15.25866667
Which is not a big difference from M=1000, so M=1000 is a good choice. 


QUESTION #3:

// Finds the smallest k so that the number of connected components is no greater than 1.05
// It finds the k where graphs stop being disconnected.
EstimateCutOff:=proc(n,M) local i:

for i from 1 to binomial(n,2) do
	if AveNuCC(n,i,M) <= 1.05 then
		RETURN(i):
	fi:
od:

RETURN(0):

end:

For example, EstimateCutOff(5, 150) returns 6. So, k=6 is the number of edges where the average number of components given some M is less than or equal to 1.05.