Riktad graf

Från Wikipedia
Hoppa till: navigering, sök
Ett enkelt exempel på en riktad graf.

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.

Formell definition och terminologi[redigera | redigera wikitext]

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

Givet en båge b=(x,y) är den inverterade bågen till b bågen (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 ritkad 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 ingrad[redigera | redigera wikitext]

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 \deg^-(n) och utgraden \deg^+(v). En nod med \deg^-(v)=0 kallas för en källa och en nod med \deg^+(v) = 0 kallas avlopp.

Referenser[redigera | redigera wikitext]

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia