Pattern Recognition, 4th Edition

15.2.3. Algorithms Based on Directed Trees

An alternative clustering scheme, based on the idea of directed trees, is proposed in [Koon 76]. Before we proceed, let us give some definitions. We recall that a directed graph is a graph whose edges are directed (see Figure 15.6a). We say that a set of edges eⁱ¹,…, e^iq constitute a directed path from a vertex A to a vertex B, if A is the initial vertex of eⁱ¹, B is the final vertex of e^iq, and the destination vertex of the edge e^ij, j = 1,…, q − 1, is the departure vertex of the edge e^ij+1. For example, in Figure 15.6a, the sequence e¹, e², e³ constitutes a directed path connecting the vertices A and B. Finally, a directed tree is a directed graph with a specific node A, known as root, such that ...