Vandringar, vägar och kretsar
I det förra avsnittet introducerade vi begreppet graf med den betydelse som detta begrepp har inom det grafteoretiska området.
I det här avsnittet ska vi bygga vidare på vad vi nu vet om grafer genom att studera vandringar, vägar och kretsar i grafer, och vilka slutsatser som vi kan dra av detta, bland annat vad gäller förekomsten av så kallade Eulervägar och Eulerkretsar.
Kapitlet avslutas med att vi i nästa avsnitt går igenom stigar och cykler, bland annat så kallade Hamiltonstigar och Hamiltoncykler.
Vandringar och vägar
Vi antar att vi har en graf som kan illustreras på följande sätt:
Låt oss säga att hörnen i denna graf representerar fem städer och kanterna representerar de sex järnvägssträckningar som sammanbinder städerna.
Om vi till exempel befinner oss i stad a och vill resa till stad e längs någon av dessa järnvägar, då kan detta göras på flera olika sätt. En möjlig resväg är från stad a via stad d till stad e (vilket vi kan uttrycka med hörnföljden a, d, e), men vi kan även till exempel välja resvägen från stad a via stad d och stad c till stad e (alltså a, d, c, e). Vi kan även välja att besöka en och samma stad flera gånger (till exempel a, b, a, d, e).
Vi använder begreppet vandring (engelska: walk) för varje val av "resväg" som består av en hörnföljd
$${v}_{1},\,{v}_{2},\,...\,,\,{v}_{n}$$
där efterföljande hörn i hörnföljden är grannar (det vill säga att det går en kant mellan hörnen). Hörnföljden a, d, e i exempelgrafen ovan är alltså en vandring, eftersom hörnen a och d respektive d och e är grannar.
Som vi har kunnat konstatera tidigare kan en vandring innehålla samma hörn flera gånger, vilket till exempel var fallet med vandringen a, b, a, d, e, där hörnet a besöks två gånger. En vandring får även innehålla samma kant fler än en gång, vilket var fallet i det nyss nämnda exemplet med vandringen a, b, a, d, e, då kanten {a, b} under vandringen användes dels i riktning från a till b, och dels från b till a.
En vandring där ingen kant passeras mer än en gång kallar vi en väg. Således är vandringen a, d, e en väg, men det är inte vandringen a, b, a, d, e.
Eulervägar och Eulerkretsar
En speciell typ av väg, som ofta förekommer i problem, är en så kallad Eulerväg, uppkallad efter matematikern Leonard Euler. En Eulerväg (engelska: Eulerian walk) är en väg som innehåller var och en av kanterna som finns i kantmängden E exakt en gång.
I vår exempelgraf ovan är t.ex. vandringen (d, a, b, c, e, d, c) en Eulerväg, eftersom denna vandring sker längs var och en av de kanter som finns i kantmängden E:
Euler stötte på denna typ av väg då han studerade ett problem som kommit att kallas Königsbergs sju broar. Genom staden Königsberg (nuvarande Kaliningrad) vid Östersjöns sydöstra strand rinner floden Pregel, som delar staden i två större landområden. I floden ligger dessutom två öar. Landområdena på vardera sidan om floden och landområdena på öarna i floden sammanbands av sju broar på ett liknande sätt som vi visar i figuren nedan.
Det problem som Euler funderade på var om man kunde ta en promenad genom staden på ett sådant sätt att var och en av de sju broarna korsades exakt en gång var (under förutsättning att man bara fick gå från ett landområde till ett annat via broarna).
Euler analyserade problemet med hjälp av en graf, där hörnen representerade de fyra landområdena och kanterna representerade de sju broarna. Det resulterade i en graf liknande denna:
Vad Euler kom fram till efter att ha analyserat detta problem var att han sökte efter en väg som passerade varje kant i grafen exakt en gång, vad som senare kommit att kallas en Eulerväg.
Han formulerade då det villkor som gäller då en graf innehåller (minst) en Eulerväg:
En graf innehåller minst en Eulerväg om högst två av grafens hörn är udda hörn.
Att detta villkor är nödvändigt för att en Eulerväg ska finnas i en graf kan vi inse genom följande informella resonemang: För att en väg genom en graf ska kunna fortsätta via ett hörn krävs för varje sätt att nå hörnet även ett sätt att lämna detta hörn. Därför måste varje hörn i grafen som ingår i Eulervägen ha ett jämnt antal kanter, förutom eventuellt hörn där vi inleder eller avslutar vandringen. Om det finns en Eulerväg i grafen kan därför bara de hörn där vi inleder och avslutar vandringen vara udda hörn.
Finns det (minst) en Eulerväg i en graf och grafen innehåller udda hörn, då vet vi att Eulervägen måste inledas och avslutas i dessa udda hörn. Att känna till detta underlättar för oss då vi vill ta reda på vilken eller vilka Eulervägar som finns i en graf.
När vi nu känner till villkoret för existens av Eulervägar kan vi avgöra om grafen i problemet Königsbergs sju broar innehåller (minst) en Eulerväg. Denna graf har ett hörn som har grad 5 och tre hörn som har grad 3. Alltså är samtliga fyra hörn i grafen udda hörn. Eftersom grafen har fler än två hörn som är udda hörn kan grafen inte innehålla någon Eulerväg. Därför finns det inte heller något sätt att under en promenad av den typ som Euler beskrev korsa var och en av stadens broar exakt en gång var.
Om vi inleder och avslutar en vandring i samma hörn, och denna vandring dessutom är en Eulerväg, då kallar vi denna vandring en Eulerkrets (engelska: Eulerian circuit). Med denna definition är alltså alla Eulerkretsar även Eulervägar, men det omvända behöver inte vara fallet.
Eftersom en Eulerkrets är en Eulerväg som inleds och avslutas i samma hörn, måste samtliga hörn i grafen vara jämna hörn för att grafen ska innehålla en Eulerkrets. Det ger oss följande villkor för existensen av Eulerkretsar i en graf:
En graf innehåller minst en Eulerkrets om alla grafens hörn är jämna hörn.
Avgör om följande grafer har någon Eulerväg och/eller någon Eulerkrets.
Eftersom vi nu känner till vilka villkor som gäller för att en graf ska ha någon Eulerväg respektive Eulerkrets börjar vi med att undersöka om hörnen i graferna är udda eller jämna hörn.
Den vänstra grafen ovan har tre hörn med grad 2 (hörnen a, d och f) och tre hörn med grad 4 (hörnen b, c och e). Alltså är samtliga hörn i grafen jämna hörn. Därmed har denna graf minst en Eulerväg och minst en Eulerkrets.
Nedan visar vi en möjlig Eulerkrets (och samtidigt Eulerväg) i denna graf (a, c, f, e, d, b, e, c, b, a). Även andra Eulervägar och Eulerkretsar än denna är möjliga:
Den högra grafen ovan har två hörn med grad 2 (hörnen c och d), två hörn med grad 3 (hörnen a och f) och två hörn med grad 4 (hörnen b och e). Alltså är två av hörnen i grafen udda hörn (övriga fyra hörn är jämna hörn). Därmed har denna graf minst en Eulerväg. Däremot kan inte denna graf ha någon Eulerkrets, eftersom inte alla grafens hörn är jämna hörn.
Eftersom denna graf har två udda hörn måste en Eulerväg inledas respektive avslutas i dessa hörn.
Nedan visar vi en möjlig Eulerväg i denna graf (a, b, c, f, e, d, a, e, b, f). Även andra Eulervägar än denna är möjliga:
I nästa avsnitt kommer vi att introducera begreppen stigar och cykler, bland annat så kallade Hamiltonstigar och Hamiltoncykler, som begreppsmässigt ligger nära vad vi har studerat i det här avsnittet.