例 例:在下图中,给出了图G以及它的真子图G和生 成子图G。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 例： 例：在下图中，给出了图G以及它的真子图G’和生 成子图G’’
例: 例:在下图(a)、(b)、(c)、(d)中,(a)与(b) 是互为补图;(c)和(d是互为补图 RvI 5 5 2 V3 3 C Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 例： 例：在下图 (a)、(b)、(c)、(d)中，(a)与(b) 是互为补图；(c)和(d)是互为补图
7-2路与回路 路 定义给定图G〈VB,设v,V,…,V∈e e2,…,n∈E其中e;是关联结点v1,v的边,交替 序列va1ve2…!env称为联结v到v的路 令Vo,vn分别为该路的起点和终点,统称为路的端点。 ☆路中边的条数称为该路的长度。 ☆此时,若v=Vn,则该路称为回路。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 7-2 路与回路 一、路 定义 给定图G=〈V,E〉,设v0，v1，…，vn ∈V,e1， e2，…，en ∈E,其中ei是关联结点vi-1 ,vi的边,交替 序列v 0 e1 v1 e2…en vn称为联结v0到vn的路。 ❖v0 ,vn分别为该路的起点和终点，统称为路的端点。 ❖路中边的条数称为该路的长度。 ❖此时，若v0 ＝vn，则该路称为回路
续 >若路中所有边全不相同,则称此路为一条迹; 〉若路中所有结点仝不相同,则称此路为通路。 若回路中除v=ⅴn以外所有结点全不相同,则称此 回路圈。(闭的通路) 在简单图中一条路vne1ve2…envn,由它的结点序 列vv1…vn确定,所以简单图的路由可由其结点序 列v1…,vn表示。在有向图中结点数大于1的 条路可由边序列|e1e2…,!n表示。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn ➢ 若路中所有边全不相同，则称此路为一条迹； ➢ 若路中所有结点全不相同，则称此路为通路。 ➢ 若回路中除v0 ＝vn以外所有结点全不相同，则称此 回路圈。（闭的通路） ➢ 在简单图中一条路v0 e1 v1 e2…en vn ，由它的结点序 列v0 v1 … vn确定,所以简单图的路,由可由其结点序 列[v0 v1 … vn ]表示。在有向图中,结点数大于1的一 条路可由边序列[e1 e2 … en ]表示。 续：
定理 定理在一个具有n个结点的图中,如果从结点v到结 点v存在一条路,则从结点v到结点v必存在一条不 多于n1条边的路。 证明如果从结点v到结点v存在一条路,则该路上 的结点序列是[vy…v…v],如果在这路上有条边, 则序列中必有1个结点,若飞n1,则必有结点vs, 它在序列中不止一次出现,即必有序列 ,在路中去掉从υ到U2的这些边,仍 然得到一条从结点v到结点v的路,但此路比原来的 路的边数要少。如此重复进行下去,必得到一条从结 点U到结点v不多于n-1条边的路。 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定理 定理 在一个具有n个结点的图中，如果从结点vj到结 点v k存在一条路，则从结点vj到结点vk必存在一条不 多于n-1条边的路。 证明 如果从结点vj到结点vk存在一条路，则该路上 的结点序列是[vj…vi…vk ]，如果在这路上有l条边， 则序列中必有l+1个结点，若l>n-1，则必有结点vs， 它 在 序 列 中 不 止 一 次 出 现 ， 即 必 有 序 列 [vj…vs…vs…vk ]，在路中去掉从vs到vs的这些边，仍 然得到一条从结点vj到结点vk的路，但此路比原来的 路的边数要少。如此重复进行下去，必得到一条从结 点vj到结点vk不多于n-1条边的路