利用矩阵求极大相容类的一种方法  

A New Algorithm for Maximal Compatible Classes Based on Matrix

作　　者：陈星[1] 林琼[1] 薛颖[1] 余显志[1] 

机构地区：[1]后勤工程学院基础部

出　　处：《后勤工程学院学报》2010年第4期92-96,共5页Journal of Logistical Engineering University

摘　　要：寻找相容关系的极大相容类和简单图的极大完全子图，在解决二元关系与数据挖掘和管理决策中的具体问题时有重要作用。利用相容关系的极大相容类与简单图的极大完全子图之间的对应关系，对极大完全子图的路径长度进行分析，得到了关于极大完全子图路径长度的一个定理。并根据该定理构造了一个用矩阵的路径长度搜索简单图的极大完全子图的方法，进而利用该方法找出了对应相容关系的极大相容类。It is important to search the maximal compatible classes of compatible relation and the maximum complete-sub- graphs of simple graph, which can be used in data mining, management decision-making and some specific relations. This paper first analyzes the paths length of maximum complete-subgraph, and then presents a theorem of the paths length of maximum about the complete-subgraph and its path length. Furthermore, the paper gives an algorithm for searching maximum complete-subgraph by the theorem and matrix of the path length. According to the correspondence between the maximal compatible classes of compatible rela- tion and the maximum complete-subgraphs of simple graph, the algorithm can be applied to find maximal compatible classes of compatible relations as well.

关 键 词：相容关系 极大完全子图 极大相容类 路径长度 

分 类 号：O157.5[理学—数学]