Graf (grafteori)

Från Wikipedia
Hoppa till: navigering, sök
För andra betydelser, se Graf.

En graf är det grundläggande begreppet inom grafteorin. Beroende på vad man skall ha grafer till, definierar man formellt grafer på litet olika sätt. 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 kan man använda uv för att beteckna en kant mellan hörnen u och v, 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 kurvornam (kanterna) löper, utan bara av på vilket sätt hörn förbinds med varandra.

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

För ändliga grafer så 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 doch grafen antas vara enkel, d. v. s. 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. Man kan då beskriva samma kant på två sätt: 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, i analogi med det engelska digraphs för "directed graphs"). 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. När man ritar riktade grafer brukar man använda pilar för att markera 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[redigera | redigera wikitext]

Den vanligaste typen av grafer, enkla och oriktade, I detta fall definieras oftast kanterna som tvådelmä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 ettdelmängder av V.

För enkla riktade grafer byter man helt enkelt ut dvådelmä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[redigera | redigera wikitext]

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

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

Beteckningar[redigera | redigera wikitext]

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.

Externa länkar[redigera | redigera wikitext]

Se även[redigera | redigera wikitext]