首页 | 本学科首页   官方微博 | 高级检索  
     检索      

二部图匹配强迫数的谱
引用本文:王洪伟.二部图匹配强迫数的谱[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
Institution: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
本文献已被 万方数据 等数据库收录!
点击此处可从《山东大学学报(理学版)》浏览原始摘要信息
点击此处可从《山东大学学报(理学版)》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号