Eulerska grafer
egenskaper och tillämpningar
Denna uppsats handlar om de så kallade eulerska graferna och grafer nära besläktade med dessa. En eulersk graf är en graf där det går att traversera alla kanter i grafen så att varje kant förekommer exakt en gång i traverseringen. Den struktur dessa grafer har uppfyller de villkor Euler ställde upp 1735 då han studerade det klassiska problemet med de sju broarna i Königsberg. Både teoretiska aspekter, som cykeldekomposition och kompatibla eulervägar, samt praktiska tillämpningar, som det kinesiska brevbärarproblemet och DNA-sekvensering (där man använder en de Bruijn-graf) behandlas i den här texten. Här redogörs även för kända och mindre kända metoder för enumeration av eulerska och semieulerska grafer. Dessa innefattar enumeration med hjälp av explicita formler, genererande funktioner samt algoritmiskt via generering. Tabeller med antal grafer presenteras för olika varianter av eulerska grafer (märkta, omärkta, planära etc.). Vid omärkt enumeration används endast den algoritmiska metoden, vilken också har använts för att generera och visa alla eulerska och semieulerska grafer med sju kanter, både enkla grafer och multigrafer.