摘要
研究了(赋权)图的圈基结构并且对包含在最小圈基中的短圈提供了大量信息,建立了一个基变换的Hall型定理,利用此定理,给出了判断一个圈基是最小圈基的充分必要条件,而且,证明了一个(赋权)图的最小圈基结构是唯一的．这一性质对于最大圈基也成立(尽管在最小圈基方面已有很多工作,而在最大圈基方面的工作几乎没有)．利用这些方法,发现了(赋权)图中具有特定性质的短圈的一些新结果．作为应用,决定了一个嵌入图的短圈的结构,并找到一个多项式算法能够判断一个嵌入图中是否存在双侧圈,如果这样的圈存在,就可以找到一个最短的双侧圈．这回答了B．Mohar和C．Thomassen提出的一个未解决问题,并对他们提出的另一个未解决问题给出了部分解答．
出处
《中国科学（A辑）》
CSCD
北大核心
2006年第2期134-145,共12页
Science in China(Series A)
基金
国家自然科学基金资助项目(批准号:10271048)
上海市重点学科基金资助项目
上海市基础研究重点项目(批准号:04JC14031)
