在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
题库
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
离散数学
旧数据
图论初步
强连通图与单向连通图的判定定理
最后
更新:
2025-01-21 17:04
查看:
47
次
反馈
刷题
强连通图与单向连通图的判定定理
## 强连通图与单向连通图的判定定理 定理7－2．4 设有向图 $G=\langle V, E\rangle, V=\left\{v_1, v_2, \ldots, v_n\right\}$ 。 $G$ 是强连通图当且仅当 $G$ 中存在经过每个顶点至少一次的回路。 证明充分性：如G中有一个经过每个顶点至少一次的回路，则G中任意两个结点都是相互可达的，故G是强连通图。 必要性：由 $G$ 的强连通性可知，$v_i \rightarrow v_{i+1}, i=$ $1,2, \ldots, n-1$ 。 设 $\Gamma_i$ 为 $v_i$ 到 $^2 v_{i+1}$ 的通路。又因为 $v_n \rightarrow v_1$ ，设 $\Gamma_n$ 为 $v_n$到 $v_1$ 的通路，则 $\Gamma_1, \Gamma_2, \ldots, \Gamma_{n-1}, \Gamma_n$ 所围成的回路经过 $G$ 中每个顶点至少一次。 ## 有向图连通 －定义7－2．7 简单有向图 $G=<V, E>$ 中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。 －定理7－2．5有向图G $=\langle V, E\rangle$ 中，它的每一个结点位于且只位于一个强分图中。 证明：1）假设 $v \in V$ ，令 $S$ 是 $G$ 中所有与 $v$ 相互可达的结点的集合，当然 $v$ 也在S中，而 $S$ 是 $G$ 的一个强分图，因此 $G$的每一结点必位于一个强分图中。 2）假设 $v$ 位于两个不同的强分图 $S _1$ 与 $S _2$ 之中，因为 $S _1$ 中每个结点与 v 相互可达，而 v 与 S 2 中每个结点也相互可达，故 $S _1$ 中任何一结点与 $S _2$ 中任何一个节点通过 v 都相互可达，与 $S _1$ 为强分图矛盾。 
刷题
做题，是检验是否掌握数学的唯一真理
上一篇：
有向图连通
下一篇：
邻接矩阵
本文对您是否有用？
有用
(
0
)
无用
(
0
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。