# Please do not post
# Daniela Elizondo
# Assignment 22
# April 17, 2022

##### Problema 1 & 2 #####
# I unfortunately did not make any progress on these proofs.

##### Problem 4 #####

# LP(G): inputs a directed graph without cycles and outputs the set of losing vertices 
LP := proc(G) local n,S,T,i:
n := nops(G):
S := {}:
T := LaG(G):
for i from 1 to n do:
    if T[i] = 0 then S := S union {i}: fi:
    od:
end:

##### Problem 5 #####

# AvNuLP(n,p,K)
# inputs a positive integer n, a rational number p between 0 and 1 and a large integer K  
# outputs an approximation to the average size of the set of losing positions, 
# for a random directed graph (w/o cycles) with n vertices, by averaging over K random graphs gotten from RDG(n,p). 

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

# I ran the following code:
#for a from 1 to 4 do:
#    print(AvNuLP(10,a/5,10000));
#    print(AvNuLP(50,a/5,10000));
#    print(AvNuLP(100,a/5,10000));
#    od:

# outputs:

# n=10,  p=1/5: 5.491000000
# n=50,  p=1/5: 11.45440000
# n=100, p=1/5: 14.37970000
# n=10,  p=2/5: 3.794200000
# n=50,  p=2/5: 6.676300000
# n=100, p=2/5: 7.974800000
# n=10,  p=3/5: 2.793300000  
# n=50,  p=3/5: 4.469500000
# n=100, p=3/5: 5.203800000
# n=10,  p=4/5: 2.048000000
# n=50,  p=4/5: 2.993000000
# n=100, p=4/5: 3.409400000