| 二部图匹配强迫数的谱 |
| |
| 引用本文： | 王洪伟. 二部图匹配强迫数的谱[J]. 山东大学学报(理学版), 2009, 44(12): 30-35 |
| |
| 作者姓名： | 王洪伟 |
| |
| 作者单位： | 临沂师范学院理学院, 山东 临沂 276005 |
| |
| 基金项目： | 临沂师范学院博士科研启动基金 |
| |
| 摘 要： | 改进了Riddle 的尾点法, 得到自然数k属于二部图匹配强迫数谱的必要条件, 给出了二部图的最小强迫数等于一个颜色集所有规范序最小尾点数的充要条件。
|
| 关 键 词： | NP 完全问题 二部图 完美匹配 强迫数 |
| 收稿时间： | 2008-10-06 |
On the spectrum of matching forcing numbers for bipartite graphs |
| |
| WANG Hong-wei. On the spectrum of matching forcing numbers for bipartite graphs[J]. Journal of Shandong University, 2009, 44(12): 30-35 |
| |
| Authors: | WANG Hong-wei |
| |
| Affiliation: | College of Science, Linyi Normal University, Linyi 276005, Shandong, China |
| |
| Abstract: | The trailing-vertex method in essence is improved,a necessary condition for the forcing number of perfect matching equals to a give natural number k for a bipartite graph is obtained,and a necessary and sufficient condition for the minimum forcing number equals the minimum number of trailing vertices of all standard onterings of a color set is given. |
| |
| Keywords: | bipartite graph perfect.matching forcing number NP-complete |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《山东大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《山东大学学报(理学版)》下载全文 |
|
