在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
题库
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
离散数学
旧数据
图论初步
路与回路
最后
更新:
2025-01-21 16:58
查看:
26
次
反馈
刷题
路与回路
## 路与回路 定义7－2．1 给定图G $=< V , E >$ ，设 $v 0, v 1, \ldots, Vn \in V$ ， $e 0, e 1, \ldots, e n \in E$ ，其中 $e i$ 是关联于结点 $V i-1, v i$ 的边，交替序列voe1v1 e2．．．envn称为联结vo到vn的路。 $v o$ 和 $v n$ 分别称作路的起点和终点。边的数目 $n$ 称作路的长度。 －当 $v 0= vn$ 时路称作回路。若路中所有的边均不相同，称作迹。若路中所有结点均不相同，称作通路。若除 $v 0= vn$ 以外所有结点均不相同的路称作圈。   定理7－2．1 n阶图中，如果从结点 $v _{ j }$ 到 $vk _{ k }$ 存在一条路， 则必存在一条不多于 $n-1$ 条边的路。 证明： 如果从结点 $V j$ 到结点 vk 存在一条路，该路上的结点序列是 $V j _{ F } \ldots Vi \ldots Vk$ ，如果在这条路中有 $l$ 条边，则序列中必有 $l+1$ 个结点，若 $l>n-1$ ，则必有结点 $V _{ s }$ ，它在序列中不止一次出现，即必有结点序列 $V _{ j } \ldots V$ ．．．．Vs．．．Vk，在路上去掉从 $V _{ s }$ 到 $V _{ s }$ 的这些边，仍是 $V _{ j }$ 到 $Vk _{ k }$ 的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从 v j到 $V _{ k }$ 的不多于 $n-1$ 条边的路。 推论在一个具有 n 个结点的图中，若从结点 $v _{ j }$ 到 $Vk _{ k }$ 存在一条路，则必存在一条从 V j 到 Vk 不多于 $n -1$ 条边的通路。
刷题
做题，是检验是否掌握数学的唯一真理
上一篇：
图的同构
下一篇：
连通图与连通分支
本文对您是否有用？
有用
(
0
)
无用
(
0
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。