存在至少2个非临界点的强连通有向图  

Strongly Connected Digraphs with at Least Two Noncritical Vertices

作　　者：李春芳[1] 林上为[1,2] 

机构地区：[1]山西大学数学科学学院,山西太原030006 [2]中国科学院数学与系统科学研究院,北京100190

出　　处：《山西大学学报（自然科学版）》2013年第2期149-151,共3页Journal of Shanxi University(Natural Science Edition)

基　　金：国家自然科学基金青年科学基金(61202017);山西省青年科技研究基金(2011021004);中国博士后科学基金(2012M510579)

摘　　要：证明顶点数为n≥3,弧数为m≥(n/2)+2的强连通有向图D中存在两个不同的顶点u*,v*,使得D-u*和D-v*都是强连通的;并用例子说明这里所给的关于弧数的下界是紧的.It is proved that a strongly connected digraph D with n≥3 vertices and at least（n 2）＋2 arcs has two distinct vertices u＊ , v＊ such that both D--u＊ and D--v＊ are strongly connected, and the examples show that the above lower bound on the number of arcs is sharp.

关 键 词：有向图的弧数 强连通子图 非临界点 

分 类 号：O157.5[理学—数学]