3
$\begingroup$

I am a software engineer. I'm dealing with a data structure which represents a digraph of a very specific structure. I am wondering if this class of graph has been identified and studied as I need to do a fair bit of work with it and would love to not reinvent the wheel if not necessary.

The structure of the graph is as follows. It is a digraph wherein each vertex has at most one edge leading from it. Note that a vertex is allowed to have zero edges leading from it as well. There is no restriction on the edges that lead into a vertex, nor is there a restriction on the graph being cyclic.

Improve this question
$\endgroup$
1
  • $\begingroup$ If you needed to compute iterates, find connected components, or store it efficiently, you might mention that. Otherwise, it is not clear how an answer will help, as most optimized algorithms handle more general cases depending on the action desired. Gerhard "Email Me About System Design" Paseman, 2011.07.14 $\endgroup$
    – Gerhard Paseman
    Commented Jul 14, 2011 at 19:02

2 Answers 2

Reset to default
7
$\begingroup$

Qiaochu Yuan has already provided an answer in terms of functions, but if you prefer to think graph-theoretically these things are known as directed pseudoforests.

Improve this answer
$\endgroup$
5
$\begingroup$

If I understand you correctly, such a thing is generally called a partial function (from the vertex set to itself).

Improve this answer
$\endgroup$
2
  • $\begingroup$ This answer is correct, and gives the right emphasis (pointing out that the out-degree-zero-vertices permitted by the OP can be interpreted as points of a domain where a function is undefined), but, since this very usual (whoever is using this: search for yourself) technical term has not been mentioned in this thread, let me mention that the quiver obtained by augmenting each out-degree-zero vertex by a loop, so that then each vertex has outdegree precisely one, is usually called a functional graph (cf. e.g. Gessel--Stanley: "Algebraic Enumeration", Handbook of Combinatorics) $\endgroup$
    – Peter Heinig
    Commented Jul 22, 2017 at 17:57
  • $\begingroup$ Another terminological comment, concerning the comment above: "functional graphs" are also often called "functional digraphs". There exists a convention in combinatorics according to which one would not be allowed to call them "functional digraphs": in parts of combinatorics (cf. e.g. the monograph "Digraphs" by Bang-Jensen--Gutin), "digraph with vertex set $V$" essentially means "subset of $(V\times V)\setminus \{ (v,v)\colon v\in V\}$", i.e., loops are then disallowed. This, and since the adjective "functional" seems emphasis enough, I recommended functional graph above. @jinxidoru $\endgroup$
    – Peter Heinig
    Commented Jul 22, 2017 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .