#OK to post homework
#Karnaa Mistry, 11/15/20, Assignment HW #18

with(combinat):

# 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(N,K): outputs first N terms of the seq of the number of labeled graphs on N vertices with 
#K components
NuKcomponentsGraphs:=proc(N,K) local n1:
[seq( nops(AllKcomponentsGraphs(n1,K)),n1=1..N)]:
end:


# NuKcomponentsGraphs(5,2) = [0, 1, 3, 19, 230];  This is in the OEIS: A323875
# NuKcomponentsGraphs(5,3) = [0, 0, 1, 6, 55];  This is in the OEIS: A323876




# 2.

#AveNuCC(n,K,M): average num of components over M random graphs on n vertices w/ K edges
AveNuCC:=proc(n,K,M) local i,sum:

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

return(evalf(sum/M)):
end:


# For various values of K, running this proc with n=30,M=1000 actually gives very close values of avg. # of components, the maximum range in the
# results is often just a few hundredths.  Example: AveNuCC(30,15,1000) gives 15.247, 15.271, 15.265, 15.256, 15.218




# 3.

#EstimateCutOff(n,M): inputs n, outputs estimate for threshold for K, when most graphs with K edges start to be
#connected (say when the average number of connected components is less than 1.05)
EstimateCutOff:=proc(n,M) local K:

K:=0:

do
    K:=K+1:
until(AveNuCC(n,K,M) < 1.05):

K:
end:




# 5. [Optional attempt]

# We want to prove that a graph G in n vertices has no cycles if and only if it is connected and has exactly n-1 edges.

# I'm unsure how to prove it with technical biconditional statements, P --> Q and Q --> P, but I think the main idea is:

# Assume that a graph G with n-1 edges has no cycles but is disconnected into two subgraphs Ga and Gb.  There are no cycles in each of these
# subgraphs, since G didn't have any cycles, either.  Each of Ga and Gb are trees, because there are connected, acylic, and
# undirected.

# Choose one vertex of Ga, GaV, and one vertex of Gb, GbV to be the roots of their respective graphs.  Connect these roots with one edge,
# thus connecting the graph G into one piece (connected graph).  Our graph G is connected, but has n edges with the n vertices, which
# is impossible, unless there is a cycle.  We said G was acyclic, therefore this is a contradiction.