| 含有两个非临界点的强连通定向图的弧数 |
| |
| 引用本文： | 林上为,李春芳,王世英.含有两个非临界点的强连通定向图的弧数[J].运筹学学报,2011,15(3):57-61. |
| |
| 作者姓名： | 林上为 李春芳 王世英 |
| |
| 作者单位： | 山西大学数学科学学院,太原,030006 |
| |
| 基金项目： | the National Natural Science Foundation of China(No.11026163,61070229); the Natural Science Foundation for Young Scientists of Shanxi Province(No.2011021004) |
| |
| 摘 要： | 证明顶点数为$n\geq 4$,弧数为$m\geq {n-1 \choose 2}+3$的强连通定向
图$D$中存在两点$u^*$、!$v^*$,使得$D-u^*$和$D-v^*$都是强连通的, 并用例子说明这里所给的
关于弧数的下界是紧的.
|
| 关 键 词： | 有向图 强连通子图 临界点 |
The Number of Arcs of Strongly Connected Oriented Graphs with Two Noncritical Vertices |
| |
| LIN Shangwei,LI Chunfang,WANG Shiying.The Number of Arcs of Strongly Connected Oriented Graphs with Two Noncritical Vertices[J].OR Transactions,2011,15(3):57-61. |
| |
| Authors: | LIN Shangwei LI Chunfang WANG Shiying |
| |
| Institution: | LIN Shangwei LI Chunfang WANG Shiying School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China |
| |
| Abstract: | It is proved that a strongly connected oriented graph D with n ≥ 4 vertices and at least (n-12) + 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. |
| |
| Keywords: | digraph strongly connected subdigraph critical vertex |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
