| 图的极大Tutte集的几个有效算法 |
| |
| 引用本文： | 简芳洪,李德明.图的极大Tutte集的几个有效算法[J].数学的实践与认识,2012,42(4):195-199. |
| |
| 作者姓名： | 简芳洪 李德明 |
| |
| 作者单位： | 1. 九江学院理学院,江西九江,332005
2. 首都师范大学数学科学学院,北京,100037 |
| |
| 摘 要： | 图G=(V,E)的Tutte集定义为X■V(G)满足ω_o(G-X)一|X|=def(G).若不存在Tutte集Y■X,则称X为图G的极大Tutte集.通过找极大extreme集和D-图的极大独立集给出一般图G的找极大Tutte集的两个有效算法,并给出结论:X■V(G)是二部图G的极大Tutte集当且仅当X为二部图G的最小覆盖,从而得到找二部图G的极大Tutte集的一个有效算法.
|
| 关 键 词： | Tutte集 extreme集 def(G) D-图 最大匹配 最小覆盖 |
Some Efficient Algorithms for Maximal Tutte Sets |
| |
| JIAN Fang-hong
,
LI De-ming.Some Efficient Algorithms for Maximal Tutte Sets[J].Mathematics in Practice and Theory,2012,42(4):195-199. |
| |
| Authors: | JIAN Fang-hong LI De-ming |
| |
| Institution: | 1.School of Science,Jiujiang University,Jiujiang 332005,China) (2.Department of Mathematics,Capital Normal University,Beijing 100037,China) |
| |
| Abstract: | A Tutte set of a graph G =(V,E) is defined as X■V(G) andω_o(G-X) - |X|= def(G).If there is no Tutte set Y■X,X is a maximal Tutte set of graph.Through finding maximal extreme sets and maximal independent sets of D-graphs,Given two efficient algorithms for maximal Tutte sets of graphs,and a conclusion:X■V(G) is a maximal Tutte set of a bipartite graph G if only and if X is a minimum cover of the bipartite graph G,an efficient algorithm for maximal Tutte sets of bipartite graphs is given. |
| |
| Keywords: | Tutte sets extreme sets def(G) D-graph maximum matching minimum cover |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
