English

运筹学学报 ›› 2011, Vol. 15 ›› Issue (3): 57-61.

• 运筹学 • 上一篇    下一篇

 含有两个非临界点的强连通定向图的弧数

 林上为, 李春芳, 王世英   

  • 出版日期:2011-09-20 发布日期:2011-09-20

The Number of Arcs of Strongly Connected Oriented Graphs with Two Noncritical Vertices

 LIN  Shang-Wei, LI  Chun-Fang, WANG  Shi-Ying   

  • Online:2011-09-20 Published:2011-09-20

PDF

1118

摘要： 证明顶点数为$n\geq 4$,弧数为$m\geq {n-1 \choose 2}+3$的强连通定向
图$D$中存在两点$u^*$、!$v^*$,使得$D-u^*$和$D-v^*$都是强连通的, 并用例子说明这里所给的
关于弧数的下界是紧的.

关键词:  , 有向图, 强连通子图, 临界点

Abstract: It is proved that a strongly
 connected oriented graph $D$ with $n\geq 4$ vertices and  at least ${n-1 \choose 2}+3$
 arcs has two distinct vertices $u^*, v^*$ such that both $D-u^*$ and $D-v^*$ are strongly connected. The examples
show that the above lower bound on the number of arcs is sharp.

Key words:  digraph,  , strongly connected subdigraph, critical vertex