论文部分内容阅读
强连通有向图D称为极小的，若在D中删去任意一条弧，则所得的有向图不是强连通的．讨论了极小强连通有向图的耳朵分解的一些性质，构造了非平面极小强连通有向图的例子，证明了极小强连通图的点色数至多是3，并且当极小强连通图的耳朵分解中每个耳朵的长度不小于4时，它有两个不相交的准核．最后确定了给定顶点数的极小强连通有向图的弧数的界，刻画了相应的极图．