Hierarchical Segmentations with Graphs: Quasi-flat Zones, Minimum Spanning Trees, and Saliency Maps

Abstract

Hierarchies of partitions are generally represented by dendrograms (direct representation). They can also be represented by saliency maps or minimum spanning trees. In this article, we precisely study the links between these three representations. In particular, we provide a new bijection between saliency maps and hierarchies based on quasi-flat zones as often used in image processing and we characterize saliency maps and minimum spanning trees as solutions to constrained minimization problems where the constraint is quasi-flat zones preservation. In practice, these results make up a toolkit for designing new hierarchical methods where one can choose the most convenient representation. They also invite us to process non-image data with morphological hierarchies. More precisely, we show the practical interest of the proposed framework for: (i) hierarchical watershed image segmentations, (ii) combinations of different hierarchical segmentations, (iii) hierarchicalizations of some non-hierarchical image segmentation methods based on regional dissimilarities, and (iv) hierarchical analysis of geographic data.

Appendices

Appendix A: Proof of Theorem 1

Proof

In order to establish Theorem 1, we will prove that the two following statements hold true:

• (1) for any connected hierarchy $\mathcal {H} = ( \mathbf{P}_0, \ldots , \mathbf{P}_\ell )$, we have: $\varPhi _G^{-1}(\varPhi _G(\mathcal {H})) = \mathcal {QFZ}(G,\varPhi _G(\mathcal {H})) = \mathcal {H}$; and

• (2) for any saliency map w, we have $\varPhi _G(\varPhi _G^{-1}(w))= \varPhi _G(\mathcal {QFZ}(G,w)) = w$.

(1) Let $\mathcal {QFZ}(G,\varPhi _G(\mathcal {H})) = (\mathbf{P}'_0, \ldots , \mathbf{P'}_\ell )$. Since $\mathcal {H}$ and $\mathcal {QFZ}(G,\varPhi _G(\mathcal {H}))$ are complete hierarchies, we have $\mathbf{P}_0 = \mathbf{P}'_0$. Thus, in order to complete the proof of (1), we will establish that $\mathbf{P}_\lambda = \mathbf{P}'_\lambda$, for any $\lambda \in \{1,\ldots ,\ell \}$. Let $\lambda \in \{1,\ldots ,\ell \}$ and let x and y be two points in V. The following statements are equivalent:

• i $\left[ \mathbf{P}'_i \right] _x = \left[ \mathbf{P}'_i \right] _y$;

• ii x and y belong to the same connected component of $\varPhi _G(\mathcal {H})^V_\lambda (G)$ [by Eq. (3)];

• iii there exists a path $\pi = (x=x_0,\ldots , x_k =y)$ from x to y in the graph $\varPhi _G(\mathcal {H})^V_\lambda (G)$;

• iv there exists a path $\pi = (x=x_0,\ldots , x_k =y)$ from x to y in the graph $(V, \{u \in E \; | \;\varPhi _G(\mathcal {H})(u) < \lambda \}$ [by Eqs. (2) and (1)];

• v there exists a path $\pi = (x=x_0,\ldots , x_k =y)$ in G from x to y such that $\varPhi _G(\mathcal {H})(\{x_{i-1},x_i\}) < \lambda$, for any $i \in \{1, \ldots , k\}$;

• vi there exists a path $\pi = (x=x_0,\ldots , x_k =y)$ in G from x to y such that $\max \left\{ j \in \left\{ 0,\ldots , \ell \right\} \; | \;\left[ \mathbf{P}_j \right] _{x_{i-1}} \ne \left[ \mathbf{P}_j \right] _{x_{i}}\right\} < \lambda$, for any $i \in \{1, \ldots , k\}$ [by Eqs. (5) and (4)];

• vii there exists a path $\pi = (x=x_0,\ldots , x_k =y)$ in G from x to y such that $\left[ \mathbf{P}_\lambda \right] _{x_{i-1}} = \left[ \mathbf{P}_\lambda \right] _{x_i}$, for any $i \in \{1, \ldots , k\}$;

• viii $\left[ \mathbf{P}_\lambda \right] _{x} = \left[ \mathbf{P}_\lambda \right] _{y}$ (since $\left[ \mathbf{P} \right] _\lambda$ is a connected partition for G).

Thus, since statements i. and viii. are equivalent, we deduce that $\mathbf{P}_\lambda = \mathbf{P}'_\lambda$, which completes the proof of statement (1).

(2) Let w be a saliency map. By the definition of a saliency map, there exists a hierarchy $\mathcal {H}$ such that $w = \varPhi _G(\mathcal {H})$. By statement (1), we have $\mathcal {H} = \varPhi _G^{-1}(\varPhi _G(\mathcal {H}))$. Thus, we deduce that $w = \varPhi _G(\varPhi _G^{-1}(\varPhi _G(\mathcal {H})))$. Then, since $w = \varPhi _G(\mathcal {H})$, we have $w = \varPhi _G(\varPhi _G^{-1}(w))$. $\square$

Appendix B: Proof of Theorem 2

In order to prove Theorem 2, we first established the following lemma.

Lemma 5

For any map z from E to $\mathbb {E}$, the following inequality holds true:

$$\begin{aligned} \varPhi _G \left( \mathcal {QFZ} \left( G, z \right) \right) \le z. \end{aligned}$$

Proof

Let $\mathcal {H} = \mathcal {QFZ}(G,z) = (\mathbf{P}_0, \ldots , \mathbf{P}_\ell )$. For any $\lambda \in \{0, \ldots \ell \}$, the partition $\mathbf{P}_\lambda$ is the connected component partition of the $\lambda$-level graph $z^V_\lambda (G)$ of G for z. By Eq. (2), we have $z^V_\lambda (G) = (V, z_\lambda (G))$, for any $\lambda \in \{0, \ldots \ell \}$. Let $u = \{x,y\}$ be any edge in E. In order, to establish Lemma , it is sufficient to prove that $z(u) \ge \varPhi _G(\mathcal {H})(u)$. For any $\lambda \in \{z(u)+1, \ldots , \ell \}$, the edge u belongs to $z_\lambda (G)$. Thus, for any $\lambda \in \{z(u)+1, \ldots , \ell \}$, we have $\left[ \mathbf{P}_\lambda \right] _x = \left[ \mathbf{P}_\lambda \right] _y$. By Eq. (6), we deduce that $\min \{ \lambda \in \{0, \ldots , \ell \} \; | \;\left[ \mathbf{P}_\lambda \right] _x = \left[ \mathbf{P}_\lambda \right] _y \} = \varPhi _G( \mathcal {H} )( u ) + 1$. Thus, we have $z(u) \ge \varPhi _G(\mathcal {H})(u)$. $\square$

Proof of Theorem 2

• 1. Let us first prove the forward implication of Theorem 2. To this end, let $\mathcal {H} = (\mathbf{P}_0, \ldots , \mathbf{P}_\ell )$ and let us assume that w is the saliency map of $\mathcal {H}$ (i.e., $w = \varPhi _G(\mathcal {H})$). Thus, we have: $\mathcal {QFZ}(G,w) = \mathcal {QFZ}(G, \varPhi _G(\mathcal {H}))$. Hence, by Theorem 1 (see, in particular, Eq. (7) which follows straightforwardly from Theorem 1), we deduce that $\mathcal {QFZ}(G,w) = \mathcal {H}$, which establishes statement 1. Let z be any map from E to $\mathbb {E}$ such that $\mathcal {QFZ}(G,z) = \mathcal {H}$ and such that $z \le w$. By Lemma , we have $\varPhi _G(\mathcal {QFZ}(G,z)) \le z$. Thus, since $\mathcal {QFZ}(G,z)= \mathcal {H}$, we deduce that $\varPhi _G(\mathcal {H}) \le z$. Hence, we have $w \le z$. Therefore, we conclude that $w = z$, which establishes statement 2.

• 2. Let us now prove the backward implication of Theorem 2. To this end, let us suppose that the map w is such that: (1) the quasi-flat zone hierarchies for w is $\mathcal {H}$ (i.e., $\mathcal {QFZ}(G,w) = \mathcal {H}$); and (2) the map w is minimal for statement (1), i.e., for any map $w'$ such that $w' \le w$, if the quasi-flat zone hierarchy for $w'$ is $\mathcal {H}$, then we have $w = w'$. By Lemma , we deduce that $\varPhi _G(\mathcal {QFZ}(G,w)) \le w$. Thus, we have $\varPhi _G(\mathcal {H}) \le w$. By Theorem 2 (see, in particular, Eq. (7)), we have $\mathcal {QFZ}(G,\varPhi _G(\mathcal {H})) = \mathcal {H}$. Thus, by definition of w (see in particular statement (2)), we deduce that $\varPhi _G(\mathcal {H}) = w$. $\square$

Appendix C: Proof of Property 

Proof

• 1. By Eq. (9), we have:

  $$\begin{aligned} \varPsi _G(\varPsi _G(w)) = \varPhi _G(\mathcal {QFZ}(G,\varPhi _G(\mathcal {QFZ}(G,w)))). \end{aligned}$$

  Hence, by Eq. (7), we deduce that:

  $$\begin{aligned} \varPsi _G(\varPsi _G(w)) = \varPhi _G(\mathcal {QFZ}(G,w)). \end{aligned}$$

  Thus, by Eq. (9), we conclude that:

  $$\begin{aligned} \varPsi _G(\varPsi _G(w)) = \varPsi _G(w). \end{aligned}$$

• 2. Lemma .

• 3. Let $w'$ be a map from E to $\mathbb {E}$ such that $w' \le w$. Let $u = \{x,y\}$ be any edge in E, we are going to prove that $[\varPsi _G(w')](u) \le [\varPsi _G(w)](u)$. By Eq. (9), we have $\varPsi _G(w') = \varPhi _G(\mathcal {QFZ}(G,w'))$ and $\varPsi _G(w) = \varPhi _G(\mathcal {QFZ}(G,w))$. Let $\mathcal {QFZ}(G,w') = (\mathbf{P}'_0, \ldots , \mathbf{P}'_{|E|})$ and $\mathcal {QFZ}(G,w) = (\mathbf{P}_0, \ldots , \mathbf{P}_{|E|})$. Let $k = [\varPsi _G(w')](u)$. From Eq. (6), we deduce that $\left[ \mathbf{P}_{k+1}\right] _x = \left[ \mathbf{P}_{k+1}\right] _y$. By Eq. (3), we have $\mathbf{P}_{k+1} = \mathbf{C}(w^V_{k+1}(G))$. Hence, there exists a path $(x_0, \ldots , x_\ell )$ such that $x_0 = x$, $x_\ell = y$, and $w(\{x_{i-1},x_i\}) < k+1$ for any $i \in \{1,\ldots ,\ell \}$. Since $w' \le w$, we also have $w'(\{x_{i-1},x_i\}) < k+1$ for any $i \in \{1,\ldots ,\ell \}$. Thus, we have $\left[ \mathbf{P}'_{k+1} \right] _x = \left[ \mathbf{P}'_{k+1} \right] _y$. Hence, by Eq. (6), we have $\left[ \varPhi _G \left( \mathcal {QFZ}(w') \right) \right] (u) \le k$. Thus, we have, $[\varPsi _G(w')](u) \le [\varPsi _G(w)](u)$. $\square$

Appendix D: Proof of Theorem 4

In order to establish the equivalence Theorem 4, we first prove the backward implication (Property ) and then the forward implication (Property )

Before establishing Properties  and 8, let us state the following propositions which can be derived from classical properties of trees.

Let S be a subset of V and let $\{x,y\}$ be an edge of G. We say that $\{x,y\}$ is outgoing from S if we have $x \in S$ and $x \in V \setminus S$ (or $y \in S$ and $x \in V \setminus S$).

Lemma 6

Let X be a connected subgraph of G. If, for any subset S of V, there is an edge u of X outgoing from S such that the weight of u is less than or equal to the weight of any edge of G outgoing from S, then, there exists a subgraph of X that is an MST of (G, w)

Let X be a graph and let $\pi = (x_0, \ldots , x_k)$ be a path in X. We say that $\pi$ is a simple path if for any two distinct i and j in $\{0, \ldots , k\}$, we have $x_i \ne x_j$. Let x and y be two vertices of X, there exists a path from x to y in X if and only if there is a simple path in X from x to y.

Property 7

Let X be a MST of (G, w). Then, the two following statements hold true:

• 1. the quasi-flat zone hierarchies of X and of G are the same; and

• 2. the graph X is minimal for Theorem 4.1, i.e., for any subgraph Y of X, if the quasi-flat zones hierarchy of Y for w is the one of G for w, then we have $Y = X$.

Proof

Let $\mathcal {H} = (\mathbf{P}_0, \ldots , \mathbf{P}_\ell ) =$ and $\mathcal {H}' = (\mathbf{P}'_0, \ldots , \mathbf{P}'_\ell )$ be the quasi-flat zone hierarchy of G and X, respectively. It can be seen that $\mathbf{P}_0 = \mathbf{P}'_0$ since $\mathcal {H}$ and $\mathcal {H}'$ are complete hierarchies. Let $\lambda \in \{1, \ldots , \ell \}$ and let x and y be two points of V. In order to complete the proof of Theorem 4.1, we are going to establish that:

• (i) if $\left[ \mathbf{P}'_\lambda \right] _x = \left[ \mathbf{P}'_\lambda \right] _y$, then $\left[ \mathbf{P}_\lambda \right] _x = \left[ \mathbf{P}_\lambda \right] _y$;

• (ii) if $\left[ \mathbf{P}_\lambda \right] _x = \left[ \mathbf{P}_\lambda \right] _y$, then $\left[ \mathbf{P}'_\lambda \right] _x = \left[ \mathbf{P}'_\lambda \right] _y$

In order to establish i), we assume that $\left[ \mathbf{P}'_\lambda \right] _x = \left[ \mathbf{P}'_\lambda \right] _y$ and we will prove that $\left[ \mathbf{P}_\lambda \right] _x = \left[ \mathbf{P}_\lambda \right] _y$. Since $\left[ \mathbf{P}'_\lambda \right] _x = \left[ \mathbf{P}'_\lambda \right] _y$, by definition of the quasi-flat zone hierarchy of X, there exists a path $\pi = (x_0, \ldots , x_k)$ in X such that $x_0 = x$, $x_k=y$, and $w(\{x_{i-1}, x_i\}) < \lambda$, for any $i \in \{1, \ldots , k\}$. Since X is a subgraph of G, the path $\pi$ is also a path in G. Thus, the vertices x and y belong to the same connected component of the $\lambda$-level graph of G. Hence, we have $\left[ \mathbf{P}'_\lambda \right] _x = \left[ \mathbf{P}'_\lambda \right] _x$.

We now establish ii) by contradiction. Therefore, we assume that $[\mathbf{P}'_\lambda ]_x \ne [\mathbf{P}'_\lambda ]_y$ and we will prove that $\left[ \mathbf{P}_\lambda \right] _x \ne \left[ \mathbf{P}_\lambda \right] _y$. Since X is a spanning tree, there exists a simple path $\pi = (x_0, \ldots , x_k)$ such that $x_0 = x$ and $x_k =y$. As $[\mathbf{P}'_\lambda ]_x \ne [\mathbf{P}'_\lambda ]_y$, there exists an index $i \in \{1, \ldots , k\}$ such that $w(\{x_{i-1},x_i\}) \ge \lambda$. Let i be the lowest index in $\{1, \ldots , k\}$ such that $w(\{x_{i-1},x_i\})\ge \lambda$. Let $X' = (V, E(X) \setminus \{\{x_{i-1},x_i\}\})$ and let C be the connected component of $X'$ that contains the vertex x. Observe that any edge u of G which is outgoing from C is such that $w(u) \ge w(\{x_{i-1},x_i\})$ (otherwise the graph $(V, E(X') \cup \{w\})$ would be connected and of weight less than the weight of X, which is a contradiction with the fact that X is a MST of (G, w)). Observe also that the vertex y belongs to $V \setminus C$ (otherwise $X'$ would be connected and of weight strictly less that the weight of X, which is a contradiction with the fact that X is a MST of (G, w)). Therefore, any path in G from x to y has an edge outgoing from C. Thus, any path in G from x to y has an edge of weight greater than or equal to $\lambda$. Hence, the vertices x and y belong to two distinct connected components of the $\lambda$-level graph of G and therefore, we have $\left[ \mathbf{P}_\lambda \right] _x \ne \left[ \mathbf{P}_\lambda \right] _y$.

Let us now prove the second proposition of Property . Let Y be a subgraph of X such that $Y \ne X$ and such that the quasi-flat zone hierarchy of Y for w is the one of G for w. Thus, we have $\mathbf{C}(w^V_\ell (Y)) = \mathbf{C}(w^V_\ell (G))$. By definition of (G, w), we have $\mathbf{C}(w^V_\ell (G)) = \{V\}$ where $\ell = |E|$. Therefore, we also have $\mathbf{C}(w^V_\ell (Y)) = \{V\}$. Hence, we deduce that $V(Y) = V$ and that Y is connected. Thus, we have $Y = X$, since X is a MST of (G, w). $\square$

Property 8

Let X be a subgraph of G such that

• (1) the quasi-flat zone hierarchies of X and of G are the same; and

• (2) the graph X is minimal for (1), i.e., for any subgraph Y of X, if the quasi-flat zone hierarchy of Y for w is the one of G for w, then we have $Y = X$.

Then, the graph X is a MST of (G, w).

Proof (by contradiction)

Let us assume that X is not a MST of (G, w). We distinguish three cases.

• i. We first assume that X is not connected. Then, the |E|-level graph of X is not connected. Thus, the |E|-level partition of X is not trivial, which is a contradiction with the fact that quasi-flat zone hierarchies of X and of G are the same since G is connected and $\mathbb {E}$ is the range of w.

• ii. We now assume that X is connected and that there exists a MST Y of (G, w) which is a proper subgraph of X. Then, by Property , the quasi-flat zone hierarchies of Y and of G are the same, which is a contradiction with (2).

• iii. We finally assume that X is connected and that there is no subgraph of X which is a MST for w. By the contraposition of Lemma , we deduce that there is a subset S of V and an edge $v = \{x,y\}$ in $E \setminus E(X)$ outgoing from S and of weight less than the weight of any edge of X outgoing from S. Let $\lambda = w(v) +1$. It can be seen that x and y belong to the same region of the $\lambda$-level partition of G. In order to complete the proof, we will show that x and y do not belong to the same $\lambda$-level partition of X, which constitutes a contradiction with statement (1). To this end, we are going to show that there is no simple path (hence, from the observation above Property , no path) in the $\lambda$-level graph of X from x to y. Since any path in the $\lambda$-level graph of X is a path in X, it is sufficient to prove that any simple path $\pi = (x_0, \ldots , x_k)$ in X such that $x_0 = x$ and $x_k =y$ is not a path in the $\lambda$-level graph of X. Without loss of generality, let us assume that x belongs to S and that y belongs to $V \setminus S$. Thus, there is an index $i \in \{1, \ldots , k\}$ such that $x_{i-1}$ belongs to S and $x_i$ belongs to $V \setminus S$. Since $\pi$ is a path in X, the edge $u = \{x_{i-1},x_i\}$ belongs to E(X). Therefore, u is an edge of X outgoing from S. Hence, by definition of v, the weight of u is greater than the weight v. Thus, the path $\pi$ is not a path in the $\lambda$-level graph of X.$\square$

Appendix E: Minimum Spanning Tree and Minimal Representation of a Hierarchy

In Sects. 5 and 6, we consider the problems of finding a minimal subgraph X and a minimal function $w'$ such that the quasi-flat zone hierarchy of G for w, the quasi-flat zone hierarchy of G for $w'$ and the quasi-flat zone hierarchy of X for w are the same. In this appendix section, we are interested in a similar problem given a connected hierarchy $\mathcal {H}$ instead of a weight map w. More precisely, we investigate the following problem:

$(P_4)$ :

given a graph G and a connected hierarchy $\mathcal {H}$, find a minimal pair (X, w) such that the quasi-flat zone hierarchy of X for w is precisely $\mathcal {H}$.

Hence, the solutions to this problem can be considered as spatially and functionally minimal representations of the given hierarchy $\mathcal {H}$.

Before stating the main result of this section, let us deduce some interesting properties from Theorem 4. These properties are useful to prove the main result of this section, namely Theorem 12.

We recall that a tree is a graph that is connected and that cannot be “reduced” by edge removal while remaining connected. More formally, a connected graph X is a tree if, for any connected subgraph Y of X such that $V(Y) = V(X)$, we have $X = Y$.

Property 9

Let $\mathcal {H}$ be a hierarchy such that $\mathcal {H} = \mathcal {QFZ}(G,w)$. If G is a tree, then we have $w = \varPhi _G(\mathcal {H})$.

Proof

Let $u = \{x,y\}$ be any edge of G and let $\lambda = \varPhi _{G}(\mathcal {H})(u)$. In order to establish Property , we will prove that $w(u) = \lambda$. Let $\mathcal {H} = (\mathbf{P}_{0}, \ldots , \mathbf{P}_{\ell })$. By Lemma , we have $\varPhi _{G}(\mathcal {H}) \le w$. Hence, we have $\underline{\lambda \le w(u)}$. Since G is a tree, the edge u appears in any path from x to y. By Eq. (6), we deduce that $\left[ \mathbf{P}_{\lambda +1}\right] _{x} = \left[ \mathbf{P}_{\lambda +1}\right] _{y}$. Thus, there is a path $\pi$ from x to y in the graph $w_{\lambda +1}^V(G)$ and the edge u appears in $\pi$. Hence, from Eq. (2), we deduce that $u \in w_{\lambda +1}(G)$ and, from Eq. (1), we can affirm that $\underline{w(u) < \lambda +1}$. Since the range of w is a subset of the integers, we deduce from the two underlined relations that $w(u) = \lambda$. $\square$

Property 10

If G is a tree, then we have $w = \varPsi _G(w)$.

Proof

Let $\mathcal {H} = \mathcal {QFZ}(G,w)$. By Eq. (9), we have $\varPsi _G(w)= \varPhi _G(\mathcal {H})$. Hence, since G is a tree, by Property , we deduce that $\varPsi _G(w) = w$. $\square$

Property 11

If X is a MST of (G, w), then for any edge u of X, we have $\varPsi _G(w)(u) = w(u)$.

Proof

Let $\mathcal {H} = \mathcal {QFZ}(G,w)$. By Theorem 4, we also have $\mathcal {QFZ}(X,w) = \mathcal {H}$. Thus, by Eq. (6), for any $u \in E(X)$, we have $\varPhi _G(\mathcal {H})(u) = \varPhi _X(\mathcal {H})(u)$. Since X is a tree, by Property , we have $\varPhi _X(\mathcal {H})(u) = w(u)$. Thus, for any $u \in E(X)$, we have $\varPhi _G(\mathcal {H})(u) = w(u)$. Hence, by Eq. (9), for any $u \in E(X)$, we have $\varPsi _G(w)(u) = w(u)$. $\square$

Let $\mathcal {H}$ be a hierarchy, let X be a subgraph of G and let f be a map from E(X) to $\mathbb {E}$. We say that (X, f) is a representation of $\mathcal {H}$ if $\mathcal {H}$ is the quasi-flat zone hierarchy of X for f. A representation (X, f) of $\mathcal {H}$ is said to be spatially minimal whenever, for any representation (Y, f) of $\mathcal {H}$ such that $Y \sqsubseteq X$, we have $Y = X$; the representation (X, f) of $\mathcal {H}$ is said to be functionally minimal if for any representation (X, g) of $\mathcal {H}$ such $g \le f$, we have $g=f$.

Due to Theorems 2 and 4, we are able to prove the following characterization of the spatially and functionally minimal representations of a hierarchy.

Theorem 12

Let $\mathcal {H}$ be a hierarchy of depth |E|, let X be a subgraph of G, and let f be any map from E(X) to $\mathbb {E}$. The pair (X, f) is a spatially and functionally minimal representation of $\mathcal {H}$ if and only if X is a minimum spanning tree of $(G, \varPhi _G(\mathcal {H}))$ and $f(u) = \varPhi _G(\mathcal {H})(u)$ for any $u \in E(X)$.

Proof

Let $g = \varPhi _G(\mathcal {H})$. In order to establish Theorem 12, we will first prove the forward implication and then the backward one.

• 1. Let us assume that (X, f) is a spatially and functionally minimal representation of $\mathcal {H}$. Let Y be any MST of (X, f). Then, by Theorem 4, we have $\mathcal {QFZ}(Y,f) = \mathcal {QFZ}(X,f) = \mathcal {H}$. Since (X, f) is a minimal representation of $\mathcal {H}$, we deduce that $Y = X$. Hence, the graph X is a tree. Then, by Property , we have $f = \varPhi _X(\mathcal {H})$. Thus, since $g = \varPhi _G(\mathcal {H})$ and since $X \sqsubseteq G$, we deduce from Eq. (6) that, for any $u \in E(X)$, we have $f(u) = g(u)$. Furthermore, we then have $\mathcal {QFZ}(X,g) = \mathcal {QFZ}(X,f)$. By definition of g, we have $\mathcal {QFZ}(G,g) = \mathcal {H}$. Thus, since (X, f) is spatially minimal and since $\mathcal {QFZ}(X,g) = \mathcal {H}$, we deduce from Theorem 4 that X is a MST of (G, g).

• 2. Let us now assume that X is a minimum spanning tree of (G, g) and that $f(u) = g(u)$ for any $u \in E(X)$. By Eq. (7), we have $\mathcal {QFZ}(G,g) = \mathcal {H}$. By Theorem 4, we deduce that $\mathcal {QFZ}(X,g) = \mathcal {H}$ and that for any $Y \sqsubseteq X$ such that $\mathcal {QFZ}(Y,g) = \mathcal {H}$, we have $Y = X$. By definition of f, we can then also deduce that $\mathcal {QFZ}(X,f) = \mathcal {H}$ and that for any $Y \sqsubseteq X$ such that $\mathcal {QFZ}(Y,f) = \mathcal {H}$, we have $Y=X$. Thus, the pair (X, f) is a spatially minimal representation of $\mathcal {H}$. Furthermore, since X is a tree, by Property , we have $\varPhi _X(\mathcal {H}) = f$. Hence, by Theorem 2, we deduce that the representation (X, f) of $\mathcal {H}$ is also functionally minimal.$\square$