Riktad graf

En riktad graf inom grafteorin är en variant av graf vars bågar (kanter) har en definierad riktning mellan de två noder (hörn) som bågen förbinder, bågen är så att säga enkelriktad. Även de förkortade beteckningarna rigraf och digraf (efter engelska directed graph) används. Via den kant som förbinder A med B, kan man bara gå från nod A till nod B, eller från B till A, inte åt båda hållen. För att kunna gå åt båda hållen behövs två kanter, en från A till B och en från B till A.

Formell definition och terminologi

Matematiskt sett är en riktad graf ett par ${\displaystyle (N,B)}$ bestående av en nodmängd N och bågmängd B. B är en delmängd av alla ordnade par av element i N, med andra ord är alla element i B par på formen ${\displaystyle (x,y)}$ där x och y båda är element i N. Ordningen på paret bestämmer riktningen på bågen, ${\displaystyle (x,y)}$ är en båge från x till y.

Givet en båge ${\displaystyle b=(x,y)}$ är den inverterade bågen till b bågen ${\displaystyle (y,x)}$. Om det för varje båge i en graf är så att även den inverterade bågen finns i grafen kallas grafen symmetrisk och kan ersättas med en vanlig, oriktad, graf.

En orienterad graf är en riktad graf erhållen ur en oriktad graf genom att man tar de oriktade bågarna i den oriktade grafen och ger dem en riktning. Skillnaden mellan en orienterad graf och en allmän riktad graf är att i en orienterad graf kan inte både en båge och dess invers finnas med.

En viktad digraf är en riktad graf med vikter på bågarna, liknande en vanlig viktad graf.

Formellt kan en riktad graf beskrivas som en uppsättning hörn (eng. Vertex) och en samling riktade kanter (eng. edges). En del teoretiker använder förkortningarna V och E från de engelska begreppen. Den riktade kanten förbinder ett par av hörn. Det första hörnet i paret är där kanten pekar ifrån och det andra hörnet i paret är där kanten pekar till.^[1]

Topologisk sortering

I en riktad graf (eng. digraph) kan försöka sortera noderna med två utfall. Antingen placerar man hörnen så att alla kanter pekar åt samma håll (som i illustrationen till höger). Då får man en topologisk sortering. Eller så rapporterar man att det är omöjligt.^[1]

Mer precist är en topologisk sortering en graf-traversering där varje hörn besöks endast efter att hörnens beroenden har besökts (alltså efter att alla hörn som har en båge riktad till hörnet i fråga har besökts). Exempelvis om hörnet V2 endast har en enda inkommande båge och den kommer från V1: då behöver hörnet V1 besökas innan hörnet V2 kan besökas. Att avgöra huruvida en topologisk sortering är möjlig gör man genom att avgöra om grafen är en Directed acyclic graph (DAG). Om en graf inte är DAG kan man inte göra topologisk sortering. ^[2]

Directed acyclic graph (DAG)

En dag kan definieras som en riktad graf (eng. digraph) utan cykler. Det betyder att kanterna mellan hörnen inte är riktade så att man kan "löpa" runt i grafen i oändliga cykler.

Formellt är en DAG (sv. riktad acyklisk graf) en riktad graf utan riktade cykler. En riktad cykel är en väg (med minst en kant) vars sista och första hörn är detsamma. ^[1]

Utgrad och ingrad

Givet en nod n i en riktad graf är nodens ingrad antalet bågar som går till noden och dess utgrad är antalet bågar som går från noden.

Ingraden för en nod n betecknas ofta ${\displaystyle \deg ^{-}(n)}$ och utgraden ${\displaystyle \deg ^{+}(v)}$. En nod med ${\displaystyle \deg ^{-}(v)=0}$ kallas för en källa och en nod med ${\displaystyle \deg ^{+}(v)=0}$ kallas avlopp.

Referenser

• Allmänt om grafer 26/2 08

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Directed graph, 10 september 2009.

Noter