Riktad graf
Riktad graf, även kortformerna rigraf och digraf (efter engelska: directed graph), är inom grafteori en grafvariant 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. 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.
Matematiskt sett är en riktad graf ett par ( N , B ) {\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 ( x , y ) {\displaystyle (x,y)} där x och y båda är element i N. Ordningen på paret bestämmer riktningen på bågen, ( x , y ) {\displaystyle (x,y)} är en båge från x till y.
Givet en båge b = ( x , y ) {\displaystyle b=(x,y)} är den inverterade bågen till b bågen ( y , x ) {\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]
Ett exempel på topologisk sortering, alla kanter pekar åt samma hållI 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]
En riktad acyklisk graf (engelska: directed acyclic graph, DAG) kan definieras som en riktad graf 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 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]
En riktad cyklisk graf är en riktad graf där alla bågar pekar åt samma håll i en cykel. I en riktad cyklisk graf har alla noder utgrad 1 och ingrad 1.
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 ) {\displaystyle \deg ^{-}(n)} och utgraden deg + ( v ) {\displaystyle \deg ^{+}(v)} . En nod med deg − ( v ) = 0 {\displaystyle \deg ^{-}(v)=0} kallas för en källa och en nod med deg + ( v ) = 0 {\displaystyle \deg ^{+}(v)=0} kallas avlopp.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4