# OK to post homework
# RDB, 2022-04-17, HW22

# 3.

# I helped debug this, so I hope I remember.

# The labeling algorithm works like this:

#   Every sink (something with no children) is labeled a 0.
#   Then, recursively, the following two rules are applied:
#       i. Anything which leads only to a 1 is a 0.
#       ii. Anything which has a single move to a 0 is a 1.

# This is a "greedy" algorithm whose single steps clearly give the correct
# labels. But does it terminate?

# Well, you could end up with a graph like [{2}, {1}], where nothing is a sink
# and there's no way to label anything. Or [{2}, {1}, {}], where this is a
# sink, but the first connected component is a strange cycle.

# If we assume that there are no cycles, then this is pretty easy.

# Say that some the algorithm terminates with an unlabeled vertex. It can't be
# a sink, lead to a 0, or lead only to 1's, or else it would have been labeled.
# So at least one of its descendants is unlabeled. If we follow that vertex and
# repeat the argument, we can construct a path of unlabeled vertices. This path
# either exhausts the unlabeled ones (in which case the final vertex of the
# path is actually labeled), or we get a cycle. Both are impossible!

# 4.

read "C22.txt":

LP := proc(G)
    local res:
    res := LaG(G):
    select(k -> res[k] = 0, {seq(1..nops(G))}):
end:

# 5.

AvNuLP := proc(n, p, K)
    evalf(add(nops(LP(RDG(n, p))), k=1..K) / K):
end:

# AvNuLP(10, 1/5, 1000); # 5.503700000
# AvNuLP(10, 2/5, 1000); # 3.794600000
# AvNuLP(10, 3/5, 1000); # 2.783400000
# AvNuLP(10, 4/5, 1000); # 2.028800000

# AvNuLP(50, 1/5, 1000); # 11.408
# AvNuLP(50, 2/5, 1000); # 6.649
# AvNuLP(50, 3/5, 1000); # 4.479
# AvNuLP(50, 4/5, 1000); # 3.010

# AvNuLP(100, 1/5, 1000); # 14.395
# AvNuLP(100, 2/5, 1000); # 7.949
# AvNuLP(100, 3/5, 1000); # 5.169
# AvNuLP(100, 4/5, 1000); # 3.43