patternMinor
Formal definition on graph levels
Viewed 0 times
definitionformallevelsgraph
Problem
I'm looking for a formal definition of "graph levels" on a DAG. This example should illustrate what I mean by this.
The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.
Level 0 : node 0
Level 1 : node 3, node 4
Level 2 : node 1, node 2
Level 3 : node 5
The node 0 has no edges directed towards it, therefore this has level 0. Next is is 3 and 4 which will have level 1 and so on.
Level 0 : node 0
Level 1 : node 3, node 4
Level 2 : node 1, node 2
Level 3 : node 5
Solution
A DAG (or poset) is ranked or graded if it is possible to assign nodes a rank function $r$ such that if $(x,y)$ is a directed edge, $r(y) = r(x)+1$. We usually choose $r$ so that $\min r = 0$. See for example the Wikipedia article on graded poset.
Context
StackExchange Computer Science Q#75980, answer score: 3
Revisions (0)
No revisions yet.