0图的基本概念.pptVIP

离散数学 离散数学 三、图的连通性（续） v2 v3 v4 v1 (a) v2 v3 v4 v1 (b) v2 v3 v4 v1 (c) 强连通图的判定定理： 有向图D强连通，当且仅当D中存在一条回路，至 少经过每个顶点一次。 离散数学 四、点割集与边割集 点割集：设无向图G = V, E，若存在顶点子集 V ?V，使G删除V (将V 中顶点及其关联的边 都删除)后所得子图G –V 满足p(G –V ) p(G)， 而删除V 的任何真子集V 后，p(G –V ) = p(G)， 则称V 为G的一个点割集。 若点割集中只有一个顶点v，则称v为割点。 离散数学 四、点割集与边割集（续） 边割集：设无向图G = V, E，若存在边集子集 E?E，使G删除E(将E中的边从G中全删除) 后所得子图G –E满足p(G –E) p(G)，而删除 E的任何真子集E后，p(G –E) = p(G)， 则称E为G的一个边割集。 若边割集中只有一条边e，则称e为割边(或桥)。 离散数学 四、点割集与边割集（续） 例6：判断下图中所有的点割集和边割集。 v4 v3 v2 e1 e2 e3 e4 e5 e6 v1 v5 v6 v7 e7 e8 e9 点割集有{v2}，{v6}，{v3, v5}。 边割集有{e9}, {e7, e8}, {e6, e7}, {e6, e8}, {e1, e2, e5}, {e1, e2, e3}, {e1, e2, e4}, {e3, e4}, {e3, e5}, {e4, e5}。 离散数学 一、关联矩阵 1、无向图的关联矩阵：设无向图G = V, E， V ={v1, v2, …, vn}，E ={e1, e2, …, em}，令mij为顶点vi 与边ej的关联次数，称M(G) = (mij)n?m为G的关联矩阵。 §7.3 图的矩阵表示 v4 v3 v2 e1 e2 e3 e4 e5 e6 v1 无向图的关联矩阵的性质： (握手定理) 离散数学 一、关联矩阵（续） 2、有向图的关联矩阵：(仅限有向无环图) 设D = V, E，V ={v1, v2, …, vn}，E ={e1, e2, …, em}， 令 称M(D) = (mij)n?m为D的关联矩阵。 vi为ej的始点， vi与ej不关联， vi为ej的终点， v4 v3 v2 e1 e2 e3 e4 e5 v1 有向图的关联矩阵的性质： 离散数学 二、邻接矩阵 邻接矩阵：设有向图D = V, E，V ={v1, v2, …, vn}， |E | = m，令 为顶点vi 邻接到vj 的边的条数， 称A(D) = ( )n?n为D的邻接矩阵。 v4 v3 v2 e1 e2 e3 e4 e5 e6 v1 有向图邻接矩阵的性质： (1) 同一行的元素和为对应顶点的出度 (2) 同一列的元素和为对应顶点的入度 (3) ? ? aij = m 为D中边的总数，即为D中长度为1的通路总数，对角线元素之和为D中环的个数，即D中长度为1的回路总数。 邻接矩阵的元素除主对角线元素外全为1， 则其对应的图是有向完全图和强连通图。 离散数学 二、邻接矩阵 定理 设A为有向图D的邻接矩阵，V ={v1, v2, …, vn}，则Al (l≥1)中元素 为vi到vj长度为l 的通路数， 为D中长度为l 的通路总数， 其中 为D中长度为l 的回路数。 v4 v3 v2 e1 e2 e3 e4 e5 e6 v1 故V1到V3长度为2的通路有3条，V1到V3长度为3的通路有4条，V1到V3长度为4的通路有6条，V1到V1长度为2、3、4的回路各有1条。 D中长度为2的通路总数为10，其中有3条回路。 推论 设Br = A + A2 + … + Ar (r≥1)，则Br中元素 为D中vi到vj长度小于等于r 的通路数， 为D中长度小于等于r 的通路总数， 其中 为D中长度小于等于r 的回路数。 定理 设A 为有向图D的邻接矩阵，则Al（l ≥ 1）中元素 为vi到vj长度为l 的通路数， 为D中长度为l 的通路总数， 其中