A Graph Theoretic Analysis of Pattern Classification via Tamura's Fuzzy Relation

Abstract

Graph theoretical arguments are used to show that the hierarchical clustering scheme induced by Tamura's N-step fuzzy relation f is contained in the maximal single linkage hierarchy. A method of computing f is proposed, based upon Prim's algorithm for generating maximal spanning trees and a result reported by Hu on maximal capacity routes in maximal spanning trees. It is shown that this procedure is superior to Tamura's generalized matrix multiplication algorithm with regard to both computing time and storage requirements.