#Ok to post homework
#Tifany Tong, November 15th, 2020, HW #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 z:
[seq(nops(AllKcomponentsGraphs(z, k)), z = 1 .. n)]:
end:

# NuKComponentsGraphs(5,2) => [0,1,3,19,230] A323875

# NuKComponentsGraphs(5,3) => [0,0,1,6,55] A323876

# --------------------------------------------------------------

# Question 2

AveNuCC := proc(n, K, M) local i, ans, totalComponents, G:
totalComponents := 0:
for i to M do 
    G := RandGr(n, K);
    totalComponents := totalComponents + nops(CCs(G)):
od:
return totalComponents/M:
end:

# [seq(evalf(AveNuCC(30, 10, 1000)), i = 1 .. 10)] = 
# [20.05000000, 20.05300000, 20.05200000, 20.05300000, 20.03700000, 
#  20.05500000, 20.04100000, 20.04500000, 20.05700000, 20.05700000]


# --------------------------------------------------------------

# Question 3

EstimateCutOff := proc(n, M) local i, ans:
for i to 1/2*n*(n - 1) do 
    if evalf(AveNuCC(n, i, M)) <= 1.05 then return i: fi: od:
return 1/2*n*(n - 1):
end: