Graf (grafteori)

För andra betydelser, se 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.

En enkel oriktad graf med sex hörn och sju kanter.

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å viktade grafer. Då har varje kant ett associerat värde (en kostnad eller längd).

Formella definitioner

Den vanligaste typen av grafer utgörs av de enkla och oriktade. I detta fall definieras oftast kanterna som 2-mängder av hörnmängden V, alltså som vissa delmängder av V med precis två element var. Exempelvis kan grafen på bilden ovan formellt specificeras som

$(\{1,2,3,4,5,6\},\ \{\{1,2\}\,,\{1,5\}\,,\{2,3\}\,,\{2,5\}\,,\{3,4\}\,,\{4,5\}\,,\{4,6\}\})$.

Om grafen tillåts ha öglor, men inte parallella kanter, så kan en likartad definition tillämpas, där öglorna representeras av 1-mängder av V.

För enkla riktade grafer byter man helt enkelt ut 2-mängder mot (ordnade) par.

Multigrafer kan definieras formellt med hjälp av multimängder, eller genom att man för varje kant anger dess ändpunkter.

Benämningar på speciella grafer

Inom grafteorin används ett antal benämningar på (enkla oriktade) grafer av särskilt intresse:

• I en komplett graf finns en kant mellan varje par av hörn.
• I en sammanhängande graf finns minst en väg mellan varje par av hörn.
• I ett träd finns exakt en väg mellan varje par av noder.
• I en skog finns som mest en väg mellan varje par av noder.
• I en bipartit graf kan noderna delas upp i två grupper så att varje kant förbinder en nod i ena gruppen med en nod i den andra.

Beteckningar

V(G)	Mängden av alla hörn i grafen G
E(G)	Mängden av alla kanter i grafen G
δ(G)	Den minimala graden hos något hörn i grafen G
Δ(G)	Den maximala graden hos något hörn i grafen G
Kn	Komplett graf av ordning n
Kn,m	Komplett bipartit graf med n respektive m hörn i varje del
$\omega _{G}$	Antalet komponenter i $G$.

Se även

• Hypergraf

Externa länkar

• Wikimedia Commons har media som rör graf.