2
$\begingroup$

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

enter image description here

$\endgroup$
4
  • 2
    $\begingroup$ Given a source $s$, can you define the level $L_i = \{ v \mid d(s,v) = i \}$? In general, it makes little sense to say you want a formal definition of something, since you are free to make any kind of definitions you want. It depends on what you want to capture and do with the definition. $\endgroup$ – Juho May 28 '17 at 13:11
  • $\begingroup$ But does this definition have a formal name? $\endgroup$ – user72738 May 28 '17 at 13:18
  • 1
    $\begingroup$ Its formal name is whatever you give it, like maybe a level structure. $\endgroup$ – Juho May 28 '17 at 13:23
  • $\begingroup$ I'm sorry if I'm not expressing myself clear. What I'm asking for is a mainstream name for the definition so that I can google on it. $\endgroup$ – user72738 May 28 '17 at 13:27
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

This is sometimes known as a level structure, and they come up in e.g., certain algorithmic applications.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.