See [Stu93], [Der02], [Singular] and the GAP™ interface [Singular03] for general information on algorithmic invariant theory. The Buchberger algorithm (involving syzygies) delivers Gröbner bases for fundamental systems of invariant rings.

We'll have to find out about this for all our graphs. Let's play around a little bit. First of all a permutation group example:

gap>LoadPackage("singular");;
gap>G:=AlternatingGroup(5);;
gap>R:=PolynomialRing(GF(2),5);
PolynomialRing(..., [ x_1, x_2, x_3, x_4, x_5 ])
gap>GeneratorsOfInvariantRing(R,G);
[ x_1+x_2+x_3+x_4+x_5, 
  x_1*x_2+x_1*x_3+x_1*x_4+x_1*x_5+x_2*x_3+x_2*x_4+x_2*x_5+x_3*x_4+x_3*x_5+x_4*x_5, 
  x_1*x_2*x_3+x_1*x_2*x_4+x_1*x_2*x_5+x_1*x_3*x_4+x_1*x_3*x_5+x_1*x_4*x_5+x_2*\
x_3*x_4+x_2*x_3*x_5+x_2*x_4*x_5+x_3*x_4*x_5, 
  x_1*x_2*x_3*x_4+x_1*x_2*x_3*x_5+x_1*x_2*x_4*x_5+x_1*x_3*x_4*x_5+x_2*x_3*x_4*\
x_5, x_1*x_2*x_3*x_4*x_5 ]
gap>I:=Ideal(R,last);
<two-sided ideal in PolynomialRing(..., [ x_1, x_2, x_3, x_4, x_5 ]), 
  (5 generators)>
gap>GroebnerBasis(I);
#I  running GroebnerBasis...
#I  done GroebnerBasis.

[ x_1+x_2+x_3+x_4+x_5, 
  x_2^2+x_2*x_3+x_2*x_4+x_2*x_5+x_3^2+x_3*x_4+x_3*x_5+x_4^2+x_4*x_5+x_5^2, 
  x_3^3+x_3^2*x_4+x_3^2*x_5+x_3*x_4^2+x_3*x_4*x_5+x_3*x_5^2+x_4^3+x_4^2*x_5+x_\
4*x_5^2+x_5^3, x_4^4+x_4^3*x_5+x_4^2*x_5^2+x_4*x_5^3+x_5^4, x_5^5 ]

And now the matrix representation:

gap>GG:=SL(IsMatrixGroup,2,5);;
gap>RR:=PolynomialRing(GF(5),2);
PolynomialRing(..., [ x_1, x_2 ])
gap>GeneratorsOfInvariantRing(RR,GG);

[ x_1^5*x_2-x_1*x_2^5, 
  x_1^20+x_1^16*x_2^4+x_1^12*x_2^8+x_1^8*x_2^12+x_1^4*x_2^16+x_2^20 ]
gap>II:=Ideal(RR,last);
<two-sided ideal in PolynomialRing(..., [ x_1, x_2 ]), (2 generators)>
gap>GroebnerBasis(II);
#I  running GroebnerBasis...
#I  done GroebnerBasis.
[ x_1^5*x_2-x_1*x_2^5, x_1^20-x_1^4*x_2^16+x_2^20, x_2^21 ]

If you prefer the underlying SINGULAR™ system instead:

>LIB "finvar.lib";
>ring R=5,(x,y),dp;
>matrix A[2][2]=0,4,1,0;
>matrix B[2][2]=0,1,4,4;
>matrix P,S,IS=invariant_ring(A,B); 
			//returns primary invariants, and second secondary invariants, i.e. module generators
			//over a Noetherian normalization, and irreducible secondary invariants 
			//if the Molien series was available
>print(P);          
x5y-xy5
>print(S);          
x20+x16y4+x12y8+x8y12+x4y16+y20
>print(IS);
1
>ideal I=P,S;
>ideal J=std(I);
>J;
J[1]=x5y-xy5
J[2]=x20-x4y16+y20
J[3]=y21

One speaks of primary invariants f 1 , ..., f n K[V] G and homogeneous, secondary invariants g₁, ..., g_n such that K[V] G is generated as a module over K[f₁, ..., f_n]. They are not uniquely determined, and being a primary or secondary invariant is not an intrinsic property of an invariant. Fundamental invariants are a minimal system of generators of K[V] G .

Syzygies are algebraic relations between fundamental invariants.

>setring R;
>module M=Syz(I);
>M;
M[1]=x20*gen(1)+x16y4*gen(1)+x12y8*gen(1)+x8y12*gen(1)+x4y16*gen(1)+y20*gen(1)
     -x5y*gen(2)+xy5*gen(2)

Let's use some more methods from the 'finvar' library:

>list L=primary_invariants(A,B);
>L;
[1]:
   _[1,1]=x5y-xy5
   _[1,2]=x20+x16y4+x12y8+x8y12+x4y16+y20
>matrix SE=secondary_not_cohen_macaulay(L[1],A,B);
>print(SE);
1

The Gröbner bases are confluent and enable you to decide ideal membership.

>poly f=x10y10;
>reduce(f,J,1);      //3rd parameter 1 avoids tail reduction
x2y18                //f is not in I
>poly g=y2*J[1]-2x*J[2];
>reduce(g,J,1);
0                    //g is in I
>matrix M=lift(J,g);
>M;
M[1,1]=y2;
M[2,1]=-2x;
M[3,1]=0

Let us furthermore figure out a minimal free resolution of the finitely generated R-module Coker(matrix(J)) = F₀ / J with finitely generated free R-modules F_i for i ≥ 0, that is an exact sequence

⋯ → F k → ⋯ → F 1 → F 0 → F 0 J → 0

with finite minimal length n if k n F k 0 . The rank(F_k), k ≥ 0, are called the k-th Betti number of the module F₀ / J.

>resolution Re=mres(prune(J),0);
>Re;
 1    2    1
R <--R <--R

0    1    2
>print(Re);
[1]:
   _[1]=x5y-xy5
   _[2]=x20-x4y16+y20
[2]:
   _[1]=x20*gen(1)-x4y16*gen(1)+y20*gen(1)-x5y*gen(2)+xy5*gen(2)
>betti(Re);
//-> 1,2,1

Hilbert's Syzygy theorem tells us that for any monomial ordering on K[x] = K[x₁,...,x_n] and R the associated ring, any finitely generated R-module M has a free resolution of length ≤ n, the number of variables.

Btw. somewhere (in the context of algorithmic treatment considerations) one speaks of a polycyclic-by-finite group, meaning it has a polycyclic subgroup of finite index. Perhaps is has to do with the finite sequence from above?

The annihilator of a module M = Coker(B) given by a presentation matrix B over the quotient ring R / I is the ideal <0> : M (by definition).

>qring Q=groebner(I);   //defines the quotient ring Q = R/I
                        //the command groebner() uses (in contrast to std()) a 
			//Hilbert series based standard basis approach (if available)
_[1]=x5y-xy5
_[2]=x20-x4y16+y20
_[3]=y21
>module B=[y2],[-2x];
>ideal ann=quotient(B,freemodule(nrows(B)));
>ann;
ann[1]=x
ann[2]=y2

And now you are invited to investigate on your own some additional topics such as elimination, Noether normalization (parametrization, the inverse to implicitization or elimination), primary decomposition, the equidimensional part and the radical, flatness, stratification, Fitting ideals, projective morphing and whatsoever.