graf

En graf är det grundläggande begreppet inom grafteorin. Grafer definieras på olika sätt beroende på användningsområde. Den grundläggande idén är dock densamma: en graf består av ett par (V,E) av mängder, där V är en mängd av hörn (även kallade noder eller punkter) och E en mängd av kanter (även kallade bågar) mellan par av hörn. Ofta betecknar uv en kant mellan hörnen u och v, vilka utgör kantens ändpunkter. I en ändlig graf är E och V ändliga. Grafer ritas ofta som punkter eller prickar som förbinds av raka eller krökta kurvor. Det är dock viktigt att grafens egenskaper inte bestäms av var dessa punkter (hörn) placeras eller av hur kurvorna (kanterna) löper, utan bara av på vilket sätt hörn förbinds med varandra. För ändliga grafer används ibland beteckningen ordning för antalet hörn och storlek för antalet kanter. Ibland tillåts grafer ha öglor eller loopar, vilket betyder kanter där båda ändarna utgörs av samma hörn. Om man inte särskilt anger detta, så brukar man dock anta att grafen saknar öglor (är öglefri eller loopfri). Ibland tillåts grafer ha flera kanter mellan samma par av hörn, parallella kanter. Grafer som tillåts ha öglor och/eller parallella kanter kallas ibland multigrafer. Om man inte särskilt anger att sådant tillåts, så brukar dock grafen antas vara enkel, det vill säga vara öglefri och sakna parallella kanter. De vanligaste graferna har oriktade kanter. Det betyder att en kant från u till v är samma sak som en kant från v till u. Samma kant kan då beskrivas på två sätt, med samma betydelse: uv och vu. Mer teoretiskt så innehåller kantmängden E delmängder av V med två element. Det finns också riktade grafer (ibland kallade rigrafer). Då är en kant från u till v inte detsamma som en kant från v till u. Alltså är uv och vu olika kanter. Kanten uv har startpunkten u och ändpunkten v. Riktade grafer brukar ritas med pilar för att visa riktningen. I en riktad graf är alltså en kant (ett element i kantmängden) ett ordnat par av noder. Det finns också . Då har varje kant ett associerat värde (en kostnad eller längd).