#OK to post homework 
#Natalya Ter-Saakov, April 17, Assignment 22
read "C22.txt":

#Problem 4

#LP(G): inputs a directed graph w/o cycles, G (let n:=nops(G)) and outputs the subest of {1,...,n} of its losing positions.
LP:=proc(G) local n,La,S,i:
S:={}:
n:=nops(G):
La:=LaG(G):
for i from 1 to n do
	if La[i]=0 then S:=S union {i}: fi:
od:
S:
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 and 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 E,i:
E:=0:
for i from 1 to K do:
 E+=nops(LP(RDG(n,p))):
od:
evalf(E/K):
end:

AvNuLP(10,1/5,10000);
#5.48
AvNuLP(10,2/5,10000);
#3.80
AvNuLP(10,3/5,10000);
#2.79
AvNuLP(10,4/5,10000);
#2.04
AvNuLP(50,1/5,10000);
#11.46
AvNuLP(50,2/5,10000);
#6.67
AvNuLP(50,3/5,10000);
#4.45
AvNuLP(50,4/5,10000);
#3.00
AvNuLP(100,1/5,10000);
#14.36
AvNuLP(100,2/5,10000);
#7.99
AvNuLP(100,3/5,10000);
#5.19
AvNuLP(100,4/5,10000);
#3.43