离散数学-图的连通性.ppt

1 6 2图的连通性 6 2 1通路与回路初级通路 回路 与简单通路 回路 6 2 2无向图的连通性与连通度连通图 连通分支短程线与距离点割集 割点 边割集 割边 桥 点连通度与边连通度 2 6 2图的连通性 续 6 2 3有向图的连通性及其分类可达性弱连通 单向连通 强连通短程线与距离 3 通路与回路 定义6 13给定图G 无向或有向的 G中顶点与边的交替序列 v0e1v1e2 elvl 若 i 1 i l ei vi 1 vi 对于有向图 ei 则称 为v0到vl的通路 v0和vl分别为通路的起点和终点 l为通路的长度 又若v0 vl 则称 为回路 若通路 回路 中所有顶点 对于回路 除v0 vl 各异 则称为初级通路或路径 初级回路或圈 长度为奇数的圈称作奇圈 长度为偶数的圈称作偶圈若通路 回路 中所有边各异 则称为简单通路 简单回路 否则称为复杂通路 复杂回路 4 说明 1 表示方法 按定义用顶点和边的交替序列 v0e1v1e2 elvl 用边序列 e1e2 el 简单图中 用顶点序列 v0v1 vl 2 在无向图中 长度为1的圈由环构成 长度为2的圈由两条平行边构成 在无向简单图中 所有圈的长度 3 在有向图中 长度为1的圈由环构成 在有向简单图中 所有圈的长度 2 5 说明 续 3 初级通路 回路 是简单通路 回路 但反之不真 初级通路 非初级的简单通路 初级回路 非初级的简单回路 6 通路与回路 续 定理6 3在n阶图中 若从顶点u到v u v 存在通路 则从u到v存在长度小于等于n 1的初级通路 证若通路中没有相同的顶点 即初级通路 长度必 n 1 若有相同的顶点 删去这两个顶点之间的这一段 仍是u到v的通路 重复进行 直到没有相同的顶点为止 定理6 4在n阶图中 若存在v到自身的简单回路 则一定存在v到自身长度小于等于n的初级回路 7 无向图的连通性与连通分支 设无向图G u v Vu与v连通 若u与v之间有通路 规定u与自身总是连通的 连通图 任意两点都连通的图 平凡图是连通图连通关系R u v V且u与v连通 R是等价关系连通分支 V关于R的等价类的导出子图设V R V1 V2 Vk G的连通分支为G V1 G V2 G Vk 连通分支数p G kG是连通图 p G 1 8 短程线与距离 u与v之间的短程线 u与v之间长度最短的通路 设u与v连通 u与v之间的距离d u v u与v之间短程线的长度若u与v不连通 规定d u v 性质 1 d u v 0 且d u v 0 u v 2 d u v d v u 3 d u v d v w d u w 例如a与e之间的短程线 ace afe d a e 2 d a h 9 点割集与边割集 设无向图G v V e E V V E E 记G v 从G中删除v及关联的边G V 从G中删除V 中所有的顶点及关联的边G e 从G中删除eG E 从G中删除E 中所有边定义6 15设无向图G V V 若p G V p G 且 V V p G V p G 则称V 为G的点割集 若 v 为点割集 则称v为割点 设E E 若p G E p G 且 E E p G E p G 则称E 为G的边割集 若 e 为边割集 则称e为割边或桥 10 实例 说明 Kn无点割集n阶零图既无点割集 也无边割集 若G连通 E 为边割集 则p G E 2若G连通 V 为点割集 则p G V 2 e f 点割集 e f 割点 c d 桥 e8 e9 边割集 e8 e9 e1 e2 e1 e3 e6 e1 e3 e4 e7 11 点连通度与边连通度 定义6 16设无向连通图G G min V V 是G的点割集或使G V 成为平凡图 称为G的点连通度 G min E E 是G的边割集 称为G的边连通度 例如 3 G 3 G 12 点连通度与边连通度 续 说明 1 若G是平凡图 则 G 0 G 0 2 若G是完全图Kn 则 G n 1 G n 1 3 若G中存在割点 则 G 1 若G中存在割边 则 G 1 4 规定非连通图的点连通度和边连通度均为0定理6 5对任何无向图G 有 G G G 13 有向图的连通性及其分类 设有向图D u v V u可达v u到v有通路 规定u到自身总是可达的 u与v相互可达 u可达v且v可达uD弱连通 连通 略去各边的方向所得无向图为连通图D单向连通 u v V u可达v或v可达uD强连通 u v V u与v相互可达D是强连通的当且仅当D中存在经过所有顶点的回路D是单向连通的当且仅当D中存在经过所有顶点的通路 14 实例 15 有向图中的短程线与距离 u到v的短程线 u到v长度最短的通路 设u可达v 距离d u到v的短程线的长度若u不可达v 规定d 性质 d 0 且d 0 u vd d d注意 没有对称性 16 6 3图的矩阵表示 6 3 1无向图的关联矩阵6 3 2有向无环图的关联矩阵6 3 3有向图的邻接矩阵有向图中的通路数与回路数6 3 4有向图的可达矩阵 17 无向图的关联矩阵 设无向图G V v1 v2 vn E e1 e2 em 令mij为vi与ej的关联次数 称 mij n m为G的关联矩阵 记为M G mij的可能取值为 0 1 2 例如 18 关联矩阵的性质 6 ej是环 第j列的一个元素为2 其余为0 5 vi是孤立点 第i行全为0 19 无环有向图的关联矩阵 20 实例 21 有向图的邻接矩阵 设有向图D V v1 v2 vn E e1 e2 em 令为顶点vi邻接到顶点vj边的条数 称 m n为D的邻接矩阵 记作A D 简记作A 22 实例 23 有向图中的通路数与回路数 定理6 6设A为n阶有向图D的邻接矩阵 则Al l 1 中元素等于D中vi到vj长度为l的通路 含回路 数 等于vi到自身长度为l的回路数 等于D中长度为l的通路 含回路 总数 等于D中长度为l的回路总数 24 有向图中的通路数与回路数 续 推论设Bl A A2 Al l 1 则Bl中元素等于D中vi到vj长度小于等于l的通路 含回路 数 等于D中vi到vi长度小于等于l的回路数 等于D中长度小于等于l的通路 含回路 数 为D中长度小于等于l的回路数 25 实例 续 说明 在这里 通路和回路数是定义意义下的 v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条 其中回路3条 26 有向图的可达矩阵 性质 P D 主对角线上的元素全为1 D强连通当且仅当P D 的元素全为1 设有向图D V v1 v2 vn 令称 pij n n为D的可达矩阵 记作P D 简记为P 27 实例 例1 1 v1到v4 v4到v1长为3的通路各有多少条 2 v1到自身长为1 2 3 4的回路各有多少条 3 长为4的通路共有多少条 其中有多少条回路 4 长度小于等于4的回路共有多少条 5 写出D的可达矩阵 并问D是强连通的吗 解 28 实例 续 v1到v4长为3的通路有条 3 v4到v1长为3的通路有条 0 v1到自身长为1 2 3 4的回路各有条 1 长为4的通路共有条 其中有条回路 16 3 长度小于等于4的回路共有条 8 可达矩阵 非强连通 单连通