PZF_comb_and_sun_Markov

# This worksheet is part of Appendix 2 of # "Using Markov chains to determine expected propagation time for probabilistic zero forcing" # by Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, and Michael Ross # This worksheet is written by Kevin Liu # It contains the code for computing the expected propagation time of # comb-graphs and sun-graphs. 

# Combs 

for n in range(5, 46): #n=5 #size of comb measured by length of the path, must be at least 3 for this program N=floor((n-1)/2) #number left of center M=ceil((n-1)/2) #number right of center A=zero_matrix(QQ,4*(N+1)*(M+1)-3) #matrix starts with 4 spots for initial states (only two are used for 0 and 0L) #intermediate states are ordered (a,b,0,0),(a,b,1,0),(a,b,0,1),(a,b,1,1) #a and b order by (1,0),(2,0),...,(N,0),(0,1),(1,1),...,(N,1),...,(0,M),(1,M),...,(N,M) for k in IntegerRange(0,4*(N+1)*(M+1),4): if k==4*(N+1)*(M+1)-4: #fully propogated case A[k,k]=1 elif k>=4*(N+1)*(M+1)-4-4*N: #all right vertices propogated A[k,k]=1/9 A[k,k+1]=2/9 A[k,k+4]=2/3 A[k+1,k+4]=1 elif k/4%(N+1)==N: #all left vertices propogated A[k,k]=1/9 A[k,k+2]=2/9 A[k,k+(N+1)*4]=2/3 A[k+2,k+(N+1)*4]=1 elif k==0: #initial cases A[k,k]=8/27 A[k,k+1]=4/27 A[k,k+4]=4/27 A[k,k+(N+1)*4]=4/27 A[k,k+6]=2/27 A[k,k+(N+1)*4+1]=2/27 A[k,k+(N+1)*4+4]=1/9 A[k+1,k+1]=1/9 A[k+1,k+6]=2/9 A[k+1,k+(N+1)*4+1]=2/9 A[k+1,k+(N+1)*4+4]=4/9 else: #all other cases A[k,k]=1/81 A[k,k+1]=2/81 A[k,k+2]=2/81 A[k,k+3]=4/81 A[k,k+4]=2/27 A[k,k+6]=4/27 A[k,k+(N+1)*4]=2/27 A[k,k+(N+1)*4+1]=4/27 A[k,k+(N+1)*4+4]=4/9 A[k+1,k+4]=1/9 A[k+1,k+6]=2/9 A[k+1,k+(N+1)*4+4]=2/3 A[k+2,k+(N+1)*4]=1/9 A[k+2,k+(N+1)*4+1]=2/9 A[k+2,k+(N+1)*4+4]=2/3 A[k+3,k+(N+1)*4+4]=1 #show(A) I=identity_matrix(RDF,4*(N+1)*(M+1)-3) #ept calculation process for k in range(4*(N+1)*(M+1)-3): I[k,4*(N+1)*(M+1)-4]=I[k,4*(N+1)*(M+1)-4]+1 B=(A-I).inverse() print n print "path EPT=",B[0,4*(N+1)*(M+1)-4]+2 #for propogation time starting along the path print "leaf EPT=",B[1,4*(N+1)*(M+1)-4]+3 #for propogation time starting on a leaf print '' 

WARNING: Output truncated!  

WARNING: Output truncated!  

 

# Suns 

for n in range(5, 46): #n=5 #size of sun measured by size of the cycle, must be at least 3 for this program A=zero_matrix(RDF,3*n-3) #matrix starts with 1 and 1L, followed by (c,0),(c,1),(c-2), and ends with (n) A[0,0]=8/27 #initial case of a single blue vertex in the cycle [state 1] A[0,1]=4/27 A[0,2]=8/27 A[0,3]=4/27 A[0,5]=3/27 A[1,1]=1/9 #case for single blue vertex and blue leaf [state 1L] A[1,3]=4/9 A[1,5]=4/9 for k in IntegerRange(1,n-2): #cases for 2 to n-2 cycle vertices blue [states (c,l)] A[3*k-1,3*k-1]=1/81 A[3*k-1,3*k]=4/81 A[3*k-1,3*k+1]=4/81 A[3*k-1,3*k+2]=4/27 A[3*k-1,3*k+3]=8/27 A[3*k-1,3*k+5]=4/9 A[3*k,3*k+5]=2/3 A[3*k,3*k+2]=1/9 A[3*k,3*k+3]=2/9 A[3*k+1,3*k+5]=1 A[3*n-5,3*n-4]=1 #cases for n-1 cycle vertices blue [states (n-1,l)] A[3*n-6,3*n-4]=1 A[3*n-7,3*n-7]=1/81 A[3*n-7,3*n-6]=4/81 A[3*n-7,3*n-5]=4/81 A[3*n-7,3*n-4]=8/9 A[3*n-4,3*n-4]=1 #case for n center vertices blue [state (n)] #show(A) I=identity_matrix(RDF,3*n-3) #ept calculation process for k in range(3*n-3): I[k,3*n-4]=I[k,3*n-4]+1 B=(A-I).inverse() print n print "cycle EPT=",B[0,3*n-4]+2 #for propogation time starting inside the cycle print "leaf EPT=",B[1,3*n-4]+3 #for propogation time starting on a leaf print '' 

WARNING: Output truncated!  

WARNING: Output truncated!