Grafens

Grafens är ett fiktivt begrepp som används i denna artikel för att illustrera en särskild klass av skiktade, riktade grafer. Begreppet syftar till att beskriva strukturer där relationer arbetar i ett tydligt nedåtgående flöde mellan nivåer, och används i exempel och förklaringar i pedagogiskt sammanhang. Det är viktigt att betona att grafens inte är en etablerad term inom den vedertagna grafteorin, utan ett konstruerat exempel för denna artikel.

Definition och egenskaper

En graf av typen grafen består av ett ändligt antal noder och kanter samt en uppdelning av noderna i nivåer från 0 till k. Varje kant går från nivå i till nivå i+1, vilket gör grafen skiktad och garanterar att den är acyklisk. Det finns en unik rot i nivå 0, och varje övrig nod har minst en inkommande kant. På så sätt bildas ett hierarkiskt flöde där information eller material rör sig nedåt genom nivåerna. Grafen kan innehålla flera föräldrarskap för en nod (flera kanter som går från olika noder i nivå i till samma nod i nivå i+1), vilket ger både spridning och redundans inom strukturen.

Exempel och konstruktion

Ett enkelt exempel består av fyra noder: R i nivå 0, A och B i nivå 1, samt C i nivå 2. Kantstrukturen kan vara R→A, R→B samt A→C och B→C. Sådan uppbyggnad illustrerar hur flera grenar kan sammanfalla i en senare nivå, samtidigt som flödet kvarstår nedåt i grafen.

Användning och algoritmer

Grafens används som modell för hierarkiska processer som produktionsflöden, data lineage eller projektplanering, där det är naturligt att spåra hur beslut och material sprids genom olika skikt. Vanliga grafalgoritmer som topologisk sortering och antal linjer av möjlig nedstäckning kan tillämpas på grafen, med tidkomplexitet i linjär tid relativt antalet kanter och noder.

Se också

Grafer, DAG, skiktade grafteorier, koncentrerade nätverk.