离散件9_图道路与连通.pptVIP

第二节 图的道路与连通;例：下图中 p1=v1e1v1e2v2e2v1e5v4e8v3e6v2 p2=v1e2v2e6v3e8v4e5v1e4v3e9v5 p3=v1e5v4e8v3e6v2 （简记为：p3=v1v4v3v2） p4=v6 都是道路。;2。道路的分类： ① 迹：任何满足道路定义的道路 。 ② 简单道路：边不重复出现的道路。 ③ 基本道路：结点不重复出现的道路。 例：上图中，p1是迹，p2是简单道路， p3是基本道路，p4是零道路。;3。回路：起点和终点相同的道路。 边不重复出现的回路称为简单回路。 结点不重复出现的回路称为圈。 例：下图中，c1是一般回路，c2是简单回路，c3是圈。 ;例：下图中 c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1 c2=v1e1v1e2v2e3v1e5v4e8v3e4v1 c3=v1e5v4e10v6e12v5e9v3e4v1 （c3可简记为：c3=v1v4v6v5v3v1）都是回路。 c1是一般回路，c2是简单回路，c3是圈。;4。定理：设G是n阶图，如果存在从结点u到 v的道路，则必存在长度不超过n-1的道路。 证明要点：如果结点u到v的道路 p的长度 超过n-1，则 p中至少有n+1个结点，因而 道路中至少有一个结点出现两次，如 viei ...v1 ，则去掉ei...vi后仍是结点u到v的 道路，但是道路长度至少短1。重复这一 过程，即得所需结论。;二、无向图的连通问题 1。定义: 如果存在从结点u到结点v的道路，则称u到v是连通的。 结点集V上的“连通”关系具有性质：自反、对称、传递。 2。如果图G中任何两个结点都是连通的，则称G是连通图。;3。图G中的极大连通子图称为图G的支， 图G的支数记为?(G)。 图G连通当且仅当?(G)=1。 例：下图中?(G)=3。 ;4。连通图G=(V, E)的点割集定义：设S ? V，如果 ?(G-S) 1，则称S是G的一个点割集。 ① S是G的一个点割集，而S的任何真子集都不是点割集时，称S是G的一个基本点割集。 如 S1={v2，v5}， S2={v2，v6}, S3={v2，v7}， S4={v3，v5}, S5={v4} ② 由单个结点（如u）构成的点割集简称为割点。 ;定理 结点u是图G的割点当且仅当存在两结点v和w，使v到w的任何道路都经过u。 证明要点： “?”, 当u是割点时，则G ? u至少有2支，从这2支中各选一个结点即可。 “ ?”,反之，如果 v到 w的任何道路都经过 u，则去掉 u后 ，v和 w各在 G ? u的 1支中，即u是割点。;5。连通图G=(V, E)的边割集定义：设F ? E，如果?(G - F) 1，则称F是G的一个边割集。 ① F是G的一个边割集，而F的任何真子集都不是边割集时，称 F是G的一个基本边割集。 如F1={v2v3，v3v7}，F2={v2v3，v5v7}, F3={v1v4}，F4={v2v4，v2v6，v5v6}, F5={v4v6，v2v6，v2v5，v3v7} ② 由单条边（如uv）构成的边割集简称为割边。;定理 边e是图G的割边当且仅当 e 不在G的任何回路上。 证明要点： “?”: 当e是割边时，则G ? e有2支，因而e 不在G的任何回路上。 “ ?”: 反之，如果 e不在任何回路上，则去掉 e 后，e 关联的两个结点各在 G ? e的 1支中，即 e 是割边。 ; 6. 图的连通度(限无环图G) (1)点连通度: 记为К(G), 定义为 最小基本点割集基数, 当G ? Kn К(G) ? n?1, 当G ? Kn 例如下图中, К(G) ?2 ;(2)边连通度: 记为λ(G), 定义为 最小基本边割集基数, 当G ? K1 λ(G) ? 0, 当G ? K1 例如下图中, К(G) ?2, λ(G) ?2;;(3)连通度定理: К(G) ?λ(G) ? ? 证明要点: 首先, 每个结点关联的边构成一个边割集, 于是λ(G) ? ?. 下面证明К(G) ?λ(G) ： 首先注意对每个基本边割集F， ?(G-F)=2；其次设F含λ(G)条边，G-F的2支为G1和G2，若G不是二部图，则去掉这支中与F关联的全部结点即可；若G是二部图，则交替删去这2支中与F关联的结点即可。;四、有向图的道路 1。定义：如果图G中由结点和边交替构成的序列 p=v0e1v1