I. INTRODUCTION

The concept of minimum spanning tree (MST) was originally developed in the field of graph theory. In the last two decades we see its widespread use in many disciplines such as biology, social science, economy, antrophometry and general taxonoml' Il], data analysis [2], regression analysis [4] and [5], computer science [6], networking [8], and multivariate and clustering analysis [10].

The ability to detect the uniqueness of MST is the first great problem for statisticians in using MST for their statistical analysis. The complexity of statistical analysis of a dissimilaritv data matrix depends on the uniqueness of its MST (see [5], and [10]). Unfortunately, as far as we know (see [l], [3], [7], [8], [9], and [lll). there is no algorithm that can detect the uniqueness of MST. The second great problem is the fact that only one MST can be given by all existing algorithms, even for the case where there are actually more than one MST. This fact can also be found in theoritical literatures (see [6], [9]. and I l]). In these trvo circumstances, Proposition l, Proposition 2 and Proposition 3 are the main result of this work. In particular. Proposition 3 provides us with tu'o fundamental results:

• l. A necessary and suffrcient condition for the uniqueness of MST.
• 2. An algorithm for constructing the union of all possible MSTs which. if it is not unique, gives us all MSTs.

The basic problem in this paper, firstly is to propose and to show a necessary and sufficient condition for uruqueness of MST of a dissimilaritl,'. Secondly is to give an algorithm for finding all possible MSTs, if there are actually more than one MST. For this purpose we consider a dissimilarity as a fuzzy- relation. Some basic concepts can be found in [3].

Suppose R a fuzzy relation on a set I; Card(I) = n and for every (x,y) in IxI we have 0 a tr^ (x,y) < o, where pr is a membership function on R. In this paper we develop a fundamental property of min-max transitive closure R- of \ where R is a dissimilarity, in connection with subdominant ultrametric. Another representation of R" can be seen in [7] and [l]. The relationship between subdominant ultrametric and minimum spanning tree such as shown in [2], [6], and [9] will be exploited in order to derive a necessary and sufficient condition for the uniqueness of minimum spanning tree in a dissimilariry*.

2. TRANSITIVE CLOSURE

A fuzzy relation R on I is called max-min transitive if for all x, Y , z in I we have

\[\mu_{R}\left(x,\,z\right)\leq V_{y}\left\{ \mu_{R}\left(x,y\right)\wedge\mu_{R}\left(y,z\right)\right\}\]

It is known that max-mrn transitiviS' of R can be verified through mar-min composition o. If R02 = R o R is a fuz4 relation defined by

\[\mu_{R^{02}}(x,z) = V_y \left\{ \mu_R(x,y) \wedge \mu_R(y,z) \right\}\] for all x, y, z in I, we have the following properties [7].

Theorem 1 If \(R^{02} = R\), then R is max-min transitive.

Theorem 2 R is max-min transitive if and only if \(R^{02} \subset R\).

Since I is finite, the max-min transitive closure R of R has the following representation:

\[\mathbf{R}^- = \mathbf{R} \cup \mathbf{R}^{02} \cup \mathbf{R}^{03} \cup \dots \cup \mathbf{R}^{ok},\] for an integer k; \(1 \le k \le n\), where \(R^{ok} = R\) o R o ... o R, k times max-min composition o of R.

Like R^-, the min-max transitive closure R⁺ can be written as

\[R^+ = R \cap R^{*2} \cap R^{*3} \cap ... \cap R^{*k}\] for an integer k , \(1 \le k \le n\) , where \(R^{*k}\) = R * R * ... * R, k times min-max composition * of R and

\[\mu_{R^{\prime 2}}\left(x,z\right)=\frac{\Lambda}{y}\left\{\mu_{R}\left(x,y\right)\vee\mu_{R}\left(y,z\right)\right\}\]

If \(R^{-c}\) and \(R^{c+}\) represent respectively the complement of \(R^{-}\) and min-max transitive closure of \(R^{c}\), it can be shown that \(R^{-c} = R^{c+}\) and \(R^{+c} = R^{-c}\). Hence by De Morgan's rule we have \(R^{-} = R^{c+c}\) and \(R^{+} = R^{c-c}\). These equalities enable us to work with either \(R^{-}\) or \(R^{+}\). Although those representations are very usefull, but it is still not comfortable to work with. The following alternative form which is more convenience for constructing \(R^{-}\) is given in [7].

Theorem 3 Suppose that R is a fuzzy relation on I. Let

\[1^* (x,y) = \bigvee_{c \text{ di } \zeta} 1(c), \text{ where}\] a. \[\zeta = \{c \mid c = (x = x_{i_1}, x_{i_2}, ..., x_{i_r} = y)\}\] is a chain from x to y}

\[b.\ l(c) = \mu_R \, (\, (x_{i_1}, x_{i_2})^{\wedge} \mu_R \, (x_{i_2}, x_{i_3})^{\wedge} ...^{\wedge} \mu_R \, (x_{i_{r-1}}, x_{i_r}).\]

Then \[\mu_{p^-}(x,y) = l^*(x,y)\], for all x and y in I.

In practice this theorem is still difficult to be implemented. In the next section we will restrict our discussion in the case where R is a dissimilarity and we derive a fundamental property in connection with its sub-dominant ultrametric in order to construct simple computation.

3. MIN-MAX TRANSITIVE CLOSURE AND SUB-DOMINANT ULTRAMETRIC

Suppose R a dissimilarity associated to dissimilarity index d on I. Hence R is a symmetric and anti-reflexive fuzzy relation, where \(\mu_R(x,y) = d(x,y)\) for all x and y in I. In the following proposition we show that, in this case, \(R^+\) has a very convenience representation.

Proposition 1 If R is a dissimilarity on I, then \(R^+ = R^{\bullet k}\) for an integer k; \(1 \le k \le n\).

Proof

We know that for an integer k; \(1 \le k \le n\),

\[\mathbf{R}^{+} = \mathbf{R} \cap \mathbf{R}^{+2} \cap ... \cap \mathbf{R}^{+k}\]

Now we show that the right hand side is equal to R*k

By definition,

\[\mu_{R^{*2}}(x,z) = {}_{y}^{\Lambda} {\{\mu_{R}(x,y) \lor \mu_{R}(y,z)\}},\] for all x, y and z in I. Especially if y = z, then

\[\mu_{R^{\bullet_2}}(x,z) \leq \mu_{R}(x,z) \vee \mu_{R}(z,z)\]

But \(\mu_R(z,z) = 0\). Hence,

\[\mu_{R^{*,2}}(x,z) \leq \mu_{R}(x,z)\] for all x and z in I or \(R^{*2} \subseteq R\). In general we have

\[R^{*k} \subseteq ... \subseteq R^{*9} \subseteq R^{*2} \subseteq R\].

It implies that \(R^+ = R^{*k}\).

Now we show a fundamental property of \(R^+\) in connection with sub-dominant ultrametric (SDU) of dissimilarity R.

Proposition 2 If R is a dissimilarity on I, then R⁺ is the SDU of R.

Proof

Theorem 3 tells us that

\[\mu_{R^{+C}}(x, y) = \mu_{R^{C-}}(x, y) = \max_{C \in A_{C,C}} 1(C)\] where \(C = (x = x_{i_1}, x_{i_2}, \dots, x_{i_r} = y)\) is a chain from x to y.

If \(\alpha = \mu_{\chi^C}(x,x)\) for all x in I, then

\[\begin{split} \mu_{R^{+C}}(\mathbf{x}, \mathbf{y}) &= \max_{C} \; \{ \min_{k} \; \{ \mu_{R}(\mathbf{x}_{i_{k}}, \; \mathbf{x}_{i_{k+1}}) \} \} \\ &= \max_{C} \; \{ \min_{k} \; \{ \mu_{R^{C}}(\mathbf{x}_{i_{1}}, \mathbf{x}_{i_{2}}), \; ..., \; \mu_{R^{C}}(\mathbf{x}_{i_{r-1}}, \mathbf{x}_{i_{r}}) \} \} \\ &= \max_{C} \; \{ \alpha - \max_{k} \; \{ \alpha - \mu_{R^{C}}(\mathbf{x}_{i_{1}}, \mathbf{x}_{i_{2}}), \; ..., \; \alpha - \mu_{R^{C}}(\mathbf{x}_{i_{r-1}}, \mathbf{x}_{i_{r}}) \} \} \\ &= \max_{C} \; \{ \alpha - \max_{k} \; \{ \mu_{R}(\mathbf{x}_{i_{1}}, \mathbf{x}_{i_{2}}), \; ..., \; \mu_{R}(\mathbf{x}_{i_{r-1}}, \mathbf{x}_{i_{r}}) \} \} \\ &= \alpha - \min_{C} \; \{ \alpha - \{ \alpha - \max_{k} \; \{ \mu_{R}(\mathbf{x}_{i_{k}}, \mathbf{x}_{i_{k+1}}) \} \} \} \\ &= \alpha - \min_{C} \; \{ \max_{k} \; \{ \mu_{R}(\mathbf{x}_{i_{k}}, \mathbf{x}_{i_{k+1}}) \} \} \end{split}\]

This equality implies that:

\[\mu_{R^+}(x, y) = \min_{C} \{ \max_{k} \{ \mu_{R}(x_{i_k}, x_{i_{k+1}}) \} \}\]

Now we will show that R'is the SDU of R.

• i. It is clear that F*. (x, y) ( p* (x, y) for all x and y in I, since R* = R'k c R.
• ii. If C = (x = xir, *,r, .., X,, = y) is a chain from x to y, we note that L(C; = ma,r {p* (*,u , *,.*, )}.

Suppose that cr is a chain from x to y and c2 is a chain from y to z, such that F** (x,y) = L (Cr) *d F*r (y,z)= L (Ct.

Suppose also that c: is a chain from x to z, constructed from cr and c2 such that:

\[L(C_3) = \max \{L(C_1), L(C_2)\}\]

In this case,

\[L(C_3) = \max \{ \mu_{R^+}(x,y), \mu_{R^+}(y,z) \}\] and we have.

\[\mu_{R^{+}}(x,z) = \min_{C \text{ di } \zeta} L(C) \le L(C_{3}).\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

It implies tlnt R* is an ultrametric on I.

iii. Suppose that U is the USD of R. Now we show that U = R'.

Consider a chain Cr = (x =Xir,xir, ..., xi. = y) from x to y where lt*. (x,y) = L(C1). Then, a. \(\mu_U(x,y) \le \max \{\mu_U(x,z), \mu_U(y,z)\}\) for all x, y and z in I, because U is an ultrametric. Especially,

\[\mu_{U}(x,y) \leq max \ \{\mu_{U} \, (x, \ x_{i_{k}} \ ), \ \mu_{U}( \, x_{i_{k}} \ ;y) \}\] for all k = 1, 2, ..., r. Hence.

\[\begin{split} \mu_U(x,y) & \leq \text{max } \{ \mu_U(x, \ x_{i_2}) \ , \ \mu_U(x_{i_2},y) \} \\ & \leq \text{max } \{ \mu_U(x, \ x_{i_2}) \ , \ \text{max } \{ \mu_U(x_{i_2}, x_{i_3}) \ , \ \mu_U(x_{i_3},y) \} \} \\ & \leq \text{max } \{ \mu_U(x, \ x_{i_2}) \ , \ \mu_U(x_{i_2}, x_{i_3}) \ , \mu_U(x_{i_3},y) \} \end{split}\]

In general we have

\[\mu_U(x,y) \le \max_k \{\mu_U(x_{i_k}, x_{i_{k+1}})\}, 1 \le k \le r-1.\]

b. U is the USD of R. Then by definition, \(U \subseteq R\) or

\[\mu_U(x,y) \le \mu_R(x,y)\], for all x and y in I.

From a and b, we have;

\[\begin{split} \mu_U(x,y) & \leq \max_k \{ \mu_R(|x_{i_k}|,|x_{i_{k+1}}|) \}, \ 1 \leq k \leq r-1. \\ & \leq L(C_1) = \mu_{R^+}(x,y). \end{split}\] or \[\mu_{U}(x,y) \le \mu_{R^{+}}(x,y)\].

It has been shown that \(R^+\) is an ultrametric and U is the SDU of R. Hence the inequality \(\mu_U(x,y) \le \mu_{R^+}(x,y)\) gives us \(\mu_U(x,y) = \mu_{R^+}(x,y)\) or \(U = R^+\).

4. SUB-DOMINANT ULTRAMETRIC AND MINIMUM SPANNING TREE

Through the notion of sub-dominant ultrametric, in this section we will show a necessary and sufficient condition for the uniqueness of minimum spanning tree. Suppose M is a minimum spanning tree of dissimilarity R defined by a dissimilarity index d. If i and j are arbitrary two vertices in M, and (\(i = x_1, x_2, ..., x_r = j\)) is the chain from i to j in M, we know that the distance d between i and j given by

\[\delta(i,j) = \max_{k} d(x_k, x_{k+1})\] is the SDU of R. Hence

\[\mu_{R^{+}}(i, j) = \delta(i, j)\] \[= d(x_{k_{0}}, x_{k_{0}+1})\] for a positive integer \(k_o\). This equality and the above popositions show that the number of zero entries of \((R - R^+)\), substraction of two matrices in the usual sense, determines the uniqueness of its minimum spanning tree. More spesifically we have the following proposition.

Proposition 3 Dissimilarity R has a unique minimum spanning tree if and only if the number of zero entries in the lower (or upper) triangle matrix of \((R - R^+)\) below (or above) diagonal, is equal to (n-1).

If in a dissimilarity there are more than one MSTs, then we can find all MSTs by inspecting zero entries of lower (or upper) triangle matrix of \((R - R^+)\) below (or above) diagonal; we delete all unnecessary zero entries.

5. CONCLUDING REMARK

The ability to detect the uniqueness of MST and the fact that only one MST can be given by all existing algorithms, even for the case where there are actually more than one MST, is the great problem for statisticians in using MST for their statistical analysis. We have handled this problem through the notion of fuzzy relation. There are three propositions resulted in this work; Proposition 1, Proposition 2 and Proposition 3. In particular, Proposition 3 provides us with two fundamental results;

• 1. A necessary and sufficient condition for the uniqueness of MST.
• 2. An algorithm for constructing the union of all possible MSTs which, if it is not unique, gives us all MSTs.

6. ACKNOWLEDGEMENT

We are very grateful to the anonymous referees for their valuable comments.

7. REFERENCES

• 1. Benzecri J.P. L'analyse des données; la taxinomie. Dunod-Paris, 1980.
• 2. Caillez F. and Pages J.P. Introduction a l' Analyse des Données. SMASH Paris, 1976.

• 3. Jambu M. Classification automatique pour l'analyse des données. Dunod Paris 1978
• 4. Djauhari M.A. A Fuzzy Relation Approach in the Detection of Influential Subsets. Proceedings of The Fourth Islamic Countries Conference on Statistical Sciences. Vol. 8, Lahore, August 1994.
• 5. Gray J.B. and Ling. R.F. k-Clustering as a Detection Tool for Influential Subsets in Regression. Technometric, Vol. 26, No. 4, 1984.
• 6. Kaufmann A. Introduction à la théorie des sousensemble flous; Applications à la classification, et à la reconnaissance des formes, aux automates et aux systèmes, aux choix des critères. Masson-Paris 1975.
• 7. Kaufmann A. Introduction àla théorie des sousensemble flous; eléments théoriques de base (Vol. 1), 2éme Edition. Masson-Paris 1977.
• 8. Narshing D. Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall 1974.
• 9. Roux. Classification Automatique. Ecole d' Ete d'Analyse Numérique, Paris 1975.
• 10. Seber G.A.F. Multivariate Observations. John Wiley and Sons, 1984.
• 11. Van Cutsem B. Ultrametrique, distance, $\phi$-distances maximum dominées par une dissimilarité donnée. Statistique et Analyse des Données, Vol 8 No. 2, 1983.