> #ok to post
> #Yifan Zhang, 11/12/2020
> 
> #Q1.
> #[Better Version of Nov. 11, 2020 ]
> #Generalize procedure NuConG(N) of M18.txt to write a procedure
> 
> #NuKcomponentsGraphs(N,K)
> 
> #that inputs a positive integer N and another positive integer K and outputs the first N terms of the sequence enumerating the number of labeled graphs on n vertices with Exactly K componets. Make sure that NuKComponentsGraphs(N,1) equals NuConG(N) for N d 6
> #Hint: Of course, you first need to write a procedure AllKcomponentsGraphs(n,K) by tweaking procedure AllConGraphs(n) and change the line nops(CCs(s))=1 to nops(CCs(s))=k
> 
> #Are the following sequences in the OEIS? If yes, what are the A-numbers
> 
> #NuConGgen(5,2), NuConGgen(5,3)
> read`M18.txt`;
> 
> AllKConGraphs:=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(AllKConGraphs(n1,K)),n1=1..n)]:
> end:
> NuKcomponentsGraphs(5,1);
[1, 1, 4, 38, 728]
> NuConG(5);
[1, 1, 4, 38, 728]
> NuKcomponentsGraphs(5,2);
[0, 1, 3, 19, 230]
> #Yes, A323875: 	Number of labeled graphs on n nodes with two connected components.
> NuKcomponentsGraphs(5,3);
[0, 0, 1, 6, 55]
> #Yes, A323876: 	Number of labeled graphs on n nodes with three connected components.
> 
> 
> 

> #Q2.
> #Using procedures RandGr(n,K) and CCs(G), in M18.txt
> #write a procedure
> #
> #AveNuCC(n,K,M)
> #
> #that generates M random graphs on n vertices with K edges, and for each of them finds the number of components and take the average over these M random graphs. Run it several times with n=30 and M=1000 to check that you get close answers. If not what M would give such agreement?

> 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:
> 
> evalf(AveNuCC(30,20,1000));
10.96100000
> evalf(AveNuCC(30,20,1000));
10.98600000
> evalf(AveNuCC(30,20,1000));
10.94200000
> evalf(AveNuCC(30,20,1000));
10.93300000
> #M=1000 is ok. The answer is close now. 
> 
> 
> 

> #Q3.
> #Using the above,say, write a procedure
> #EstimateCutOff(n,M)
> 
> #that inputs a positive integer n and outputs an estimate for the "threshold" for K, when most graphs with K edges start to be connected (say when the average number of connected componets is less than 1.05)
> 
> EstimateCutOff:=proc(n,M) local K:
> 
> for K from 1 to 100 do
>  if AveNuCC(n,K,M)<1.05 then
>   return(K);
>  fi
> od:
> 
> return "NOT FOUND SUCH K or K is larger than 100":
> 
> end:
> 
> EstimateCutOff(10, 1000);
19
> evalf(AveNuCC(10,19,1000));
1.039000000
> #For example, when input AveNuCC with K=19, it works that the average number of connected components is less than 1.05
> 
> 
> 
> 
> 

> #Q4.
> #[Optional challenge] Running it for various n from 100 to 200, and M=1000 (or possibly larger) Can you conjecture an expression for that cut-off in terms of n?
> evalf(AveNuCC(100,350,1000));
1.067000000
> evalf(AveNuCC(100,360,1000));
1.055000000
> evalf(AveNuCC(100,360,1000));
1.048000000
> #for n=100, K is around to 360. Maybe K and n is in linear relation with K = 3.6 * n
> #try n=200, if K is around to 720
> evalf(AveNuCC(200,720,1000));
1.116000000
> #The coeff is not 3.6. 
> #Hence, the relation between K and n may not be linear!
> #Next, try n=125,150,175,200 and test if the relation is in polynomial
> evalf(AveNuCC(200,850,1000));
1.033000000
> evalf(AveNuCC(200,820,1000));
1.046000000
> evalf(AveNuCC(200,820,1000));
1.053000000
> #so for n=200, K is around to 820. 
> #Now, Define: Lambda = K/n
> #for n = 100, K is around to 360. Lambda = 3.6
> #for n = 200, K is around to 820. Lambda = 4.1
> #Conjecture: Lambda is linearly increasing, 
> #Next, I predict, for n=150, Lambda = (3.6+4.1)/2= 3.85, K should be around to 3.825*150 = 577.5 -> 578
> evalf(AveNuCC(150,578,1000));
1.046000000
> #Hence, for n=150, K is around to 578, the prediction is right. 
> #Next, test if for n=125 and Lambda = (3.6+3.85)/2 = 3.725, K is around to 3.725*125 = 465.6 -> 466
> evalf(AveNuCC(125,466,1000));
1.052000000
> #Hence, for n = 125, K is around to 466. 
> #And test for n = 175 and Lambda = (3.85+4.1)/2 = 3.975, K is around to 3.975*175 = 695.6 -> 696
> evalf(AveNuCC(175,696,1000));
1.052000000
> #Hence, for n = 175, K is around to 696
> #In a summary, By the defined Lambda = K/n, 
> #for n = 100, K is around to 360, and Lambda = 3.6
> #for n = 125, K is around to 466, and Lambda = 3.725
> #for n = 150, K is around to 578, and Lambda = 3.825
> #for n = 175, K is around to 696, and Lambda = 3.975
> #for n = 200, K is around to 810, and Lambda = 4.1
> #Conjecture: 
> #Lambda = 3.6+0.005*(n-100) = 3.1 + 0.005*n
> #and K = Lambda * n = (3.1 + 0.005*n) * n = 3.1*n + 0.005*n^2
> 
> GenerateK:=proc(n) local K, result: 
> K:= round(3.1*n + 0.005*n^2):
> result:=evalf(AveNuCC(n,K,1000)):
> if(result >= (1.05*0.97) and result <= (1.05*1.03)) then
>  RETURN(n,K, "The error of estimate K is less than 3%");
> fi:
> 
> RETURN("FAIL: Error > 3%"):
> end:
> n:=rand(100..200);
n := proc () (proc () option builtin = RandNumberInterface; end proc)(6, 101, 7)+100 end proc
> GenerateK(n());
193, 785, "The error of estimate K is less than 3%"
> 
> 
> 
> #Q5.
> #[Optional challenge in human mathematics] Prove that a graph in n vertices has no cycles if and only if it is (i) connected (ii) has exactly n-1 edges
> #The graph in n vertices has no cycles is a tree.
> #The minimum number of edges required to make a graph of n vertices is n-1 edges. 
> #Since tree is a connected graph, there is at least one path between every pair of vertices in a tree. Suppose there is second path between connected vertices a and b, then there is a circle and it cannot be a tree. So any two vertices can only have one path connected with others. Hence there is exactly n-1 edges with n vertices for the graph with no cycles. 
> 
> 
> 
>