What's the meaning of functional graph?
I'm reading Guerino Mazzolla's Comprehensive Mathematics for Computer Scientists, there's a definition:
Definition 9 A graph $g$ is called functional if $(u,v)\in g$ and $(u,w)\in g$ imply $v=w$.
I read on Mathworld:
A functional graph is a directed graph in which each vertex has outdegree one, and can therefore be specified by a function mapping $\{1,...,n\}$ onto itself.
From Mazzola's book definition I understood that a graph is functional if it has two equal ordered sets(?), Mathworld's seems to tell me that Mazzola's definition is actually indicating a mapping between those ordered sets, I also guess that functional comes from function and it's about a graph that's produced by a function.
$\endgroup$1 Answer
$\begingroup$Both definitions you give say that if you name one vertex $u$, then there is exactly one "value-vertex". This is just the way a (necessarily single valued) function works and it is graphically represented in the way that every vertex has one outgoing directed arrow (necessarily to some vertex inside the graph).
I feel the picture from the wikipedia says it all. For a function, from $\mathbb{R}$ to $\mathbb{R}$ say, you'd usually draw the graph of the function as a curve in $\mathbb{R}\times \mathbb{R}$. The insight is that if $\mathbb{dom}(f)$ is finite as well as $\mathbb{dom}(f)=\mathbb{codom}(f)$, then you can just use the x-axis as the y-axis. The arrows denote which variables lead to which values.
