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

运筹学学报 ›› 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

摘要/Abstract

摘要： 证明顶点数为$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

林上为, 李春芳, 王世英. 含有两个非临界点的强连通定向图的弧数[J]. 运筹学学报, 2011, 15(3): 57-61.

LIN Shang-Wei, LI Chun-Fang, WANG Shi-Ying. The Number of Arcs of Strongly Connected Oriented Graphs with Two Noncritical Vertices[J]. Operations Research Transactions, 2011, 15(3): 57-61.

[1]	董艳侠, 薛涛, 张广. 广义de Bruijn有向图的k-元控制集[J]. 运筹学学报, 2021, 25(2): 127-134.
[2]	董艳侠, 张广, 单而芳. 广义de Bruijn和Kautz有向图的双向控制集[J]. 运筹学学报, 2016, 20(3): 99-106.
[3]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[4]	肖毛, 王文环. 不含偶圈双圈图的极小斜能量[J]. 运筹学学报, 2014, 18(4): 85-95.
[5]	蓝以信, 王应明. 随机DEA期望值模型的一些性质[J]. 运筹学学报, 2014, 18(2): 29-39.
[6]	杨建芳, 高岩. 营救设备数量受限的应急疏散模型和算法[J]. 运筹学学报, 2014, 18(2): 77-86.
[7]	晁绵涛, 简金宝, 梁东颖. 次b凸函数和次b凸规划[J]. 运筹学学报, 2012, 16(2): 1-8.
[8]	姚奕荣, 安柳, 陈熙, 郑权. 可达到和可逼近总极小点的存在性和最优性[J]. 运筹学学报, 2012, 16(2): 32-40.
[9]	伊博, 李仲飞, 曾燕. 基于动态VaR约束与随机波动率模型的最优投资策略[J]. 运筹学学报, 2012, 16(2): 77-90.
[10]	邵嘉婷, 徐大川. 随机容错设施布局问题的近似算法[J]. 运筹学学报, 2012, 16(1): 13-20.
[11]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[12]	尚有林, 刘牧华, 李璞. 一种新的逼近精确罚函数的罚函数及性质[J]. 运筹学学报, 2012, 16(1): 56-66.
[13]	翁克瑞. 带固定轴线成本的轴辐式网络设计问题[J]. 运筹学学报, 2012, 16(1): 88-96.
[14]	米辉, 张曙光. 不完全市场下考虑损失厌恶的连续时间投资组合选择[J]. 运筹学学报, 2012, 16(1): 1-12.
[15]	唐丹, 王鹤朝, 单而芳. 完全多部图与完全图Kronercker积的点参数研究[J]. 运筹学学报, 2012, 16(1): 31-40.