7-2 路及回路.pdf

7-2 路与回路 在现实世界界中,常常要考虑这样的一 个问题: 如何从一个图G 中的给定的结点出发, 沿着一些边连续移动, 达到另一个指定的结 点,这种依次由点和边组成的序列, 就形成 路的概念。 定义7-2.1 路 给定图G= 〈V,E〉,设v ，v ，…，v ∈V, 0 1 n e ，e ，…，e ∈E,其中e 是关联结点v ,v 1 2 n i i-1 i 的边,交替序列v e v e …e v 称为联结v 到 0 1 1 2 n n 0 vn 的路。 路:v e v v e v e v e v e v 1 2 3 2 3 3 4 2 6 5 7 3 [定义] 路的长度 v 和v 分别称作路的起点和终点, 边的数 0 n 目n称作路的长度。 [定义] 回路 当v =v 时, 这条路称作回路。 0 n [定义] 迹 若一条路中所有的边e ，e ，…，e 均不 1 2 n 相同,称作迹。 (边不相同，但结点可以重复) 迹:v e v e v e v e v e v 5 8 4 5 2 6 5 7 3 2 4 [定义] 通路 若一条路中所有的结点v ，v ，…，v 均 0 1 n 不同,则称作通路。 (1)通路:v e v e v e v e v 4 8 5 6 2 1 1 2 3 (2)在简单图中的一条通路必定也是迹 [定义] 圈 闭的通路,即除v =v 外,其余的结点均不相 0 n 同的路,就称作圈。 圈:v e v e v e v e v 2 1 1 3 3 7 5 6 2 例如在图7-2.1中有 图7-2.1 路的例子 路:v e v v e v e v e v e v 1 2 3 2 3 3 4 2 6 5 7 3 迹:v e v e v e v e v e v 5 8 4 5 2 6 5 7 3 2 4 通路:v e v e v e v e v 4 8 5 6 2 1 1 2 3 圈:v e v e v e v e v 2 1 1 3 3 7 5 6 2 在简单图中一条路v e v e …e v ，由它的 0 1 1 2 n n 结点序列v v