何常香，刘伟龙

（上海理工大学 理学院，上海　200093）

2n阶（n-2）-正则二部图的最小基本圈基

何常香，刘伟龙

（上海理工大学 理学院，上海200093）

设图G为2n阶（n-2）-正则二部图.构造了图G的一个基本圈基并且证明了此圈基就是图G的一个最小基本圈基，同时还确定了任意最小基本圈基对应的生成树的结构.

正则二部图；图的圈基；最小圈基；最小基本圈基

0　引　言

设图G为无向图，C为G中的一个圈，对于G中的任意一条边e，e或在C上或不在C上，故圈C可以通过向量γC∈｛0,1｝|E|表示.图G的圈空间是Z2上由｛γC|C是G中的圈｝形成的向量空间.图G的一个圈基由G的一些圈组成，通过圈基中圈的线性组合可以生成G的圈空间.圈基的长度是基中所有圈的长度之和，长度最小的圈基称为图的最小圈基.在文献［1］中定义了圈基的5种分类，分别是基本圈基、弱基本圈基、幺模圈基、整数圈基和无向圈基.在本文中，我们只考虑图的基本圈基.

尽管一个图的最小圈基可以在多项式时间内计算得到［2］，但是对大部分图，要给出其具体的圈基是困难的，这其中某些特殊图类的最小圈基已经被找到［3-5］.在文献［6］中作者证明了计算最小基本圈基的复杂度为APX-hard；在文献［7］中，作者找到了2n阶（n-1）-正则图K2×Kn（这里K2×Kn表示K2与Kn的直积）的一组最小基本圈基.受此启发，本文研究了2n阶（n-2）-正则二部图的最小基本圈基及其对应的生成树的结构.

若G=（V,E）是2n阶二部图，G是完全二部图Kn,n的子图，称Kn,nE（G）为G的二部补图，记为G∗.设V′是V（G）的一个非空子集，以G［V′］表示G的诱导子图.若G是2n阶（n-2）-正则二部图……