极小强连通有向图.pdf

第48卷第5期 厦门大学学报(自然科学版) V01．48No．5 2009年9月 ofXiamen Sep．2009 Journal University(NaturalScience) 极小强连通有向图 徐志霞1’2 (1．南开大学组合数学中心，天津300071； 2．新疆大学数学与系统科学学院．新疆乌鲁木齐830046) 摘要：强连通有向图D称为极小的．若在D中删去任意一条弧，则所得的有向图不是强连通的．讨论了极小强连通有向 图的耳朵分解的一些性质。构造了非平面极小强连通有向图的倒子，证明了极小强连通图的点色数至多是3，并且当极 小强连通图的耳朵分解中每个耳朵的长度不小于4时，它有两个不相交的准核．最后确定了给定顶点数的极小强连通有 向图的弧数的界，刻画了相应的极图． 关键词：强连通有向图；极小强连通有向图；耳朵分解；准核 中图分类号：o157．5 文献标识码：A 文章编号：0438—0479(2009)05—0627—05 连通有向图D，可以在保持强连通的条件下删除D中 I 预备知识 的弧，直到不能删除时为止，所得到的有向图D’是D 的一个生成极小强连通有向子图．由于去掉的弧集可 简单有向图是指没有自环和平行弧的有向图．本 以不同，所以一个强连通有向图可能有多个不同的生 文中研究的有向图是指简单有向图，没有定义的概念 成极小强连通子图．反之，任何强连通图都可以看成是 或术语可以参考[1]． 在它的一个生成极小强连通图中加弧得到的．根据极 记有向图D_--(V，A)，其中V是D的顶点集，A小强连通有向图的定义我们可以看出，极小强连通图 是D的弧集。设D的顶点数IV(D)I一行，弧数』A(D)I的任意强连通子图也是极小的，并且一定是点导出子 =仇．D的基础图是将D的每条弧中的方向去掉，变成 图；反之，极小强连通图的任意点导出子图如果是强连 一条边后得到的无向图．D的基础图中可能有重边，不 通的，则此子图也是极小的． 一定是简单图．我们把从D的基础图中去掉重边得到 在我们熟知的关于有向图的理论中，通常把无圈 的简单图称为D的底图．称有向图D是一个定向图， 有向图当作一类最简单的有向图，或者看成是树在无 若D是在某个简单无向图G的每条边上给一个定向 向图概念中的推广，并且对无圈有向图的性质做了很 得到的有向图，或者说D是一个没有有向2圈的简单 好的刻画[1]．而极小强连通有向图是有向图在强连通 有向图．定向图如果有有向圈的话，最小圈长至少是 意义下的极小图．1985年张福基和郭晓峰[2]研究了极 3． 小强连通有向图的性质和构造方法，给出了极小强连 非平凡有向图D称为强连通的，若对D中任意两 通有向图的2度顶点数的一个精确下界，也给出了几 个顶点“和可，存在从乱到口和从口到“的有向路．有 乎可约矩阵的一种标准形式． 向图D称为志一弧强连通的，如果从D中删除任意少于 志条弧，所得的有向图仍为强连通图．D称为极小忌一弧 2 极小强连通有向图的耳朵分解 强连通图，若D是五一弧强连通的，并且对D中任意一 条弧P，D—P不是忌一弧强连通的．我们也称一个1一弧 在本节中首先给出一般的强连通有向图的耳朵分 强连通有向图D为极小强连通有向图，即若D是强连 鳃的定义，然后刻画极小强连通有向图的耳朵分解的 通有向图，且删去任意一条弧所得的有向图不是强连 一些性质，通过这些性质证明了极小强连通有向图的 通的，则称D是极小强连通有向图．对任意给定