#C12.txt: Oct. 17, 2016, Math 640 (Rutgers Univ.) (Fall 2016) Help:=proc(): print(`MTTn(A), MTT(A,n) , LT(n), PC(f,i) , AJ(f) `): end: with(linalg): #MTTn(A): inputs the adjacenty matrix A, of a graph (0-1 matrix) and outputs # the number of spanning trees MTTn:=proc(A) local i,j,n: n:=nops(A): det( [seq( [seq(-A[i][j],j=1..i-1), add(A[i][j],j=1..i-1)+add(A[i][j],j=i+1..n) , seq(-A[i][j],j=i+1..n-1)], i=1..n-1)]): end: #MTT(A,n): inputs a letter A and outputs # the "generating funtions" of all labeled trees MTT:=proc(A,n) local i,j: det( [seq( [seq(-A[i][j],j=1..i-1), add(A[i][j],j=1..i-1)+add(A[i][j],j=i+1..n) , seq(-A[i][j],j=i+1..n-1)], i=1..n-1)]): end: #LT(n): inputs a pos. integer n and outputs # the set of labeled trees on n vertices LT:=proc(n) local i,j,t: t:= det( [seq( [seq(-{i,j},j=1..i-1), add({i,j},j=1..i-1)+add({i,j},j=i+1..n) , seq(-{i,j},j=i+1..n-1)], i=1..n-1)]): if n=2 then RETURN({{1,2}}): fi: t:={op(t)}: {seq(convert(op(i,t),set),i=1..nops(t))}: end: #PC(f,i): inputs a function, f, from {1,...,n}->{1,...n} (n=nops(f)) #and i from 1 to n, outputs the path leading from i to a cycle, followed by #the cycle PC:=proc(f,i) local n,cu, P,j,P1,C,m: n:=nops(f): P:=[i]: cu:=f[i]: while not member(cu,P) do P:=[op(P),cu]: cu:=f[cu]: od: # j:=ListTools[Search](cu,P): #does not work for all versions of Maple, so replaced by the line below for j from 1 to nops(P) while P[j]<>cu do od: P1:=[op(1..j,P)]: C:=[op(j..nops(P),P)]: #j:=min[index](C): #does not work for all versions of Maple, replaced by line below m:=min(C): for j from 1 to nops(C) while C[j]<>m do od: C:=[op(j..nops(C),C),op(1..j-1,C)]: [P1,C]: end: #AJ(f): inputs a list of length n, say, consiting of {1,...,n} such that i goes to f[i] #(n^n of them), outputs the DOUBLY-ROUTED tree given by Joyal's bijection #in the form [Labelled Tree, [First Root, SecondRoot]] #finished by Dr. Z. after class AJ:=proc(f) local S,LO,i,n, al,AllC,T,V,v,a,T1,c,i1,V1: n:=nops(f): LO:={seq(i,i=1..n)}: S:={}: while LO<>{} do al:= PC(f, LO[1]): S:=S union {al}: LO:=LO minus {op(al[1]),op(al[2])}: od: S: AllC:={seq(S[i][2],i=1..nops(S))}: V:={seq(op(AllC[i]),i=1..nops(AllC))}: #T: Table such for each v in V T[v] is the set of edges beloning to a path #that leads to v for v in V do T[v]:={}: for a in S do if a[1][-1]=v then T[v]:=T[v] union {seq({a[1][i],a[1][i+1]},i=1..nops(a[1])-1)}: fi: od: od: for c in AllC do for i1 from 1 to nops(c)-1 do T1[c[i1]]:=c[i1+1]: od: T1[c[nops(c)]]:=c[1]: od: V1:=sort(convert(V,list)): V1:=[seq(T1[V1[i]],i=1..nops(V1))]: [{seq( op(T[V1[i]]), i=1..nops(V1))} union {seq({V1[i],V1[i+1]},i=1..nops(V1)-1)},[V1[1],V1[nops(V1)]]]: end: