> Help22 := proc() print(`mex(S), ai(i), aiC(i), RDG(n,p), Parents(G), OneStep0(G,AL,T)  , OneStep1(G,AL,T), OneStep(G,AL,T), LaG(G)    `); end proc;
> mex := proc(S) local i; for i from 0 while member(i, S) do ; end do; i; end proc;
> ai := proc(i) local j; option remember; if i = 0 then RETURN(0); else mex({seq(ai(j) + j, j = 0 .. i - 1), seq(ai(j), j = 0 .. i - 1)}); end if; end proc;
> aiC := proc(i) trunc(1/2*(1 + sqrt(5))*i); end proc;
> RDG := proc(n, p) local a, b, L, i, j, S, ra; a := numer(p); b := denom(p); ra := rand(1 .. b); L := []; for i to n do S := {}; for j from i + 1 to n do if ra() <= a then S := S union {j}; end if; end do; L := [op(L), S]; end do; L; end proc;
> Parents := proc(G) local n, i, j, P; option remember; n := nops(G); for j to n do P[j] := {}; end do; for i to n do for j in G[i] do P[j] := P[j] union {i}; end do; end do; [seq(P[j], j = 1 .. n)]; end proc;
> OneStep0 := proc(G, AL, T) local AL1, n, T1, i, j, P; AL1 := AL; n := nops(G); P := Parents(G); T1 := T; for i in AL do if T1[i] = 0 then for j in P[i] do T1 := [op(1 .. j - 1, T1), 1, op(j + 1 .. n, T1)]; AL1 := AL1 union {j}; end do; end if; end do; RETURN(G, AL1, T1); end proc;
> OneStep1 := proc(G, AL, T) local n, T1, i, j; n := nops(G); T1 := T; for i to n do if not member(i, AL) then if G[i] minus AL = {} and {seq(T1[j], j in G[i])} = {1} then T1 := [op(1 .. i - 1, T1), 0, op(i + 1 .. n, T1)]; RETURN(G, AL union {i}, T1); end if; end if; end do; G, AL, T1; end proc;
> OneStep := proc(G, AL, T) local n, Hope; n := nops(G); if nops(AL) = n then RETURN(G, AL, op(T)); end if; Hope := OneStep0(G, AL, T); if nops(AL) < nops(Hope[2]) then RETURN(Hope); end if; Hope := OneStep1(G, AL, T); if nops(AL) < nops(Hope[2]) then RETURN(Hope); end if; FAIL; end proc;
> LaG := proc(G) local n, i, AL, T, Hope; n := nops(G); T := [(-1) $ n]; AL := {}; for i to n do if G[i] = {} then T := [op(1 .. i - 1, T), 0, op(i + 1 .. n, T)]; AL := AL union {i}; end if; end do; Hope := G, AL, T; while nops(Hope[2]) < n do Hope := OneStep(Hope); end do; [seq(Hope[3][i], i = 1 .. n)]; end proc;
> LP := proc(G) local S, L, i; S := LaG(G); L := []; for i to nops(S) do if S[i] = 0 then L := [op(L), i]; end if; end do; L; end proc;
> AvNuLP := proc(n, p, K) local i, S, T, count; count := 0; for i to K do S := RDG(n, p); T := LP(S); count := count + nops(T); end do; print(count); evalf(count/K); end proc;
> AvNuLP(10, 1/5, 10000);
                             54921


                          5.492100000


;
> AvNuLP(10, 2/5, 10000);
                             38033


                          3.803300000


;
> AvNuLP(10, 3/5, 10000);
                             27898


                          2.789800000


;
> AvNuLP(10, 4/5, 10000);
                             20376


                          2.037600000


;
> AvNuLP(50, 1/5, 10000);
                             114603


                          11.46030000


;
> AvNuLP(50, 2/5, 10000);
                             66967


                          6.696700000


;
> AvNuLP(50, 3/5, 10000);
                             44665


                          4.466500000


;
> AvNuLP(50, 4/5, 10000);
                             29994


                          2.999400000


;
> AvNuLP(100, 1/5, 10000)*AvNuLP(100, 2/5, 10000)*AvNuLP(100, 3/5, 10000)*AvNuLP(100, 4/5, 10000);
Warning, a multi-line expression was interpreted as each line being multiplied together; use a semi-colon to split the expression into separate statements if desired, or use an explicit * to eliminate this warning
                             143438


                             79929


                             52019


                             34203


                          2039.833877


;
> NULL;
> NULL;