Stigar och cykler
Tidigare i det här kapitlet har vi introducerat det centrala grafteoretiska begreppet graf och gått igenom en del av de egenskaper som sådana grafer har. I det föregående avsnittet undersökte vi även vandringar, vägar och kretsar i grafer, och hur vi kan avgöra om en graf innehåller någon Eulerväg och/eller Eulerkrets.
I det här avsnittet ska vi introducera begreppen stig och cykel, samt så kallade Hamiltonstigar och Hamiltoncykler.
Stigar och cykler
I det förra avsnittet introducerade vi begreppet vandring (engelska: walk), som kan ses som 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). Om ingen kant i vandringen passeras mer än en gång, kallar vi den vandringen för en väg.
Om de hörn som ingår i en väg passeras exakt en gång var, kallar vi den vandringen för en stig. Om en stig dessutom börjar och slutar i samma hörn, kallar vi den stigen för en cykel. Alla cykler är alltså även stigar, medan en stig inte nödvändigtvis även är en cykel.
Tidigare har vi stött på denna graf:
Nedan till vänster har vi ett exempel på en stig (a, b, c) i grafen ovan och nedan till höger har vi ett exempel på en cykel (a, b, c, d, a) i samma graf:
Hamiltonstigar och Hamiltoncykler
En partiledare är ute på valturné och ska besöka ett antal utvalda städer, utan att besöka någon av dessa städer mer än en gång var under turnén.
Det här problemet kan vi analysera med hjälp av en graf, där hörnen representerar de utvalda städerna och kanterna representerar resvägarna mellan städerna.
Vad vi är ute efter är en stig sådan att varje hörn i grafen besöks exakt en gång. En sådan stig kallar vi en Hamiltonstig, uppkallad efter matematikern William R. Hamilton.
Om en Hamiltonstig dessutom inleds och avslutas i samma hörn, kallar vi den en Hamiltoncykel.
Nedan till vänster har vi ett exempel på en Hamiltonstig i en graf (a, b, c, d, e) och nedan till höger har vi ett exempel på en Hamiltoncykel (och Hamiltonstig) i samma graf (a, b, c, e, d, a):
När vi i det förra avsnittet studerade Eulervägar och Eulerkretsar, kom vi fram till att det finns enkla villkor som avgör huruvida en graf innehåller någon Eulerväg och/eller Eulerkrets. Någon motsvarighet till detta har man inte funnit vad gäller förekomst av Hamiltonstigar och Hamiltoncykler. Att i det generella fallet avgöra om en graf innehåller någon Hamiltonstig och/eller Hamiltoncykel är därför ett mycket svårt problem.
Handelsresandeproblemet
Ett klassiskt matematiskt problem inom det grafteoretiska området som berör stigar är det så kallade handelsresandeproblemet (engelska: the travelling salesman problem (TSP)).
Problemet går ut på att en försäljare ska besöka en viss uppsättning städer och vill ta reda på den kortaste resvägen (mätt i t.ex. avstånd, tid eller pengar) som finns för att klara av detta uppdrag, om försäljaren inleder och avslutar resan i samma stad.
Detta problem kan analyseras med hjälp av en graf, där hörnen representerar städerna och kanterna representerar transportvägarna mellan städerna. För att ange hur långt det är mellan två hörn i grafen, använder man sig av vikter som anges för var och en av grafens kanter, och den resulterande grafen kallas därför en viktad graf.
Nedan har vi ett exempel på en viktad graf:
Den viktade grafen ovan innehåller (minst) en Hamiltoncykel. Kan du hitta den? Vilken längd har den Hamiltoncykeln (cykelns längd är lika med summan av vikterna längs de kanter som ingår i cykeln)? Är detta den kortaste Hamiltoncykeln i grafen?
Trots att detta problem är enkelt att definiera är det ofta mycket resurskrävande att lösa när storleken på de inblandade graferna ökar.