Grafteori - Introduktion och Begrepp

Inom grafteori så behandlas grafer som mera liknar kartor där olika städer (kallas hörn) binds ihop med vägar (kallas kanter). Dessa grafer har alltså inte särskilt många likheter med funktioners grafer utan beskriver mer relationer mellan olika noder.

Man kan likna en graf med en karta över kollektivtrafiken i en stad där olika hållplatser binds ihop med linjer där linjerna representerar hur bussar/tåg/spårvagnar trafikerar vägarna mellan hållplatsen. När dessa relationer sedan förenklas till en mer schematisk bild så bildas en så kallad graf. Dessa grafer kan sedan användas för att beräkna en så bra väg som möjligt eller till att reducera kostnader vid produktion.

I en graf brukar de olika delarna kallas för Hörn/Nod, Kant/Båge och Ögla/Loop. Här väljer vi att kalla dessa delar för följande:

När man vandrar på en graf går man en ”bana” från hörn till hörn på något vis. En vandring som börjar och slutar i samma hörn kallas för en sluten vandring. Man brukar dela upp de olika sätten att vandra på inom följande kategorier:

• Exempel på en graf och innebörden av Ögla/loop, Hörn/nod, Kant/Bäge.
• Exempel på en väg.
• Exempel på en krets.
• Exempel på en stig.
• Exempel på en cykel.