En riktad graf inom grafteorin är en variant av graf vars bågar (kanter) har en definierad riktning mellan de två noder 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.

Ett enkelt exempel på en riktad graf.

Formell definition och terminologiRedigera

Matematiskt sett är en riktad graf ett par   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   där x och y båda är element i N. Ordningen på paret bestämmer riktningen på bågen,   är en båge från x till y.

Givet en båge   är den inverterade bågen till b bågen  . 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.

Utgrad och ingradRedigera

 
En riktad graf med ingrader och utgrader utsatta på noderna med formen (ingrad, utgrad).

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   och utgraden  . En nod med   kallas för en källa och en nod med   kallas avlopp.

ReferenserRedigera

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