Improvements of a numerical Algorithm for a certain Class of Colouring Problems

Abstract

We re-derive an algorithm used to calculate solutions for the edge-colouring and dimer problems for planar graphs. The theoretical background for this includes Pfaffian and then as Grassmann Integrals. We develop a new algorithm which is slightly faster and not restricted to planar graphs, and use this new algorithm to find results for small square, hexagonal and kagome grids. The new algorithm is generalised to a larger class of counting problems.Vi forklarer en algoritme for å finne løsninger til dimer- of kant-fargeleggingsproblemet for flate grafer. Den teoretiske bakgrunnen for algoritmen inkluderer Pfaffianen og Grassmann integraler. Vi lager en ny algoritme som er litt raskere og fungerer utenom flate grafer, og bruker denne for å finne resultater for firkant, sekskant of kagome gitre. Den nye algoritmen blir generalisert til en sto rre klasse telle problem.