| 枚举图的全部极大独立集的普遍性方法 |
| |
| 摘 要： | 完整地研究了寻找一个图的全部极大独立集所需要的理论、寻找范围、计算公式和枚举方法，采用有根树描述，以邻接矩阵中任意一行所对应的顶点为根，再以该行中各个非零元素所对应的那些顶点为根，按照文中所述方法生成有根树，这些有根树就描述出图的全部极大独立集，本方法已用计算机程序实现。
|
| 关 键 词： | 图，独立集，极大独立集，有根树 |
A General Method for Generating all Maximal Independent Sets of a Graph |
| |
| Authors: | Liu Changlin Shen Shihu Li Jing |
| |
| Institution: | Liu Changlin; Shen Shihu; Li Jing (Dept. of Auto. ) (Dept. of Computer Eng. ) |
| |
| Abstract: | The theory on generating all Maximal Independent Sets (MIS) of a graph and related formulas. approaches are studied completely in this paper. The process to generate MIS is described by some rooted trees. as the roots for which. any one vertex of a given graph and those vertexes being adjoined with it are used. The presented method is general and practical. it has been realized by a computer program. |
| |
| Keywords: | graph independent set maximal independent set rooted tree |
| 本文献已被 CNKI 等数据库收录！ |
